《important数据结构》由会员分享，可在线阅读，更多相关《important数据结构（4页珍藏版）》请在金锄头文库上搜索。
1、个人收集整理 仅供参考学习警 示中山大学授予学士学位工作细则第六条考试作弊不授予学士学位计算机科学系 2008上学期数据结构与算法期末考试试题( A )任课教师： 考试形式：闭卷 考试时间： 小时年级：07 班别： 专业： 姓名： _ 学号： _成绩 一 （分）标准模板库提供了数据结构vector和list. 请回答下列问题： 它们的逻辑结构和存储结构分别是什么？答：vector和list的逻辑结构均是线性结构，存储结构分别是连续的和链式的。Vector和list是线性表的两种不同实现。 这两种数据结构各有什么特点，或者更适用于什么样的场合？答：vector是一种随机存取结构，插入和删除平均需
2、要移动一半的元素；list是顺序存取结构，插入和删除只需要修改指针。或者答：vector适用于元素个数已知，需要随机存取，但是，插入和删除不多的场合。List适用于元素个数未知，随机存取不重要，但是，插入和删除频繁的场合。二 （分）回答下列问题： 将下列函数按照增长顺序（由慢到快）排列2n, 10n2, 100n, log n, log n3, e10, 15n+100log n, n!答：e10, log n, log n3, 15n +100log n, 100n, 10n2, 2n, n! 有些同学把2n与n!的增长顺序搞反了。有同学把整个顺序颠倒了。注意题目要求。我们做程序的人皆不可不
3、顾客户的要求，否则，饭碗就被自己砸掉了！ 说明下列函数的时间复杂度和空间复杂度（包含过程）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).三 （分）回答快速排序的有关问题。假定选择最左元素作为支点。 快速排序是不是稳定的？为什么？（举例或者给出证明）答：不稳定。如，输入1,2,1, 第一次划分后：1，1，2， 也是排序结果，两个1的前
4、后次序已经改变。有同学答“稳定”，不知道从哪里学来的。举例通常找最简单的例子。 快速排序在什么条件下最坏情况发生？试分析最坏情况复杂度。答：当输入已经有序，划分结果前半部分为空，后半部分有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) = n log n + 2log nT(n/2log n) = nlog n + n = O(
5、nlog n).四 （分）假设N(h)表示高度为h的AVL树的最少结点数。假定单根树的高度为。 试给出N(0), N(1), N(2), N(3)的值。答： N（0）=1,N(1)=2, N(2)=4, N(3) = 7 给出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树，试画出每次插入结束后的状态。答：略五 （分）回答下列问题： 二分查找平均时间复杂度是什么？使用二分查找算法的前提条件是什么？实现二分查找应该使用什么数据结构或者存储结构？答：二分查找
6、平均时间复杂度O(log n). 前提是查找记录按照关键字有序。实现二分查找应该用顺序结构存储。 与二分查找相比较，使用二叉查找树进行查找有什么特点？答：二分查找的平均时间性能也是O(log n), 但是插入和删除不需要移动元素，适合于动态查找。 假定hash函数为h(k)=k%13，表长为13。.试画出使用平方探查法依次插入15,16,32,67,55,28的hash表，并计算查找76和67的探查次数。答：hash table 略。查找76和67的探查次数分别是2和4。六 （分）对于图回答下列问题： 画出图的邻接表示意图答： 拓扑排序的一种方法是排其前驱结点已经全部排序的结点。试给出图的拓扑
7、排序，假定用一个队列存储当前可排序的结点。假定初始堆包含0，4，其中0是队首。答：0 4 1 6 5 8 9 7 3 2 请写出拓扑排序算法，并在尾部加上一段代码说明图是否存在圈。假定数组indgree表示排序过程中各结点的前驱数目。答：template void Digraph:breadth_sort(List &topological_order)/*Post: The vertices of the Digraph are arranged into the List topological_order which is found with a breadth-first trave
8、rsal of those vertices that do not belong to a cycle.Uses: Methods of classes Queue and List.*/ /代码略。参考课本。 /用sorted表示已排序结点数 If (sortedgraph.size) Cout “There must be a cycle” Else Cout “There is no cycle” 图1（六题图） 图2（七题图）七 （15分）回答下列问题： 假定图G是二叉树。二叉树的哪种遍历序对应图G从根结点开始的深度优先遍历？答：二叉树的先根次序对应深度优先遍历。 给出下列深度优先遍
9、历算法，请写出对图2 调用dfs(G,D)的结点遍历顺序（参照下图的邻接表）。答：DGHEIBACF 请说明，如何修改以上算法使之实现宽度优先遍历。Boolean visitedV.sizeDfs(graph G, vertex x)for each vertex u in V visitedu=false;list L = 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
10、each w in Adjv if (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,2,3,4,5,6,7,8,9,10的最小最大堆。答：（可以是其它形式的） 试问如何求最小最大堆的最小关键字结点和最大关键字结点？ 答：最小关键字在根结点。最大关键字是根结点的最大子结点（如果有子结点）。 试实现删除最小最大堆的最小关键字结点运算delMin(结果仍然保持最小最大堆. 可以用伪代码)。答：delMin可以通过删除最后一个结点x，将 x插入到根结点，然后从上到下调整。首先在min层构成的堆上自上而下调整一层，然后与比较x所在的min层的父结点比较，并做相应调整，一直调整至叶结点。 按照你的算法，画出依次输出前三个最小元素后的最小最大堆。答：总的来说，题目都是讲过的，或者做过的，最后一个例外。4
