已知字符集{a, b, c, d, e, f},若各字符出现的次数分别为6, 3, 8, 2, 10, 4,则对应字符集中各字符的哈夫曼编码可能是( )。
A. 00, 1011, 01, 1010, 11, 100
B. 00, 100, 110, 000, 0010, 01
C. 10, 1011, 11, 0011, 00, 010
D. 0011, 10, 11, 0010, 01, 000
方法一:构造
按照题目条件构...
用户登录可进行刷题及查看答案
按照题目条件构造哈夫曼树。
每次取最小的两个子树的根结点合并。过程如下图所示:
左指针标0,右指针标1,从根结点到叶结点的路径即为该字符的哈夫曼编码。
本题选A。
方法二:代入选项
从选项构造哈夫曼树,检查是否符合哈夫曼编码性质。
选项B中a的编码是d的编码的前缀,错误。
选项C中a的编码是b的编码的前缀,错误。
选项D构造出的哈夫曼树不符合WPL最小规则,错误。
但其实这样做可能更加麻烦,需要画出4棵哈夫曼树依次进行检查。
检查后只有A符合要求。
登录后提交答案
暂无评论,来抢沙发