CSP-J 2023 第一轮 第 10 题：构造哈夫曼编码

题目

假设有一组字符 {a,b,c,d,e,f}, 对应的频率分别为 $5\%,9\%,12\%,13\%,16\%,45\%$。请问以下哪个选项是字符abcdef分别对应的一组哈夫曼编码?

选项

• A. 1111,1110,101,100,110,0
• B. 1010,1001,1000,011,010,00
• C. 000,001,010,011,10,11
• D. 1010,1011,110,111,00,01

答案

A

题解

答案是 A。

哈夫曼编码的构造规则是：每次选出频率最小的两个节点合并，直到只剩一个节点。本题可以直接用百分数对应的数值计算：

得到下面的树。给每条分支标上 0 或 1，从根走到字符经过的标记就是它的编码：

``text 根 ├─0 → f 编码：0 └─1 ├─0 │ ├─0 → d 编码：100 │ └─1 → c 编码：101 └─1 ├─0 → e 编码：110 └─1 ├─0 → b 编码：1110 └─1 → a 编码：1111 ``

按 a、b、c、d、e、f 的顺序排列，就是：

``text 1111, 1110, 101, 100, 110, 0 ``

所以选 A。

注意：每个分叉的 0、1 可以互换，因此哈夫曼编码不唯一。本题也可以快速排除：最后一次合并的是 f(45) 和 其余字符组成的节点(55)，所以 f 的编码一定只有 1 位，四个选项中只有 A 符合。