2. 考研
  3. 设某赫夫曼树的高度为5，若已对两个字符编码为1和01，则最多还可以对( )个字符编码。

设某赫夫曼树的高度为5，若已对两个字符编码为1和01，则最多还可以对( )个字符编码。

admin2021-08-17  49
问题 设某赫夫曼树的高度为5，若已对两个字符编码为1和01，则最多还可以对(    )个字符编码。
选项 A、3
B、4
C、5
D、6
答案B
解析 首先，赫夫曼编码遵循的原则为：一个编码不能是任何其他编码的前缀。比如1和10就不行，因为1是10的前缀。既然1和01已经使用了，所以1和01开头的码字不能再使用。又由于赫夫曼树的高度为5，故赫夫曼编码的长度不能超过4，只剩下0000、0001、0010、O011等4种编码（这种编码方式可得到最多），故选B选项。
注意：本题选的是最多还可以对多少个字符编码，所以不能选取001、000等编码。例如选取001，就意味着0010和0011不能使用，这样可编码的字符就少了1个。
总结：
(1)有n个叶子结点的赫夫曼树的结点总数为2n—1。
(2)高度为h的赫夫曼树中，至少有2h—1个结点，至多有2h—l个结点。
(3)赫夫曼树中一定没有度为1的结点。
(4)赫夫曼树中两个权值最小的结点一定是兄弟结点。
(5)树中任一非叶子结点的权值一定不小于下一层任一结点的权值。
补充例题：一棵赫夫曼树共有215个结点，对其进行赫夫曼编码，共能得到多少个码字？
解析：求多少个码字就是求有多少个叶结点，从(1)可以得到，叶结点的个数为108个，故可以得到108个码字。
转载请注明原文地址:https://kaotiyun.com/show/ZP3i777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)