发布时间 : 星期四 文章数据结构复习题汇总更新完毕开始阅读63b051366d175f0e7cd184254b35eefdc8d31534
6.图G各顶点的连接关系及相应权值如下图所示。 （1）画出图的邻接表存储图示
（2）从顶点1开始对图进行广度优先遍历，写出遍历结果； （3）使用Kruskal算法求该图的最小生成树，给出的形成过程。（11分）
5 5 1 3
2 6 6 3 7 4
2 4
6 7.设Hash函数为H(K)=K mod 7，哈希表的地址空间为0，．．．，6，开始时哈希
表为空，用平方探测法解决冲突，请画出依次插入键值9，14，10，56，30后的哈希表。
8. 在双循环链表中，写出在指针P所指结点之前插入指针S所指结点的执行语句序列；结点定义如下： struct Node{ char data; Node *next; Node *back; }；
9. 设右图为某树的二叉树表示，请画出该树。
10. 简要说明快速排序的排序思想, 并给出算法时间复杂度。根
据所给序列（49，38，65，97，76，13，27，50），设选第一个元素为支点/参考值（pivot），写出快速排序的第一趟排序的结果。
解答：先选一个轴值（即比较的基准），通过一趟排序将待排序记录分割成独立的两部分，前一部分记录的关键码均小于或等于轴值，后一部分记录的关键码均大于或等于轴值，然后分别对这两部分重复上述方法，直到整个序列有序。 11. 运用堆排序（Heapsort）方法，设初始序列为（46，88，45，39，70，58，101，10，66，34），若按教材上的算法建初始堆，画出初始堆的树状图。 12. 设Hash函数为H(K)=K mod 7，哈希表的地址空间为0，．．．，6，开始时哈希表为空，用线性探测法解决冲突，请画出依次插入键值23，14，9，6，30，12，18后的哈希表。
13.图G各顶点的连接关系及相应权值如右图所示。（1）画出该图的邻接距阵；（2）并从顶点0开始对图进行广度优先遍历，写出遍历结果；（3）使用Prim
算法求该图的最小生成树，画出其生成过程。
14. 如图所示为一有向图，试求：
50V4V42040V3V32010V5V520401010V2V220V0V030V1V1 在邻接矩阵和(逆)邻接表存储结构下利用深度和广度优先算法遍历序列。
15. 求出如图所示的AOE网中所有关键路径，请写出事件的最早发生时间和最晚发生时间、活动的最早开始时间和最晚开始时间，以及求得的关键路径（10分）。
a0?31a2?73a5?7a6?65a10?10a9?20a1?4a3?5a7?47a11?62V0 0 0 a4?34V2 4 5 V3 15 15 a8?86V5 21 23 V6 19 19 答案： 事件 最早发生时间 最晚发生时间 活动 V7 25 25 V1 3 3 V4 8 8 a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 最早开始时间 最晚开始时间 差值 是否关键活动 0 0 0 是 0 1 1 3 8 5 3 3 0 是 4 5 1 8 8 0 是 15 17 2 15 15 0 是 8 11 3 21 23 2 15 15 0 是 19 19 0 是 关键路径有两条：a0a3a5a7a11和a0a3a5a10
16. 已知一组关键字为｛25，18，46，2，53，39，32，4，74，67，60，11｝，按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
答案：由已知关键字组进行构造时，是从空二叉排序树开始依次选取关键字通过查找和插入而生成出二叉排序树。二叉排序树的生成过程如下图：
2525181825462518463941132675374...260关键字25查找成功时比较1次，关键字18，46查找成功时各比较2次，关键字4，39，53查找成功时各比较3次，关键字11，32，74查找成功时各比较4次，关键字11，67查找成功时各比较5次，关键字60查找成功时比较6次，则： ASL=（1*1+2*2+3*3+3*4+2*5+1*6）/12=42/12=3.5
17. 简要说明快速排序的排序思想. 根据所给序列（49，38，65，97，76，13，27，50），设选第一个元素为支点/参考值（pivot），写出快速排序的第一趟排序的结果。
Solution:
18. 图G各顶点的连接关系及相应权值如右图所示。（1）画出该图的邻接距阵；（2）并从顶点0开始对图进行广度深度优先遍历，写出遍历结果；（3）使
用Prim, Kruskal算法求该图的最小生成树，画出其生成过程。
1 0 1 3 4 4 2 b 2
19. 在什么样的情况下，等长编码是最优的前缀码?
在每个字符的使用概率相同的情况下，也即在哈夫曼树中每片叶子的权重相等的时候，等长编码是最优的前缀码。
19.设右图为某树的二叉树表示，请画出该树。（或者树到二叉树的题）
20.假设用于通信的电文由字符集{A, B, C, D, R} 解 中的字母构成，这5个字母在电文中出现的频率 依次为{40, 20, 10, 10, 20 }。请画出对应的 编码哈夫曼树（Huffman）； 求出每个字符的哈夫曼编码。
Prim算法求该图的最小生成树