GESP 六级 · GESP 202503 C++ 六级 第 6 题

给定字符集 $\{A, B, C, D\}$ 的出现频率分别为 $\{5, 1, 6, 2\}$，则正确的哈夫曼编码是（ ）。

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

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

【考点】哈夫曼编码｜优先队列｜树的构建

🎯 考纲定位 六级哈夫曼编码是信息论基础，命题人专卡"频率与码长反比"这一核心直觉，多数考生误以为频率高的码更长，直接排除 A、C。

🧠 解题思维 先建最小堆：B(1)、D(2)、A(5)、C(6)；合并 B+D 得 3，再合并 3+A 得 8，最后 8+C 得 14。树根右子为 C，左子为 8；8 的右子为 A，左子为 3；3 的左子为 B，右子为 D。按左 0 右 1 分配：C→0，A→11，B→100，D→101。

🪤 陷阱拆解 A、C 选项 C 的码长为 2，违反"最高频最短"原则；D 选项码长匹配但 C=0、A=10、B=101、D=100，与标准构建不符，命题人利用"左右子树可互换"的模糊性设坑，只背结论者易混淆。

🔄 反命题思维 若将频率改为 C=1、B=6，答案会彻底翻转；若题目允许任意合法哈夫曼码，B 与 D 均成立，但六级要求唯一解，必须锁定标准构建。