《数据结构课程各章的重点及要点》由会员分享，可在线阅读，更多相关《数据结构课程各章的重点及要点（3页珍藏版）》请在金锄头文库上搜索。
1、1数据结构作业三数据结构作业三第六章 树与森林一、主教材中的习题6-14 判断以下序列是否是最小堆? 如果不是, 将它调整为最小堆。(1) 100, 86, 48, 73, 35, 39, 42, 57, 66, 21 (2) 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 (3) 103, 97, 56, 38, 66, 23, 42, 12, 30, 52, 06, 20 (4) 05, 56, 20, 23, 40, 38, 29, 61, 35, 76, 28, 100 6-16 在森林的二叉树表示中，用 llink 存储指向结点第一个子女的指针，用 rl
2、ink存储指向结点下一个兄弟的指针，用 data 存储结点的值。如果我们采用静态二叉链表作为森林的存储表示，同时按森林的先根次序依次安放森林的所有结点，则可以在它们的结点中用只有一个二进位的标志 ltag 代替 llink，用 rtag 代替 rlink。并设定若 ltag = 0，则该结点没有子女，若 ltag 0，则该结点有子女；若 rtag = 0，则该结点没有下一个兄弟，若 rtag 0，则该结点有下一个兄弟。试给出这种表示的结构定义，并设计一个算法，将用这种表示存储的森林转换成用 llink - rlink 表示的森林。6-18 已知一棵二叉树的前序遍历的结果是 ABECDFGHIJ
3、, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树。6-19 已知一棵树的先根次序遍历的结果与其对应二叉树表示(长子-兄弟表示)的前序遍历结果相同, 树的后根次序遍历结果与其对应二叉树表示的中序遍历结果相同。试问利用树的先根次序遍历结果和后根次序遍历结果能否唯一确定一棵树? 举例说明。6-21 假定用于通信的电文仅由 8 个字母 c1, c2, c3, c4, c5, c6, c7, c8 组成, 各字母在电文中出现的频率分别为 5, 25, 3, 6, 10, 11, 36, 4。试为这 8 个字母设计不等长 Huffman 编码, 并给出该电文的总码数。第七章 集合与搜索一、主教
4、材中的习题7-2 试编写一个算法，打印一个有穷集合中的所有成员。要求使用集合抽象数据类型中的基本操作。如果集合中包含有子集合，各个子集合之间没有重复的元素，采用什么结构比较合适。7-7 设有序顺序表中的元素依次为 017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的判定树, 并计算搜索成功的平均搜索长度和搜2索不成功的平均搜索长度。7-8 若对有 n 个元素的有序顺序表和无序顺序表进行顺序搜索, 试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同?(1) 搜索失败;(2)
5、 搜索成功, 且表中只有一个关键码等于给定值 k 的对象;(3) 搜索成功, 且表中有若干个关键码等于给定值 k 的对象, 要求一次搜索找出所有对象。7-15在二叉搜索树上删除一个有两个子女的结点时，可以采用以下三种方法：(1) 用左子树 TL 上具有最大关键码的结点 X 顶替，再递归地删除 X。 (2) 交替地用左子树 TL 上具有最大关键码的结点和右子树 TR 上具有最小关键码的结点顶替，再递归地删除适当的结点。(3) 用左子树 TL 上具有最大关键码的结点或者用右子树 TR 上具有最小关键码的结点顶替，再递归地删除适当的结点。可随机选择其中一个方案。试编写程序实现这三个删除方法，并用实例
6、说明哪一个方法最易于达到平衡化。7-18 将关键码 DEC, FEB, NOV, OCT, JUL, SEP, AUG, APR, MAR, MAY, JUN, JAN 按字母顺序依次插入到一棵初始为空的 AVL 树中，画出每插入一个关键码后的 AVL 树，并标明平衡旋转的类型。7-19 从第 7-18 题所建立的 AVL 树中删除关键码 MAY，为保持 AVL 树的特性，应如何进行删除和调整? 若接着删除关键码 FEB，又应如何删除与调整?第八章 图一、主教材中的习题8-8 对于如右图所示的有向图，试写出：(1) 从顶点出发进行深度优先搜索所得到的深度优先生成树；(2) 从顶点出发进行广度优先搜索所得到的广度优先生成树； 8-11 右图是一个连通图，请画出3(1) 以顶点为根的深度优先生成树；(2) 如果有关节点，请找出所有的关节点。(3) 如果想把该连通图变成重连通图，至少在图中加几条边？如何加？8-15 以右图为例，按 Dijkstra 算法计算得到的从顶点到其它各个顶点的最短路径和最短路径长度。
