GESP 六级 · GESP202609 C++ 六级 第 11 题

有 5 个字符，其出现频率分别为 2、4、5、9、12。按哈夫曼算法构造编码树，其最小带权路径长度 WPL 为（ ）。

哈夫曼树构造遵循贪心策略：每次从当前节点集合中取出权值最小的两个合并为新节点，新节点权值为两者之和，再放回集合。WPL 等于所有内部节点权值之和，也等于各叶子权值×深度之和。本题只需按规则合并四次即可。

选项 A 68 是漏加 12 这个内部节点；C 71 是合并顺序错成先合 9+12；D 73 是深度算错（把 12 当深度 2）。最阴险的是"合并后不重排"——若按原序 2,4,5,9,12 直接两两加，会漏掉 5 与 6 的合并，导致 WPL 偏大。

1. 考纲定位

本题考查 GESP 六级《算法与数据结构》模块中的贪心算法与哈夫曼树。命题人专门卡住"合并后未重新排序"和"深度计算错误"两大高频失误点，这是六级考生最容易栽跟头的地方。

2. 解题思维

先排序 [2,4,5,9,12]，每次取最小两数合并：2+4=6 → [5,6,9,12]；5+6=11 → [9,11,12]；9+11=20 → [12,20]；12+20=32。WPL 等于所有内部节点权值之和：6+11+20+32=69。