内容发布更新时间 : 2024/11/8 14:04:30星期一 下面是文章的全部内容请认真阅读。

① 请分别用双亲表示法、孩子表示法、孩子兄弟表示法给出该树的存储结构。 ② 请给出该树的先序遍历序列和后序遍历序列。 ③ 请将这棵树转换成二叉树。

⑽ 设给定权值集合w={3,5,7,8,11,12} ，请构造关于w的一棵huffman树，并求其加权路径长度WPL 。

⑾ 假设用于通信的电文是由字符集{a, b, c, d, e, f, g, h}中的字符构成， 这8个字符在电文中出现的概率分别为{0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10} 。

① 请画出对应的huffman树(按左子树根结点的权小于等于右子树根结点的权的次序构造)。 ② 求出每个字符的huffman编码

习 题 七

⑴ 分析并回答下列问题：

① 图中顶点的度之和与边数之和的关系?

② 有向图中顶点的入度之和与出度之和的关系?

③ 具有n个顶点的无向图，至少应有多少条边才能确保是一个连通图? 若采用邻接矩阵表示，则该矩阵的大小是多少?

④ 具有n个顶点的有向图，至少应有多少条弧才能确保是强连通图的? 为什么? ⑵ 设一有向图G=(V,E)，其中V={a,b,c,d,e} ， E={, , , , , ,, , }

① 请画出该有向图，并求各顶点的入度和出度。 ② 分别画出有向图的正邻接链表和逆邻接链表。 ⑶ 对图7-27所示的带权无向图。 ① 写出相应的邻接矩阵表示。 ② 写出相应的边表表示。 ③ 求出各顶点的度。

⑷ 已知有向图的逆邻接链表如图7-28所示。

① 画出该有向图。

② 写出相应的邻接矩阵表示。

③ 写出从顶点a开始的深度优先和广度优先遍历序列。 ④ 画出从顶点a开始的深度优先和广度优先生成树。

⑸ 一个带权连通图的最小生成树是否唯一?在什么情况下可能不唯一? ⑹ 对于图7-27所示的带权无向图。

① 按照Prime算法给出从顶点2开始构造最小生成树的过程。 ② 按照Kruskal算法给出最小生成树的过程。 ⑺ 已知带权有向图如图7-29所示，请利用Dijkstra算法从顶点V4出发到其余顶点的最短路径及长度，给出相应的求解步骤。

⑻ 已知带权有向图如图7-30所示，请利用Floyd算法求出每对顶点之间的最短路径及路径长度。

⑼ 一个AOV网用邻接矩阵表示，如图7-31。用拓扑排序求该AOV网的一个拓扑序列，给出相应的步骤。

⑽ 拓扑排序的结果不是唯一的，请给出如图7-32所示的有向图的所有可能的拓扑序列。 ⑾ 请在深度优先搜索算法的基础上设计一个对有向无环图进行拓扑排序的算法。

⑿ 设计一个算法利用图的遍历方法输出一个无向图G中从顶点Vi到Vj的长度为S的简单路径，设图采用邻接链表作为存储结构。

⒀ 假设一个工程的进度计划用AOE网表示，如图7-33所示。 ① 求出每个事件的最早发生时间和最晚发生时间。 ② 该工程完工至少需要多少时间? ③ 求出所有关键路径和关键活动。

习 题 九

⑴ 对于一个有n个元素的线性表，若采用顺序查找方法时的平均查找长度是什么？若结点是有序的，则采用折半查找法是的平均查找长度是什么?

⑵ 设查找表采用单链表存储，请分别写出对该表进行顺序查找的静态查找和动态查找的算法。

⑶ 设二叉排序树中的关键字互不相同：则

① 最小元素无左孩子，最大元素无右孩子，此命题是否正确？ ② 最大和最小元素一定是叶子结点吗？ ③ 一个新结点总是插入在叶子结点上吗？

⑷ 试比较哈希表构造时几种冲突处理方法的优点和缺点。

⑸ 将关键字序列(10, 2, 26, 4, 18, 24, 21, 15, 8, 23, 5, 12, 14)依次插入到初态为空的二叉排序树中，请画出所得到的树T； 然后画出删除10之后的二叉排序树T1 ； 若再将10插入到T1中得到的二叉排序树T2是否与T1相同? 请给出T2的先序、中序和后序序列。

⑹ 设有关键字序列为：(Dec, Feb, Nov, Oct, June, Sept, Aug, Apr, May, July, Jan, Mar) ，请手工构造一棵二叉排序树。该树是平衡二叉排序树? 若不是，请为其构造一棵平衡二叉排序树。 ⑺ 设关键字序列是(19, 14, 23, 01, 68, 84, 27, 55, 11, 34, 79)，散列表长度是11，散列函数是H(key)=key MOD 11，

① 采用开放地址法的线性探测方法解决冲突，请构造该关键字序列的哈希表。 ② 采用开放地址法的二次探测方法解决冲突，请构造该关键字序列的哈希表。 ⑻ 试比较线性索引和树形索引的优点和缺点。

⑼ 设关键字序列是(19, 24, 23, 17, 38, 04, 27, 51, 31, 34, 69)，散列表长度是11，散列函数是H(key)=key MOD 11，

① 采用开放地址法的线性探测方法解决冲突，请构造该关键字序列的哈希表。 ② 求出在等概率情况下，该方法的查找成功和不成功的平均查找长度ASL。 ⑽ 下图是一棵3阶B_树，请画出插入关键字B,L,P,Q后的树形。

习 题 十

⑴ 回答下列各题：

① 从未排序序列中挑选元素，并将其依次放入到已排序序列中(初始时为空)的一端的方法是什么？

② 在待排序的元素基本有序的前提下，效率最高的排序方法是什么?

③ 从未排序序列中依次取出元素与已排序序列 (初始时为空)中的元素进行比较，将其放入已排序序列的正确位置方法是什么？

④ 设有1000个元素， 希望采用最快的速度挑选出其中前10个最大的元素， 最好的方法是什么?

⑵ 若对关键字序列为(54, 37, 93, 25, 17, 68, 58, 41, 76)的一组记录进行快速排序时，递归调用使用的栈所能到达的最大深度是多少?共需递归调用多少次?其中第二次递归调用是对哪组记录进行排序?

⑶ 在堆排序，快速排序和归并排序中，若只从存储空间考虑，应选择哪种方法；若只从排序结果的稳定性考虑，应选择哪种方法；若只从平均情况下排序最快考虑，应选择哪种方法； ⑷ 设有关键字序列为(14, 17, 53, 35, 9, 32, 68, 41, 76, 23)的一组记录，请给出用希尔排序法(增量序列是5, 3, 1)排序时的每一躺结果。

⑸ 设有关键字序列为(14, 17, 53, 35, 9, 37, 68, 21, 46)的一组记录，请给出冒泡排序法排序时的每一躺结果。

⑹ 设有关键字序列为(14, 17, 53, 35, 9, 37, 68, 21, 46)的一组记录，利用快速排序法进行排序时，请给出以第一个记录为基准得到的一次划分结果。 ⑺ 设关键字序列为(14, 17, 53, 35, 9, 37, 68, 21)的一组记录，请给出按非递增采用堆排序时的每一躺结果。

⑻ 设关键字序列为(314, 617, 253, 335, 19, 237, 464, 121, 46, 231, 176, 344)的一组记录，请给出采用基数排序时的每一躺结果。

⑼ 将哨兵放在R[n]中，被排序的记录存放在R[1…n-1]中，重写直接插入排序算法。

⑽ 实际中常采用单链表存储数据记录，请写出排序记录的结构的定义并修改。