GESP 六级 · GESP 202409 C++ 六级 第 21 题

哈夫曼编码本质上是一种贪心策略。

贪心算法每一步做出当前最优选择，且不回溯。难点在于证明贪心策略的正确性（常用交换论证法）。

贪心算法需要严格证明正确性。典型错误：局部最优不等于全局最优。例如0-1背包问题就不能用贪心。

【考点】贪心策略｜哈夫曼树构建

1. 🎯 考纲定位

本题考查《GESP 六级 C++ 大纲》"算法思想"模块中的贪心策略判定。命题人卡住的是那些只背结论、不追本质的考生——他们知道哈夫曼编码能压缩，却说不清为什么能压缩。