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

1《中山大学授予学士学位工作细则》第六条考试作弊不授予学士学位计算机科学系2008上学期《数据结构与算法》期末考试试题(A)任课教师：考试形式：闭卷考试时间：小时年级：07班别：专业：姓名：_____学号：_成绩一．（１０分）标准模板库提供了数据结构vector和list.请回答下列问题：１．它们的逻辑结构和存储结构分别是什么？答：vector和list的逻辑结构均是线性结构，存储结构分别是连续的和链式的。Vector和list是线性表的两种不同实现。２．这两种数据结构各有什么特点，或者更适用于什么样的场合？答：vector是一种随机存取结构，插入和删除平均需要移动一半的元素；list是顺序存取结构，插入和删除只需要修改指针。或者答：vector适用于元素个数已知，需要随机存取，但是，插入和删除不多的场合。List适用于元素个数未知，随机存取不重要，但是，插入和删除频繁的场合。二．（１０分）回答下列问题：１．将下列函数按照增长顺序（由慢到快）排列2n,10n2,100n,logn,logn3,e10,15n+100logn,n!答：e10,logn,logn3,15n+100logn,100n,10n2,2n,n!有些同学把2n与n!的增长顺序搞反了。有同学把整个顺序颠倒了。注意题目要求。我们做程序的人皆不可不顾客户的要求，否则，饭碗就被自己砸掉了！２．说明下列函数的时间复杂度和空间复杂度（包含过程）intfun(intn){if(n==0||n==1){return1;}else{return2*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).三．（１５分）回答快速排序的有关问题。假定选择最左元素作为支点。１．快速排序是不是稳定的？为什么？（举例或者给出证明）答：不稳定。如，输入1,2,1,第一次划分后：1，1，2，也是排序结果，两个1的前后次序已经改变。有同学答“稳定”，不知道从哪里学来的。举例通常找最简单的例子。２．快速排序在什么条件下最坏情况发生？试分析最坏情况复杂度。答：当输入已经有序，划分结果前半部分为空，后半部分有n-1个元素，所以比较次数T(n)=n+T(n-1)，解得T(n)=n(n+1)/2=O(n2).本题和下题均要求做简单分析。３．快速排序在什么情况下最好情况发生？试分析最好情况复杂度。答：最好情况发生在一次划分后前后两部分均约含一半元素,比较次数T(1)=0,T(0)=0,T(n)=n+2T(n/2)=…=nlogn+2lognT(n/2logn)=nlogn+n=O(nlogn).四．（１０分）假设N(h)表示高度为h的AVL树的最少结点数。假定单根树的高度为０。１．试给出N(0),N(1),N(2),N(3)的值。答：N（0）=1,N(1)=2,N(2)=4,N(3)=7警示2２．给出N(h)的递推公式。答：N(0)=1,N(1)=2,N(h)=1+N(h-1)+N(h-2)３．将关键字cup,cop,copy,hit,hi,his,hig依次插入空AVL树，试画出每次插入结束后的状态。答：略五．（１５分）回答下列问题：１．二分查找平均时间复杂度是什么？使用二分查找算法的前提条件是什么？实现二分查找应该使用什么数据结构或者存储结构？答：二分查找平均时间复杂度O(logn).前提是查找记录按照关键字有序。实现二分查找应该用顺序结构存储。２．与二分查找相比较，使用二叉查找树进行查找有什么特点？答：二分查找的平均时间性能也是O(logn),但是插入和删除不需要移动元素，适合于动态查找。３．假定hash函数为h(k)=k%13，表长为13。.试画出使用平方探查法依次插入15,16,32,67,55,28的hash表，并计算查找76和67的探查次数。答：hashtable略。查找76和67的探查次数分别是2和4。六．（１５分）对于图１回答下列问题：１．画出图１的邻接表示意图答：２．拓扑排序的一种方法是排其前驱结点已经全部排序的结点。试给出图１的拓扑排序，假定用一个队列存储当前可排序的结点。假定初始堆包含0，4，其中0是队首。答：0416589732３．请写出拓扑排序算法，并在尾部加上一段代码说明图是否存在圈。假定数组indgree[]表示排序过程中各结点的前驱数目。答：templateintgraph_sizevoidDigraphgraph_size::breadth_sort(ListVertex&topological_order)/*Post:TheverticesoftheDigrapharearrangedintotheListtopological_orderwhichisfoundwithabreadth-firsttraversalofthoseverticesthatdonotbelongtoacycle.Uses:MethodsofclassesQueueandList.*/3{//代码略。参考课本。//用sorted表示已排序结点数If(sortedgraph.size)Cout“Theremustbeacycle”ElseCout“Thereisnocycle”}图1（六题图）图2（七题图）七．（15分）回答下列问题：１．假定图G是二叉树。二叉树Ｇ的哪种遍历序对应图G从根结点开始的深度优先遍历？答：二叉树的先根次序对应深度优先遍历。２．给出下列深度优先遍历算法，请写出对图2调用dfs(G,D)的结点遍历顺序（参照下图的邻接表）。答：DGHEIBACF３．请说明，如何修改以上算法使之实现宽度优先遍历。Booleanvisited[V.size]Dfs(graphG,vertexx){foreachvertexuinVvisited[u]=false;listL=empty;search(x);while(Lnonempty)removewfromendofLifvisited[w]==false{search(w);}}search(vertexv){print(v);visited(v)=true;foreachwinAdj[v]4if(visited[w]==false)addwtoendofL}答：将“removewfromendofL”修改为“removefromthefrontofL”,或者将算法中的“栈”改为“队列”。八．（10分）一个最小最大堆（minmaxheap）是一颗完全二叉树，每个结点均包含一个关键字。树的根结点称为第1层。如果x是树上奇数层（又称最小层）的结点，则以x为其根结点的二叉树上所有结点关键字均大于x.如果x是树上偶数层（又称最大层）的结点，则以x为其根结点的二叉树上所有结点关键字均小于x.１．试构造包含1,2,3,4,5,6,7,8,9,10的最小最大堆。答：（可以是其它形式的）２．试问如何求最小最大堆的最小关键字结点和最大关键字结点？答：最小关键字在根结点。最大关键字是根结点的最大子结点（如果有子结点）。３．试实现删除最小最大堆的最小关键字结点运算delMin(结果仍然保持最小最大堆.可以用伪代码)。答：delMin可以通过删除最后一个结点x，将x插入到根结点，然后从上到下调整。首先在min层构成的堆上自上而下调整一层，然后与比较x所在的min层的父结点比较，并做相应调整，一直调整至叶结点。４．按照你的算法，画出依次输出前三个最小元素后的最小最大堆。答：总的来说，题目都是讲过的，或者做过的，最后一个例外。