NOIP 提高组初赛 · NOIP 2011 提高组初赛试题 第 15 题

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

拿到题先别急着套公式，哈夫曼编码的核心是'贪心合并'。这题四个权值里有两对能凑出相同的和（300+400=700 与 600+700=1300 等），这种'平局'就是命题人埋的坑。做题时要把所有可能的合并次序都画出来，看'也'字在不同树形里落在第几层，答案就出来了。

很多学生看到哈夫曼编码就以为'权值越小层数越深'，直接断定'也'（400）一定比'之'（700）深，选成 3 或 4 层；也有同学只画了一种合并顺序（比如先合最小的两个），就武断认为只有这一种树形，漏掉了另一种同样合法的合并方式，导致把'2'这个选项也排除了。

考点与概念 哈夫曼编码要求构造一棵带权路径长度最小的二叉树。构造规则很简单：每次从当前所有节点里挑出两个权值最小的，把它们合并成一个新节点（新节点权值等于两者之和），重复直到只剩一个根节点。编码长度就是叶子节点在树里的深度（根为 0 层，子节点深度+1）。命题视角 命题人特别喜欢在权值出现'平局'时挖坑。本题四个权值 700,600,300,400，其中 300+400=700，正好与'之'的权值相同；而 600+700=1300 又与 400+900 等无关。因为存在多个'最小对'可选，哈夫曼树就不是唯一的，'也'字的深度可能不同，所以答案可能是多个选项。

思考心法与计算 拿到题先列四个叶子：之(700)、乎(600)、者(300)、也(400)。 第一步必须选两个最小的合并：只能是 300(者) 和 400(也)，得到新节点 A=700。此时剩下：之(700)、乎(600)、A(700)。 第二步要从{700,700,600}里选两个最小的。这里有两个'700'，它们分别是'之'和'A'。命题人允许我们任选一对作为'最小对'，于是产生两种合法的合并顺序： 1) 选乎(600) 和 之(700) 合并 → 新节点 B=1300。此时剩下 A(700) 和 B(1300)。第三步只能合并它们 → 根=2000。 在这种树里，'也'是 A 的左孩子，A 又是根的左孩子，所以'也'的深度是 2（编码长度 2）。 2) 选乎(600) 和 A(700) 合并 → 新节点 C=1300。此时剩下 之(700) 和 C(1300)。第三步合并 → 根=2000。 在这种树里，'也'是 A 的孩子，而 A 是 C 的左孩子，C 是根的左孩子，所以'也'的深度是 3（编码长度 3）。 两种树都满足哈夫曼构造规则，因此'也'的编码长度可能是 2 或 3。

避坑提醒

• 不要以为'400'一定比'700'深，哈夫曼只保证'带权路径和最小'，不保证每个叶子深度单调。
• 遇到多个相同最小权值时，务必把所有可能的配对都试一遍，否则就会漏掉正确答案。
• 编码长度就是深度，别把'层数'和'深度'搞混（根为 0 层时，深度=层数+1；但题目问的是编码长度，直接数节点在树上的深度即可）。

考频与趋势 哈夫曼树在题库里共考过 44 题，覆盖 5 个考试级别（2009-2026）；逐年分布：2009 年 1 题、2011 年 2 题、2015 年 1 题、2021 年 1 题、2022 年 1 题、2023 年 5 题、2024 年 10 题、2025 年 10 题、2026 年 11 题、null 年 2 题；分赛事：GESP 六级 31 题、GESP 七级 5 题、CSP 入门级 4 题、NOIP 提高组 初赛 3 题、NOIP 普及组 初赛 1 题。 从数据看，哈夫曼树在 NOIP 提高组初赛中已考过 3 次，且近三年（2023-2026）在 GESP 六级和 CSP 入门级的考频持续攀升，说明该考点热度很高。

预测 基于给定数据与经验，未来在 CSP-J/S 或 GESP 中仍可能出现类似的'多解哈夫曼树'题目，但题干通常会给出更明确的合并规则（如'每次只合并相邻权值'或'规定平局时按字母序'），以减少歧义。若出现完全开放的多解情形，大概率会设计成'可能为 2 或 3'这样的多选式单选，考察学生是否意识到树的非唯一性。暂无足够依据预测具体年份或题型变化。