题目

1、由树转换成二叉树，其根的右孩子指针总是空的。（ ）

2、画出下列二叉树对应的森林。

3、设森林 F 对应的二叉树为 B，它有 m 个结点，B 的根为 P，P 的右子树的结点个数为 n，森林 F 中第一棵树的结点的个数是（ ）。
A. m - n
B. m - n - 1
C. n + 1
D. 不能确定

4、下列存储形式中，（ ）不是树的存储形式。
A. 双亲表示法
B. 孩子链表表示法
C. 孩子兄弟表示法
D. 顺序存储表示法

5、如果 F 是由有序树 T 转换而来的二叉树，那么 T 中结点的后根序列就是 F 中结点的（ ）序列。
A. 前序
B. 中序
C. 后序
D. 层次

6、假设一棵二叉树的层次序列（按层次递增顺序排列，同一层次自左向右）为 ABECFGDHI，中序序列为 BCDAFEHIG。请画出该二叉树，并将其转换成对应的森林。

7、设用于通信的电文仅由 7 个字母 a, b, c, d, e, f, g 组成，字母在电文中出现的频率分别是 0.07, 0.19, 0.06, 0.34, 0.03, 0.21, 0.10
（1）请为这 7 个字母构建 Huffman 树，写出每个字母的 Huffman 编码。
（2）求该哈夫曼树的带权路径长度 WPL。（要求左子树根结点的权小于等于右子树根结点的权）

8、依次输入一个关键字序列{60, 27, 76, 66, 80, 22, 70, 62}。
（1）按输入次序构造并画出此二叉排序树；
（2）画出该树在删除关键字 “76” 后的二叉排序树。

9、如下图所示是一棵二叉排序树，现对它做如下插入和删除操作。

（1）插入 2；
（2）删除 13；
（3）插入 34；
（4）插入 26；
（5）删除 4；
（6）删除 8；

答案

1、正确

2、

3、A

4、D

5、B

6、

7、（1）将频率乘以 100，得到 7, 19, 6, 34, 3, 21, 10

a 对应的哈夫曼编码为 1010；
b 对应的哈夫曼编码为 00；
c 对应的哈夫曼编码为 10111；
d 对应的哈夫曼编码为 11；
e 对应的哈夫曼编码为 10110；
f 对应的哈夫曼编码为 01；
c 对应的哈夫曼编码为 100；

（2）WPL = 19×2 + 21×2 + 10×3 + 7×4 + 3×5 + 6×5 + 34×2 = 251

8、（1）

（2）

9、（1）

（2）

（3）

（4）

（5）

（6）