NOIP 提高 2011 第一轮 第 15 题：现有一段文言文，要通过二进制哈夫曼编码进行压缩。简单起见，假设这段文言文只由

题目

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

答案

B、C

题解

考点定位

本题考「哈夫曼编码长度（不定项）」,对应大纲 3.2.3 哈夫曼树（难度【4】）。

解题过程

频次 之700、呼600、者300、也400。哈夫曼合并：300+400=700（者也）→ 与 700/600 的组合不唯一：

• 方案一：合并(300,400)=700，再合并 (700,700)=1400，再 (1400,600)：树高 3，「也」深 3；
• 方案二：合并(600,700)=1300 与 (300,400)=700 再并：高 2~3——「也」可在深度 2。

「也」深度可能为 2 或 3（不同合并顺序下哈夫曼树形态不唯一，但 WPL 相同）。

答案：B、C。

易错提醒

① 哈夫曼树形态不唯一但 WPL 唯一——同频次结点交换层数不改变总长；② 枚举合并顺序验证两种深度。