第六章 树和二叉树作业 一、选择题（每题 2 分，共 24 分）。 1. 一棵二叉树的顺序存储情况如下： 树中，度为 2 的结点数为（ C ）。 A．1 B．2 C．3 D．4 2. 一棵“完全二叉树”结点数为 25，高度为（ B ）。 A．4 D．不确定 B．5 C．6 3．下列说法中，（ B ）是正确的。 A. 二叉树就是度为 2 的树 B. 二叉树中不存在度大于 2 的结点 C. 二叉树是有序树 D. 二叉树中每个结点的度均为 2 4.一棵二叉树的前序遍历序列为 ABCDEFG,它的中序遍历序列可能是（ B ）。 A. CABDEFG C. DACEFBG B. BCDAEFG D. ADBCFEG 5．线索二叉树中的线索指的是（ C ）。 A．左孩子 C.指针 B.遍历 D.标志 6. 建立线索二叉树的目的是（ A ）。 A. 方便查找某结点的前驱或后继 B. 方便二叉树的插入与删除 C. 方便查找某结点的双亲 D. 使二叉树的遍历结果唯一 7. 有 abc 三个结点的右单枝二叉树的顺序存储结构应该用（ D ）示意。 A. B. C. D. a a a a b b b ^ c ^ ^ b c ^ ^ c ^ ^ c 8. 一颗有 2046 个结点的完全二叉树的第 10 层上共有（ B ）个结点。 A. 511 D. 1024 1023 C. B. 512 9. 一棵完全二叉树一定是一棵（ A ）。 A. 平衡二叉树 B. 二叉排序树 

C. 堆 D. 哈夫曼树 10．某二叉树的中序遍历序列和后序遍历序列正好相反，则该二叉树一定是（ C ）的二叉 树。 A．空或只有一个结点 C．任一结点无左孩子 B．高度等于其结点数 D．任一结点无右孩子 11．一棵二叉树的顺序存储情况如下： 2 3 4 1 A B C D E 0 F 0 0 G 5 6 7 8 9 10 11 12 13 H 0 0 14 15 X 0 结点 D 的左孩子结点为（ D ）。 A．E B．C C．F D．没有 12．一棵“完全二叉树”结点数为 25，高度为（ B ）。 A．4 B．5 C．6 D．不确定 二、填空题（每空 3 分，共 18 分）。 1. 树的路径长度：是从树根到每个结点的路径长度之和。对结点数相同的树来说，路径长 度最短的是 完全 二叉树。 2. 在有 n 个叶子结点的哈夫曼树中，总结点数是 2n-1 。 3. 在有 n 个结点的二叉链表中，值为非空的链域的个数为 n-1 。 4. 某二叉树的中序遍历序列和后序遍历序列正好相反，则该二叉树一定是 左孩子 的二叉树。 任一结点无 5. 深度为 k 的二叉树最多有 2 1k  个结点，最少有 k 个结点。 三、综合题（共 58 分）。 1. 假定字符集{a，b，c，d，e，f }中的字符在电码中出现的次数如下： 字符 频度 a 9 b c d 12 20 23 e 15 f 5 构造一棵哈夫曼树（6 分），给出每个字符的哈夫曼编码（4 分），并计算哈夫曼树的加权 路径长度 WPL（2 分）。 （符合 WPL 最小 的均为哈夫曼树，答案不唯一） 哈夫曼编码: a:1110 b:10 c:00 d:10 e:01 f:1111 WPL=208 

2. 假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字符构成，它们在电文中出现的频率分别 为{0.31,0.16,0.10,0.08,0.11,0.20,0.04}。要求： (1)为这 7 个字符设计哈夫曼树（6 分）。 (2)据此哈夫曼树设计哈夫曼编码（4 分）。 (3)假设电文的长度为 100 字符，使用哈夫曼编码比使用 3 位二进制数等长编码使电文总长 压缩多少？（4 分） (1) 为这 7 个字符设计哈夫曼树为（符合 WPL 最小的均为哈夫曼树，答案不唯一）： (2) 哈夫曼编码为： a:01;b:001;c:100;d:0001;e:101;f:11;g:0000 (3) 假设电文的长度为 100 字符，使用哈夫曼编码比使用 3 位二进制数等长编码使电文总长 压缩多少？ 采用等长码，100 个字符需要 300 位二进制数，采用哈夫曼编码发送这 100 个字符需要 261 二进制位，压缩了 300-261=39 个字符。压缩比为 39/300=13%。 3. 二叉数 T 的（双亲到孩子的）边集为： { , , , , , } 请回答下列问题： （1）T 的根结点（2 分）： （2）T 的叶结点（2 分）： （3）T 的深度（2 分）： （4）如果上述列出边集中，某个结点只有一个孩子时，均为其左孩子；某个结点有两个孩 子时，则先列出了连接左孩子的边后列出了连接右孩子的边。画出该二叉树其及前序线索（6 分）。 (1)T 的根结点 ：D 

(2)T 的叶结点 ：B，C，G, (3)T 的深度 ：4 (4)该二叉树其及前序线索为： 4．现有以下按前序和中序遍历二叉树的结果： 前序：ABCEDFGHI 中序：CEBGFHDAI 画出该二叉树的逻辑结构图（5 分），并在图中加入中序线索（5 分）。 5．有电文：ABCDBCDCBDDBACBCCFCDBBBEBB。 用 Huffman 树构造电文中每一字符的最优通讯编码。画出构造的哈夫曼树，并给出每个字符 的哈夫曼编码方案。（符合 WPL 最小的 均为哈夫曼树，答案不唯一） （1）构造哈夫曼树（6 分）： （2）哈夫曼编码方案（4 分）： A：0001 E：00000 F：00001 B：1 C：01 D：001