严蔚敏版数据结构参考答案

C．X的左子树中最右结点 D．X的左子树中最右叶结点 答案：C

（13）引入二叉线索树的目的是（ ）。

A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除

C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 答案：A

（14）设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。

A．n?1 答案：C

（15）n（n≥2）个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（ ）。 A．该树一定是一棵完全二叉树 B．树中一定没有度为1的结点

C．树中两个权值最小的结点一定是兄弟结点

D．树中任一非叶结点的权值一定不小于下一层任一结点的权值 答案：A

解释：哈夫曼树的构造过程是每次都选取权值最小的树作为左右子树构造一棵新的二叉树，所以树中一定没有度为1的结点、两个权值最小的结点一定是兄弟结点、任一非叶结点的权值一定不小于下一层任一结点的权值。

2．应用题

（1）试找出满足下列条件的二叉树

① 先序序列与后序序列相同 ②中序序列与后序序列相同 ③ 先序序列与中序序列相同 ④中序序列与层次遍历序列相同

答案：先序遍历二叉树的顺序是“根—左子树—右子树”，中序遍历“左子树—根—右

子树”，后序遍历顺序是：“左子树—右子树―根＂，根据以上原则有

① 或为空树，或为只有根结点的二叉树

② 或为空树，或为任一结点至多只有左子树的二叉树． ③ 或为空树，或为任一结点至多只有右子树的二叉树． ④ 或为空树，或为任一结点至多只有右子树的二叉树

（2）设一棵二叉树的先序序列： A B D F C E G H ，中序序列： B F D A G E H C ①画出这棵二叉树。

②画出这棵二叉树的后序线索树。

③将这棵二叉树转换成对应的树（或森林）。 答案：

35

B．n C．n + 1 D．n + 2

A ABCB A

D

E C

H B D F

CEnullFDEF G GHGH③

① ②

（3） 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。

① 试为这8个字母设计赫夫曼编码。

② 试设计另一种由二进制表示的等长编码方案。 ③ 对于上述实例，比较两种方案的优缺点。 答案：方案1；哈夫曼编码

先将概率放大100倍，以方便构造哈夫曼树。

w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6], (7,10)】, ??19, 21, 32

（100）

（40） （60）

19 21 32 （28）

（17） （11）

7 10 6 （5） 2 3

0 1 0 1 0 1 19 21 32 0 1 0 1 0 1 7 10 6 0 1 36

2 3

方案比较： 字 母编号 1 2 3 4 5 6 方案1的WPL＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61 方案2的WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 结论：哈夫曼编码优于等长二进制编码

（4）已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT的存储结构的初态和终态。

答案： 初态:

1 2 3 4 5 6 7 8 9 10 11 12 13 weight 3 12 7 4 2 8 11 parent 0 0 0 0 0 0 0 0 0 0 0 0 0 lchild 0 0 0 0 0 0 0 0 0 0 0 0 0 rchild 0 0 0 0 0 0 0 0 0 0 0 0 0

7 8 对应编码 1100 00 11110 1110 10 11111 01 1101 出现频率 0.07 0.19 0.02 0.06 0.32 0.03 0.21 0.10 字母编号 1 2 3 4 5 6 7 8 对应编码 000 001 010 011 100 101 110 111 出现频率 0.07 0.19 0.02 0.06 0.32 0.03 0.21 0.10 37

终态：

1 2 3 4 5 6 7 8 9 10 11 12 13

3．算法设计题

以二叉链表作为二叉树的存储结构，编写以下算法： （1）统计二叉树的叶结点个数。

[题目分析]如果二叉树为空，返回0，如果二叉树不为空且左右子树为空，返回1，如果二叉树不为空，且左右子树不同时为空，返回左子树中叶子节点个数加上右子树中叶子节点个数。 [算法描述]

int LeafNodeCount(BiTree T) { }

（2）判别两棵树是否相等。

if(T==NULL)

return 0; //如果是空树，则叶子结点个数为0

return 1; //判断结点是否是叶子结点（左孩子右孩子都为空），若是则返回1 return LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild); else if(T->lchild==NULL&&T->rchild==NULL) else

weight 3 12 7 4 2 8 11 5 9 15 20 27 47 parent 8 12 10 9 8 10 11 9 11 12 13 13 0 lchild 0 0 0 0 0 0 0 5 4 3 9 2 11 rchild 0 0 0 0 0 0 0 1 8 6 7 10 12

38