判断题
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.
3.哈夫曼编码是一种最优的前缀码。对一个给定的字符集及其字符频率,其哈夫曼编码不一定是唯一的,但是每个字符的哈夫曼码的长度一定是唯一的。
选择题
1.对N(N≥2)个权值均不相同的字符构造哈夫曼树。下列关于该哈夫曼树的叙述中,错误的是:
B.树中两个权值最小的结点一定是兄弟结点
C.树中任一非叶结点的权值一定不小于下一层任一结点的权值
D.该树一定是一棵完全二叉树
2.由分别带权为9、2、5、7的四个叶子结点构成一棵哈夫曼树,该树的带权路径长度为:
B.37
C.44
D.46
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?
B.2
C.4
D.5
4.哈夫曼树是n个带权叶子结点构成的所有二叉树中()最小的二叉树。
B.高度
C.带权路径长度
D.度
5.关于Huffamn树,如下说法错误的是( )
B.Huffman树中,任意调整结点左右孩子的顺序,不影响带权路径长度
C.Huffamn树的带权路径长度最大
D.Huffman树中,权值越大的叶子结点离根结点越近
6.设给定权值总数有n 个,其哈夫曼树的结点总数为( )。
B.2n+1
C.2n-1
D.不确定
7.设哈夫曼树中有199个结点,则该哈夫曼树中有()个叶子结点。
B.100
C.101
D.102
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?
B.00, 100, 110, 000, 0010, 01
C.10, 1011, 11, 0011, 00, 010
D.0011, 10, 11, 0010, 01, 000
9.设有13个值,用它们构成一棵哈夫曼树,则该哈夫曼树共有结点数是( )。
B.12
C.26
D.25
10.以下关于huffman树说法错误的是( )。
B.huffman树中没有度数为1的分支结点
C.若初始森林中共有n棵二叉树,最终求得的huffman树共有2n-1个结点
D.若初始森林中共有n棵二叉树,进行2n-1次合并后才能剩下一棵最终的huffman树
11.设一段文本中包含4个对象{a,b,c,d},其出现次数相应为{4,2,5,1},则该段文本的哈夫曼编码比采用等长方式的编码节省了多少位数?
B.2
C.4
D.5
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:
B.37
C.44
D.46
13.根据使用频率为5个字符设计的哈夫曼编码不可能是( )。
B.000,001,010,011,1
C.100,11,10,1,0
D.001,000,01,11,10
14.已知权值集合为{5,7,2,3,6,1,4},计算带权路径长度WPL()。
B.74
C.75
D.76
15.对 n 个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有 115 个结点,则 n 的值是:
B.57
C.58
D.60