GESP 六级 · GESP 202603 C++ 六级 第 9 题

有 $6$ 个字符，它们出现的次数分别为：$\{2, 3, 3, 4, 6, 8\}$，现在用哈夫曼编码为这些字符编码，最小加权路径长度 WPL（每个字符的出现次数 $\times$ 它的编码长度，再把每个字符结果加起来）的值为（）。

哈夫曼编码：每次合并权值最小的两个节点，构建最优二叉树，使带权路径长度（WPL）最小。用于数据压缩。

审题时注意题目要求（选正确还是选错误），避免因审题不清失分。涉及代码的题目要逐行分析变量变化。

【考点】哈夫曼树构造｜贪心算法｜WPL 定义

哈夫曼树是贪心算法的经典载体。构造时把全部频率放入最小堆，每次弹出两个最小节点合并，新生成节点的频率等于两者之和。关键点在于：每次合并后，新节点的深度比原节点多一层，所以总 WPL = 所有合并步骤中新生成节点的频率之和。

本题六个初始频率为 2,3,3,4,6,8。合并过程：2+3=5，3+4=7，5+6=11，7+8=15，11+15=26。累加每一次新生成的频率：5+7+11+15+26 = 64。

A 选项 58 是把原始频率直接乘某个深度后相加，完全忽略了合并过程；B 选项 60 是常见的手算错误，往往漏掉某次合并；C 选项 62 可能来自错误的树形——哈夫曼树不是任意二叉树，必须严格满足贪心构造条件。若只背"WPL=频率×深度”公式，不去模拟合并，就会把本题算成 58 或 60 这类看似合理实则错误的值。

反命题视角：若把本题改成"2,3,3,4,6,9"，合并序列变成 5,7,11,15,26，WPL 仍为 64，说明 WPL 对最末位频率变化不敏感；若改成"2,3,3,4,5,6"，合并序列为 5,7,8,13,21，WPL=58，答案就跳到 A。刷到类似题，先问自己"命题人想考我什么？"——通常就是贪心构造 +WPL 计算。