CSP-J 入门级 · CSP 2022 入门级第一轮 第 7 题

假设字母表 $\{a,b,c,d,e\}$ 在字符串出现的频率分别为 $10\%$，$15\%$，$30\%$，$16\%$，$29\%$。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母 $d$ 的编码长度（ ）位。

这题考哈夫曼编码，核心就是贪心合并最小频次。拿到题先别急着算，把频率从小到大排好序，模拟每次合并两个最小的，画出树形结构，d 在哪一层答案就出来了。

最容易掉进两个坑：一是以为频率大的字母编码一定长，其实哈夫曼树结构不唯一，合并顺序不同可能导致同一频率字母深度不同；二是算错合并后的新节点频率，导致后续合并顺序全乱。比如把 a+b 算成 25 后，若错误地先和 d(16) 合并，树形就变了，d 的编码长度可能变成 3。所以一定要严格按从小到大贪心合并，并在纸上画出完整的二叉树，数 d 到根的路径长度才稳妥。

本题考查哈夫曼树构建与编码长度计算，属于典型贪心算法应用。命题人喜欢给一组看似杂乱但总和为100%的频率，让学生判断某个特定字母的编码长度。哈夫曼编码的核心规则是：每次从当前所有节点中选取两个权值（频率）最小的进行合并，生成一个新节点，其权值为两者之和，新节点成为这两个原节点的父节点。重复此过程直到只剩一个根节点。

给定频率：a=10%, b=15%, c=30%, d=16%, e=29%。排序后为：a(10) < b(15) < d(16) < e(29) < c(30)。

第一步：合并最小的 a(10) 和 b(15)，得到新节点 25。 第二步：当前最小的是 d(16) 和刚才生成的 25，合并它们得到 41。 第三步：剩余 e(29) 和 c(30)，合并得到 59。 第四步：最后合并 41 和 59，得到根节点 100。

此时树形结构如下： 根(100) -> 左子树(41) -> 左(d,16), 右(25) -> 左(a,10), 右(b,15) 根(100) -> 右子树(59) -> 左(e,29), 右(c,30)

观察字母 d 的位置：从根出发，向左走到(41)，再向左走到 d，路径长度为 2。因此 d 的编码长度是 2 位，对应选项 B。

避坑提示：哈夫曼树的结构依赖于合并顺序，虽然最终编码长度分布是确定的，但在构建过程中若不小心把 d 和 25 合并后的新节点再与 e 合并（错误地认为 e 比 25 小），树形就会完全不同，d 的深度可能变成 3。务必严格按从小到大贪心合并，并在纸上画出完整二叉树，数清 d 到根的路径长度。