NOIP 普及 2011 第一轮 第 15 题：哈夫曼编码的编码长度

题目

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

选项

• A. 1
• B. 2
• C. 3
• D. 4

答案

C

题解

考点定位

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

解题过程

频次：之700、呼600、者300、也200。哈夫曼合并最小两堆：

1. 合 300+200=500（者也）
2. 合 500+600=1100（呼+者也）
3. 合 1100+700=1800（根）

「也」在最深层：深度 3 ⇒ 编码长度 3。

选 C。

易错提醒

① 每次合并频次最小的两个；② 出现最少的字符编码最长——「也」(200) 显然最深。