CSP-S 提高级 · CSP 2019 提高级第一轮第 13 题

选择题 · 答案 B · 考点：贪心算法、最短路径、图论算法

← 整套速查表 CSP-S 提高级全部真题

题目

以下哪些算法不属于贪心算法？（）

答案：B

考点

贪心算法讲解 →贪心算法真题汇总 →最短路径图论算法

解题思维

这题考的是算法思想分类。拿到题别急着背，先想每个算法的核心逻辑：是每一步都做了‘不可撤销’的贪心选择，还是通过多阶段递推来‘回头看’优化？看它有没有固定的决策顺序，有没有保存子问题的多解，就能快速区分。

常见错误

学生最容易把 Floyd 误判成贪心，因为它也是‘每次取最小值’，但它的本质是动态规划：通过枚举中间点 k 逐步优化，每一步都依赖前面所有 k 的结果，没有固定的贪心选择顺序，还会‘回头看’之前的路径。另外，部分同学会纠结 Dijkstra 是否贪心，其实它每次选当前距离最小的未处理顶点做松弛，决策不可撤销，就是典型的贪心，只是它要求边权非负而已。

详细解析（节选）

CSP 2019 P13 算法分类辨析

考察知识点

贪心算法与动态规划的本质区别
经典图论算法（最短路、最小生成树）的思想归属

同考点真题

第 28 题· NOIP 2010 普及组初赛试题 · 答案 num <= 2num < 3num == 2go(LEFT_TO_RIGHT)pos[i] == LEFTLEFT == pos[i]hour[i] + go(RIGHT_TO_LEFT)go(RIGHT_TO_LEFT) + hour[i]pos[i] = LEFT看解析 →
第 28 题· NOIP 2016 普及组初赛试题 · 答案 n-nn+1M[i]<C[j]M[i]<=C[j]count<=Acheck(mid)mid-1看解析 →
第 11 题· CSP 2019 入门级第一轮 · 答案 C看解析 →
第 19 题· CSP 2019 提高级第一轮 · 答案 CDB看解析 →
第 20 题· CSP 2020 入门级第一轮 · 答案 BDA看解析 →

在 OI伴学里做这道题

登录后可计时作答、查看完整六段式解析，并按你的错题自动生成同类练习。

去刷题先做一次 AI 学情诊断

CSP-S 提高级 · CSP 2019 提高级第一轮 第 13 题

题目

考点