判断题

1.Given a Huffman tree for N (≥2) characters, all with different weights. The weight of any non-leaf node must be no less than the weight of any node on the next lower level.

哈夫曼树的根节点的权重为左右子节点的权重之和。

2.Let C be an alphabet in which each character c in C has frequency c.freq. If the size of C is n, the length of the optimal prefix code for any character c is not greater than n−1.

考虑哈夫曼树最不平衡的情况，设根结点为第0层，从第一层开始，到倒数第二层为止，都只有一个叶子结点，倒数第一层有2个叶子结点，整个树向一边倾倒。参考选择题第2题的图。即使是这种最不平衡的情况下，观察每一个字符的最优前缀码，最长也才是字符集个数减1。

3.哈夫曼编码是一种最优的前缀码。对一个给定的字符集及其字符频率，其哈夫曼编码不一定是唯一的，但是每个字符的哈夫曼码的长度一定是唯一的。

哈夫曼字符的频率相同时每个字符的码长不是确定的。

选择题

1.对N（N≥2）个权值均不相同的字符构造哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是：

哈夫曼树是不等长编码，饿如果是完全二叉树，那么就会是等长编码了。

2.由分别带权为9、2、5、7的四个叶子结点构成一棵哈夫曼树，该树的带权路径长度为：

根据图，计算带权路径长度，\(\color{red}{9+7\times2+2\times3+5\times3=44}\)

3.Given a piece of text which consists of characters {a, b, c, d}, with the frequencies of occurrence being {4, 2, 5, 1}, respectively. How many bits are saved by Huffman code comparing to the equal-length code?

设左结点为0，右结点为1。根据图得到编码：a(10),b(110),c(0),d(111)。\(\color{red}{2\times4+3\times2+5+3=22}\)位。而假如采用等长码，需要\(\color{red}{12\times2=24}\)位

4.哈夫曼树是n个带权叶子结点构成的所有二叉树中（）最小的二叉树。

5.关于Huffamn树，如下说法错误的是（ ）

6.设给定权值总数有n 个,其哈夫曼树的结点总数为（ ）。

哈夫曼树的叶结点个数为给定权值个数，而非叶结点为为叶结点个数减1。

7.设哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。

见第6题的分析。

8.Given a set of characters { a, b, c, d, e, f } with their occurrence frequencies being { 6, 3, 8, 2, 10, 4 }, respectively. Which of the following is a correct set of the corresponding Huffman codes?

关于这个问题，首先判断是否是前缀码，排除BC，然后计算分别采用A、D编码的带权路径长度为70和86。

9.设有13个值，用它们构成一棵哈夫曼树，则该哈夫曼树共有结点数是（ ）。

见第6题的分析。

10.以下关于huffman树说法错误的是（ ）。

其实这个问题的D选项就是变相在问合并之后最终的哈夫曼树有多少非叶子结点，这个可见第6题的分析。

11.设一段文本中包含4个对象{a,b,c,d}，其出现次数相应为{4,2,5,1}，则该段文本的哈夫曼编码比采用等长方式的编码节省了多少位数？

同第3题。

12.Construct a Huffman tree from four leaf nodes with weights 9, 2, 5 and 7. Then the weighted path length of this Huffman tree is:

同第2题。

13.根据使用频率为5个字符设计的哈夫曼编码不可能是（ ）。

直接看是否是前缀码。

14.已知权值集合为{5，7，2，3，6，1，4}，计算带权路径长度WPL（）。

如图，计算带权最短路径\(\color{red}{2\times7+3\times5+3\times4+2\times6+3\times3+4\times2+4=74}\)

15.对 n 个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有 115 个结点，则 n 的值是：

见第6题的分析。