中山大学数据结构期末测试题

1、读书破万卷下笔如有神警中山大学授予学士学位工作细则第六条考试作弊不授予学士学位计算机科学系 2008上学期数据结构与算法期末考试试题(A )任课教师：考试形式：闭卷考试时间：小时年级：07 班别：专业：姓名：学号：_成绩一. (10分)标准模板库提供了数据结构vector和list.请回答下列问题：1. 它们的逻辑结构和存储结构分别是什么？答：vector和list的逻辑结构均是线性结构，存储结构分别是连续的和链式的。Vector和list是线性表的两种不同实现。2. 这两种数据结构各有什么特点，或者更适用于什么样的场合？答：vector是一种随机存取结构，插入和删除平均需要移动一半的元素；l

2、ist是顺序存取结构，插入和删除只需要修改指针。或者答：vector适用于元素个数已知，需要随机存取，但是，插入和删除不多的场合。List适用于元素个数未知，随机存取不重要，但是，插入和删除频繁的场合。二. (10分)回答下列问题：1. 将下列函数按照增长顺序(由慢到快)排列2n, 10n ,100n, log n, log n , e , 15n+100log n, n!答：e10, log n, log n3, 15n +100log n, 100n, 10n 2, 2n, n!有些同学把2n与n!的增长顺序搞反了。有同学把整个顺序颠倒了。注意题目要求。我们做程序的人皆不可不顾客户的要求，

3、否则，饭碗就被自己砸掉了！2. 说明下列函数的时间复杂度和空间复杂度(包含过程)int fun(int n) if (n=0 | n=1) return 1; else return 2 * fun(n-2) +1;答：T(0)=T(1)=1; T(n)=T(n-2) +1=T(n-2 *n/2) + n /2= T(0) + n /2=O( n)S(n)为递归深度，即 O(n/2).三. (15分)回答快速排序的有关问题。假定选择最左元素作为支点。1. 快速排序是不是稳定的？为什么？(举例或者给出证明)答：不稳定。如，输入1,2,1,第一次划分后：1, 1, 2,也是排序结果，两个1的前后次

4、序已经改变。有同学答“稳定”，不知道从哪里学来的。举例通常找最简单的例子。2. 快速排序在什么条件下最坏情况发生？试分析最坏情况复杂度。答：当输入已经有序，戈U分结果前半部分为空，后半部分有n-1个元素，所以比较次数 T(n) = n+T(n-1),解得T(n)=n(n+1)/2=O(n 2).本题和下题均要求做简单分析。3. 快速排序在什么情况下最好情况发生？试分析最好情况复杂度。答：最好情况发生在一次划分后前后两部分均约含一半元素，比较次数T(1) = 0, T(0)=0,T(n)=n+2T(n/2)=n log n + 2log nT(n/2 log n) = nlog n + n =

5、O(nlog n).四. (10分)假设 N(h)表示高度为h的AVL树的最少结点数。假定单根树的高度为0。1. 试给出 N(0), N(1), N(2), N(3)的值。答： N ( 0) =1,N(1)=2, N(2)=4, N(3) = 72. 给出N(h)的递推公式。答：N(0)=1, N(1)=2, N(h)=1+N(h-1)+N(h-2)3. 将关键字cup, cop, copy, hit, hi, his, hig依次插入空 AVL树，试画出每次插入结束后的状态。 答：略五. (15分)回答下列问题：1. 二分查找平均时间复杂度是什么？使用二分查找算法的前提条件是什么？实现二分查

6、找应该使用什么数据结构或者存储结构？答：二分查找平均时间复杂度O(log n).前提是查找记录按照关键字有序。实现二分查找应该用顺序结构存储。2. 与二分查找相比较，使用二叉查找树进行查找有什么特点？答：二分查找的平均时间性能也是O(log n),但是插入和删除不需要移动元素，适合于动态查找。3. 假定hash函数为h(k)=k%13，表长为13。.试画出使用平方探查法依次插入15,16,32,67,55,28的hash表，并计算查找76和67的探查次数。答：hash table略。查找76和67的探查次数分别是 2和4。六. (15分)对于图1回答下列问题:1. 画出图1的邻接表示意图4AA

7、fMAl2. 拓扑排序的一种方法是排其前驱结点已经全部排序的结点。试给出图1的拓扑排序，假定用一个队列存储当前可排序的结点。假定初始堆包含0, 4,其中0是队首。答: 0 4 1 6 5 8 9 7 3 23. 请写出拓扑排序算法，并在尾部加上一段代码说明图是否存在圈。假定数组indgree表示排序过程中各结点的前驱数目。答: template vint graph_size>void Digraphvgraph_size>:breadth_sort(ListvVertex> &topological_order)/*Post: The vertices of the

8、 Digraph are arranged into the Listtopological_order which is found with a breadth-first traversal of those vertices that do not belong to a cycle.Uses: Methods of classes Queue and List.*/代码略。参考课本。/用sorted表示已排序结点数If (sortedvgraph.size)Cout vv There must be a cycle”ElseCout vv There is no cycle”图1 （

9、六题图）七. （15分）回答下列问题:1.假定图G是二叉树。二叉树G的哪种遍历序对应图G从根结点开始的深度优先遍历?5CrEFBCA.DEADBCEGBD三IcGDFHLG&Adjac&ncy:答：二叉树的先根次序对应深度优先遍历。2. 给出下列深度优先遍历算法，请写出对图2调用dfs（G,D）的结点遍历顺序（参照下图的邻接表）答: DGHEIBACF3. 请说明，如何修改以上算法使之实现宽度优先遍历。Boolean visitedV.size Dfs(graph G, vertex x) for each vertex u in V visitedu=false;list L

10、 = empty; search(x);while (L nonempty) remove w from end of L if visitedw=false search(w);search(vertex v)print(v); visited(v)=true; for each w in Adjvif （visitedw=false） add w to end of L答：将"remove w from end of L ”修改为"remove from the front of L ” ,或者将算法中的"栈”改 为“队列”。八. （10分）一个最小最大堆（min max heap ）是一颗完全二叉树，每个结点均包含一个关键字。树的根 结点称为第1层。如果x是树上奇数层（又称最小层）的结点，则以x为其根结点的二叉树上所有结点关键字均大于 x.如果x是树上偶数层（又称最大层）的结点，则以 x为其根结点的二叉树上所有 结点关键字均小于x.1.试构造包含1,2,3,4,5,6,7,8,9,10的最小最大堆。2436$ /589答：（可以是其它形式的）2. 试问如何求最小最大堆的最小关键字结点和最大关键字结点？答：最小关键字在根结点。最大关键字是根结点的最大子结点（如果有子结点）。3. 试实现删除最小最大堆的最小关键字结点运算delMin（结果仍