GESP 六级 · GESP 202506 C++ 六级 第 9 题

第9题 设有字符集 $\{a, b, c, d, e\}$，其出现频率分别为 $\{5, 8, 12, 15, 20\}$，得到的哈夫曼编码为（ ）。

A.

a: 010
b: 011
c: 00
d: 10
e: 11

B.

a: 00
b: 10
c: 011
d: 100
e: 111

C.

a: 10
b: 01
c: 011
d: 100
e: 111

D.

a: 100
b: 01
c: 011
d: 100
e: 00

哈夫曼编码：每次合并权值最小的两个节点，构建最优二叉树，使带权路径长度（WPL）最小。用于数据压缩。

审题时注意题目要求（选正确还是选错误），避免因审题不清失分。涉及代码的题目要逐行分析变量变化。

【考点】哈夫曼编码｜优先队列｜贪心构造

🎯考纲定位 本题考查 GESP 六级「数据结构与算法」模块中的哈夫曼编码，属于树结构应用场景。命题人用“给定频次直接选编码”的题型，卡住的是考生是否真正理解“贪心构造”而非死记编码表。

🧠解题思维 按频次从小到大排序，反复合并两个最小节点，建立二叉树；左子树标 0、右子树标 1，从根向下读取路径即得编码。本题合并过程为：(a,b)→13，(c,13)→25，(d,e)→35，最后合并 25 与 35。由此得到 a:010, b:011, c:00, d:10, e:11，与选项 A 完全吻合。若计算总编码长度：5×3+8×3+12×2+15×2+20×2=120 位，验证了最优性。

🪤陷阱拆解 B 选项把高频字符 c 的编码拉长至 3 位，违背最优性；C 选项仅左右互换导致高频 e 获得更长码；D 选项出现重复前缀（a 与 d 同为 100，e 为 00 与 a 冲突），根本构不成前缀码。死记结论而不验证树形就会选错。

🔄反命题思维 若将频次改为含 0 或相等，合并顺序不唯一，但总编码长度不变；若题目改为“给定字符串求最短编码位数”，则需计算各字符频次与编码长度的加权和。刷到类似题先问自己：命题人想考我贪心构造还是前缀码性质？