GESP 七级 · GESP 202606 C++ 七级 第 4 题

有 $5$ 个字符，它们出现的次数分别为 $3$、$4$、$7$、$8$、$9$。使用哈夫曼编码时，最小的带权路径长度 WPL 为（ ）。

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

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

【考点】哈夫曼编码｜贪心算法｜带权路径长度

GESP 202606 C++ 七级 信息学基础。命题人通过"求最小带权路径长度"卡住考生对哈夫曼编码本质的理解——不是简单求和，而是贪心构造最优二叉树。

贪心策略：每次合并两个最小权值节点。初始序列 3,4,7,8,9。合并 3+4=7，序列变为 7,7,8,9；合并 7+7=14，序列变为 8,9,14；合并 8+9=17，序列变为 14,17；合并 14+17=31。WPL=7+14+17+31=69。此类题通法：WPL=所有内部节点权值之和。

错误选项 A(62) 源于误用"所有权重之和"，B(64) 混淆了"叶子节点权值和"与"内部节点权值和"，C(67) 偷换概念将"路径长度"当成"深度之和"。最阴险的是命题人故意给出"简单加法"的干扰项，测试你是否真正理解哈夫曼树的构造过程。

若命题人把权重改为 3,4,5,8,9，WPL 会因树结构变化而不同。刷到此类题先问自己："命题人想考我什么？"答案永远是哈夫曼树的贪心构造与 WPL 定义。