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

有 $6$ 个字符，它们出现的次数分别为：$3,4,7,8,12,15$，现在用哈夫曼编码为这些字符编码，最小加权路径长度 $WPL$ 的值为（ ）。

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

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

【考点】哈夫曼编码｜贪心算法｜二叉树WPL计算

考纲定位：GESP六级算法模块必考树结构应用，命题人用WPL计算卡住只会背编码规则的考生。

解题思维：哈夫曼树WPL等于所有合并产生的新节点频率之和——从3,4,7,8,12,15开始，合并3+4=7，累计7；合并7+7=14，累计7+14=21；合并8+12=20，累计21+20=41；合并14+15=29，累计41+29=70；合并20+29=49，累计70+49=119。通法：每次取最小两频率合并，累加新节点频率到WPL，直到只剩根。

陷阱拆解：A项113是漏算最后一次合并49；C项126是合并顺序错（如先合8+12再合7+7导致中间值偏大）；D项31是误把初始频率和49当答案。命题人偷换概念：WPL≠频率和，必须通过哈夫曼树构建过程累加新生成节点。

反命题思维：若改题给WPL反推频率，或加入相同频率需排序规则，考点就变成贪心策略的鲁棒性。刷到树结构题，先问自己"命题人想考我什么"，别死记公式。