NOIP 普及组初赛 · NOIP 2011 普及组初赛试题 第 15 题

现有一段文言文，要通过二进制哈夫曼编码进行压缩。简单起见，假设这段文言文只由 $4$ 个汉字“之”、“呼”、“者”、“也”组成，它们出现的次数分别为 $700,600,300,200$。那么，“也”字的编码长度是（ ）。

哈夫曼编码的核心就一句话：每次把频率最小的两个节点拎出来合并成一颗新树，新树的频率是俩数之和。把这过程重复到只剩一棵根节点，再数一下目标字符在树里的深度，就是它的编码长度。

最容易栽跟头的就是合并顺序搞反，随手把大的先加一起，结果树的高度被压扁了，深度算出来偏小。还有的同学以为编码长度跟频率成反比就瞎蒙，忘了哈夫曼树是动态生成的，必须严格按从小到大两两合并。

这道题考的是哈夫曼编码的构造规则以及编码长度与树深度的关系。哈夫曼编码的核心就一句话：每次把频率最小的两个节点拎出来合并成一颗新树，新树的频率是俩数之和。把这过程重复到只剩一棵根节点，再数一下目标字符在树里的深度，就是它的编码长度。频率越低，深度越深，编码越长；频率高的字符挤在靠近根的地方，编码短。命题人爱在这里挖坑，比如让你算某个字的编码长度，或者让你判断编码是否最优，如果合并顺序不对，树的高度就变了，答案自然跟着错。所以拿到题先想：这四个字里谁最小？200 的“也”和 300 的“者”最小，先把它们加起来得到 500。现在剩下的节点是 500、600、700，显然 500 和 600 最小，再合并成 1100。最后只剩 1100 和 700，合并成 1800，树就建好了。现在看“也”字，它和“者”先合并，所以它在合并后的子树里深度是 1；这个子树又和“呼”合并，深度再加 1 变成 2；最后这个子树再和“之”合并，深度再加 1 变成 3。编码长度就是 3，对应选项 C。易错点就是合并顺序搞反，比如先把 600 和 700 加起来，那“也”的深度就会变成 2，答案就错了。哈夫曼编码的构造规则是固定的，必须严格按从小到大两两合并，不能凭感觉。从考频来看，进制与编码这个大类在题库里一共考过 149 题，覆盖 11 个考试级别，逐年分布里 2023 年突然爆到 17 题，2024 年更是冲到 29 题，2025、2026 年也保持在 17 题左右，说明这类题目在近年越来越受命题人青睐。哈夫曼树单独考过 44 题，覆盖 5 个级别，逐年分布里 2023 年考了 5 题，2024 年考了 10 题，2025 年考了 10 题，2026 年考了 11 题，呈现明显的上升趋势。分赛事看，GESP 六级考了 31 题，GESP 七级考了 5 题，NOIP 普及组初赛考了 1 题，NOIP 提高组初赛考了 3 题。综合这些数据，可以预测未来几年哈夫曼树相关的题目还会继续高频出现，命题人可能会在更复杂的场景下考查，比如多字符、带权路径长度计算，或者结合其他编码知识综合出题。对于这道题，只要记住哈夫曼编码的构造规则和深度与编码长度的关系，就能稳稳拿下。