NOIP 提高组初赛 · NOIP 2015 提高组初赛试题 第 12 题

在数据压缩编码的应用中，哈夫曼（Huffman）算法是一种采用了（ ）思想的算法。

拿到题先想哈夫曼树是怎么建出来的：每次把权值最小的两个节点拎出来合并，这步操作本身就是在局部做最优选择，顺着这个‘局部最优’的线索就能直接锁定贪心思想。

很多孩子看到‘合并’两个字就下意识往分治想，其实分治是把大问题拆成互相独立的小问题分别解决，而哈夫曼每一步的合并都依赖前面合并产生的结果，并不独立；递推通常指按固定规律一步步推数值，回溯则是反复撤销尝试，这两者跟哈夫曼的‘每次选最小’特征都搭不上边。最容易掉坑的是把‘局部最优’误当成‘分治’，记住贪心的核心就是每一步只看眼前最优，不回头，也不拆成独立子问题。

考点概念：哈夫曼算法与贪心思想

哈夫曼（Huffman）算法的核心操作是：从当前森林中选出权值最小的两棵树，把它们合并成一棵新树，新树的权值是两棵子树权值之和。这个过程反复进行，直到只剩下一棵树为止。

为什么这是贪心？因为算法在每一步都只考虑当前局部最优的选择——把最小的两个合并，而不关心这样做会不会影响后面的步骤。事实上，哈夫曼算法可以证明这种局部最优策略最终能得到全局最优的带权路径长度（WPL）。这就是贪心算法的典型特征：每一步都选当前最好的，局部最优累积成全局最优。

命题视角

命题人爱考这种‘算法思想归类’题，因为知识点本身不难，但需要学生真正理解算法的运行机制，而不是死记硬背。哈夫曼树是数据结构里的经典，但很多孩子只记得‘建哈夫曼树’，却说不清它属于哪一类算法思想。命题人往往会在选项里放几个看起来很相近的概念（比如分治、递推），考察学生是否真正区分清楚。

思考心法

拿到题先想：哈夫曼树是怎么建出来的？每次把权值最小的两个节点拎出来合并。这一步操作本身就是在局部做最优选择。顺着这个‘局部最优’的线索，就能直接锁定贪心思想。如果学生能说出‘每次选最小’这个特征，基本就能排除其他选项了。

具体怎么算

虽然这是一道概念题，但理解算法的构造过程有助于加深印象。假设有一组叶子节点的权值，哈夫曼算法会先排序，取最小的两个合并，得到一棵新树，再把这棵新树放回集合中重新排序，继续取最小的两个合并……如此反复，直到只剩一棵树。整个过程就是不断在局部做最优选择，最终得到全局最优的编码方案。

避坑

很多孩子看到‘合并’两个字就下意识往分治想，其实分治是把大问题拆成互相独立的小问题分别解决，而哈夫曼每一步的合并都依赖前面合并产生的结果，并不独立；递推通常指按固定规律一步步推数值，回溯则是反复撤销尝试，这两者跟哈夫曼的‘每次选最小’特征都搭不上边。最容易掉坑的是把‘局部最优’误当成‘分治’，记住贪心的核心就是每一步只看眼前最优，不回头，也不拆成独立子问题。

考频与趋势

从题库数据看，贪心思想在历年考试中非常活跃：题库共考过 79 题，覆盖 7 个考试级别（2007-2026）；逐年分布：2007 年 1 题、2009 年 1 题、2015 年 1 题、2018 年 1 题、2023 年 12 题、2024 年 23 题、2025 年 24 题、2026 年 13 题、null 年 3 题；分赛事：GESP 六级 34 题、GESP 七级 27 题、GESP 八级 10 题、GESP 五级 3 题、NOIP 提高组 初赛 3 题、CSP 提高级 1 题、NOIP 普及组 初赛 1 题。可以看出，贪心考点在近年（尤其是 2023-2026 年）考频显著上升，说明命题人越来越喜欢用这类思想归类题来考察学生的算法直觉。

预测

基于上述数据，未来几年贪心思想仍将是高频考点，尤其在 GESP 六级、七级和 NOIP 提高组/普及组初赛中，很可能会继续出现类似的‘算法思想归类’单选题。暂无足够依据预测具体会考哪个算法，但可以肯定的是，只要学生能清晰说出‘局部最优’这个特征，就能应对这类题目。