✏️ 纠错
第 210 题 / 共 226 题
第 9 题 设有字符集 {a, b, c, d, e, f} ,其出现频率分别为{5, 9, 12, 13, 16, 45}。哈夫曼算法构造最优前缀编码,以下哪⼀组可能是对应的哈夫曼编码?(⾮叶子节点左边分支记作0,右边分支记作1,左右互换不影响正确性)。
📝 题目解析

答案:B

考纲知识点:数据结构(哈夫曼树与哈夫曼编码的构造)

详细解析:

哈夫曼编码构造原则:每次选频率最小的两个节点合并,父节点频率为两者之和,左分支记0、右分支记1(左右可互换,编码不唯一但长度最优)。

初始节点:5 (a)、9 (b)、12 (c)、13 (d)、16 (e)、45 (f);

第一次合并5+9=14,节点:12 (c)、13 (d)、14 (a,b)、16 (e)、45 (f);

第二次合并12+13=25,节点:14 (a,b)、16 (e)、25 (c,d)、45 (f);

第三次合并14+16=30,节点:25 (c,d)、30 (a,b,e)、45 (f);

第四次合并25+30=55,节点:45 (f)、55 (a,b,c,d,e);

第五次合并45+55=100,哈夫曼树完成。

编码结果(左0 右 1):

f (45):根→左,编码0;

e (16):根→右→右,编码111;

d (13):根→右→左→右,编码101;

c (12):根→右→左→左,编码100;

b (9):根→右→右→左→右,编码1101;

a (5):根→右→右→左→左,编码1100;

与选项B 完全匹配。