试题-已知一段文本有1382个字符，使用了1382个字节进行存储，这段文本全部是由a、b、c、d、e这5个字符组成，a出现了354次，b出现了48

题目

已知一段文本有1382个字符，使用了1382个字节进行存储，这段文本全部是由a、b、c、d、e这5个字符组成，a出现了354次，b出现了483次，c出现了227次，d出现了96次，e出现了232次，对这5个字符使用哈夫曼（Huffman）算法进行编码，则以下哪些说法正确（）

A.使用哈夫曼算法编码后，用编码值来存储这段文本将花费最少的存储空间

B.使用哈夫曼算法进行编码，a、b、c、d、e这5个字符对应的编码值是唯一确定的

C.使用哈夫曼算法进行编码，a、b、c、d、e这5个字符对应的编码值可以有多套，但每个字符编码的位（bit）数是确定的

D.b这个字符的哈夫曼编码值位数应该最短，d这个字符的哈夫曼编码值位数应该最长

上一题 下一题

解答

正确答案是 A C D

A正确，Huffman树就是求最优解。可以有多套方案，但最终每套方案生成的编码长度都相同且都是最优解。

B错误，我们可以将左子树定为1右子树定为0也可以反之，不同的方案获得的编码值是不同的，但每个字符的编码长度是固定的。

C正确，不同的方案影响的只是通向节点的路径为0还是1，而不会影响Huffman树的层次结构

D正确，生成了Huffman树之后，我们就能看到，出现频率越高的节点越靠近根，深度越小即编码值尾数越短；出现频率越低的节点越远离根，深度越大即编码位数越长。

C 9条回复评论

博客园

怎么没能早点看到你这篇文章呢

发表于 2022-05-08 22:00:00

0 0

老干妈拌面

B和D？就大神指点

发表于 2018-10-13 12:00:35

0 0

小洁癖

霍夫曼编码是，电文总长最短的二进制前缀编码。

发表于 2018-10-13 12:00:26

0 0

柠檬很甜

其实D看漏了。很简单，1382个字符占用1382个字节，每个字符占一个字节存储，出现次数最多的，先用内存字节数也最多，因此，根据哈夫曼的数学原理，即树的带权路径和最小，编码最优。因此离树根最近的，必然应该编码它占用位数最少。

发表于 2018-10-13 12:00:20

0 0

米米大户

Huffman树就是求最优解。可以有多套方案，但最终每套方案生成的编码长度都相同且都是最优解

发表于 2018-10-13 12:00:06

0 0

米米大户

感觉A说的不是很严谨，最优解只是对于Huffman编码的储存来讲，但别的压缩方法会比Huffman压缩更小，感觉有点不对

发表于 2018-10-13 11:59:56

0 0

寒山远火

关于D选项，从哈夫曼编码思想的角度，频率最高的编码就应该最短，频率最低的编码就应该最长，选项中说的是“应该”，提出的是要求，而实际是不是有和它一样长的，只有编码之后才知道，有也并不违背这个要求，所以D没毛病

发表于 2018-10-13 11:59:48

0 0

资深90后

A为啥要选？难道直接用字符储存不如编码节约空间？

发表于 2018-10-13 11:59:39

0 0

一零计划

哈夫曼编码采用变长编码对源符号进行编码，变长编码表根据源符号出现概率得到，源符号出现概率越大，对应编码越短，反之越长。这样得到的编码平均长度和期望值最小，可以压缩存储。使用哈夫曼编码这几个字符对应的编码值不唯一，但是它们所占的编码位数唯一。所以答案为ACD

发表于 2018-10-13 11:59:33

0 0

问题信息

分类：数据结构 - 赫夫曼树

难度:

最新校招难题刷题，快来进刷题群吧