校园智能化能源管理系统实践与优化
2026/11/5 2:40:43
软考中级软件设计师高频考点：分治动态规划贪心与回溯四种算法设计策略辨析及真题详解（附历年真题·百度网盘）
🎯所属考纲模块：专题六 数据结构与常用算法（考点 05：算法设计策略）
🏷️考查题型：上午综合知识单选题（1 分，年均 1~2 题）
📌核心知识点：分治与动态规划的分界（子问题是否重叠）、贪心的局部最优与全局最优、回溯与分支限界的搜索方式、策略与经典算法的配对
🔁系列序号：series_31
本文核心知识点目录
- 软考中级软件设计师高频考点：分治动态规划贪心与回溯四种算法设计策略辨析及真题详解（附历年真题·百度网盘）
- 一、 四种策略的判定标准
- 二、 最容易混的两组
- 三、 真题切片
- 3.1 真题 1（2021 年上半年 上午试卷 第 64 题）
- 3.2 真题 2（2021 年下半年 上午试卷 第 62 题）
- 3.3 补充真题（2022 年下半年 上午试卷 第 64 题）
- 四、 易错点与相邻考点辨析
- 附：相关真题与复习资料
算法设计策略这一块，软考从不让你手写算法，只考**“这个算法/这句话属于哪种策略”**。四种策略的边界非常清晰，但考场上极易被两句描述绕晕：
- “子问题相互独立” → 分治；
- “最优子结构 + 重叠子问题” → 动态规划；
- “每步都取当前最好” → 贪心；
- “解空间树 + 深度优先 + 剪枝” → 回溯。
本篇把这四句话和经典算法的对应关系钉死，再用两道真题验证。
一、 四种策略的判定标准
| 策略 | 核心思想 | 判定关键词 | 经典算法 |
|---|---|---|---|
| 分治 | 把问题分成相互独立的同样子问题，分别求解后合并 | 子问题独立、递归、合并 | 归并排序、快速排序、二分查找、大整数乘法 |
| 动态规划 | 子问题重叠，用表记录已解子问题，避免重复计算 | 最优子结构+重叠子问题 | 0-1 背包、最长公共子序列、矩阵连乘、Floyd |
| 贪心 | 每一步都取当前局部最优，不回溯 | 局部最优、不可撤销 | Dijkstra 最短路、Prim/Kruskal 最小生成树、哈夫曼编码 |
| 回溯 | 深度优先搜索解空间树，不满足约束就剪枝回退 | 解空间树、深度优先、剪枝 | 八皇后、图的 m 着色、子集和、迷宫求解 |
二、 最容易混的两组
第一组：分治 vs 动态规划
分治：子问题互不重叠，各自独立求解，最后合并 → 归并排序、二分查找 动规：子问题大量重叠，必须"记住"中间结果再递推 → 斐波那契、0-1 背包判据只有一条：子问题是否重叠。重叠 → 动规；不重叠 → 分治。
第二组：回溯 vs 分支限界
| 维度 | 回溯法 | 分支限界法 |
|---|---|---|
| 搜索方式 | 深度优先 | 广度优先（或最小耗费优先） |
| 存储结构 | 栈（递归） | 队列 / 优先队列 |
| 目标 | 找出所有解或任一解 | 找最优解 |
2021 年上半年第 65 题就考这个分野："若了解问题的解空间，并以广度优先的方式搜索解空间"→ 分支限界法。
三、 真题切片
3.1 真题 1（2021 年上半年 上午试卷 第 64 题）
在求解某问题时，经过分析发现该问题具有最优子结构和重叠子问题性质。则适合（64）算法设计策略得到最优解。
A. 分治 B. 贪心 C. 动态规划 D. 回溯
答案：C
排除逻辑：
- 题干直接给出动态规划的两个成立条件：“最优子结构 + 重叠子问题”，这是教材原话；
- A 分治要求子问题互不重叠，与"重叠子问题"直接矛盾；
- B 贪心不要求重叠子问题，也不保证全局最优（需另证贪心选择性质）；
- D 回溯是搜索解空间，与"最优子结构"无关。
3.2 真题 2（2021 年下半年 上午试卷 第 62 题）
归并排序算法在排序过程中，将待排序数组分为两个大小相同的子数组，分别对两个子数组采用归并排序算法进行排序，排好序的两个子数组采用时间复杂度为 O(n) 的过程合并为一个大数组。根据上述描述，归并排序算法采用了（62）算法设计策略。
A. 分治 B. 动态规划 C. 贪心 D. 回溯
答案：A
排除逻辑：
- 题干三要素"分成两个大小相同的子数组（划分）+分别递归排序（求解）+O(n) 合并（合并）"正是分治的"分—治—合"三步；
- B 动态规划——左右两半互不重叠，没有"重叠子问题"，也不需要记忆化表；
- C 贪心——没有任何"局部最优选择"动作；
- D 回溯——没有解空间树与剪枝。
3.3 补充真题（2022 年下半年 上午试卷 第 64 题）
采用 Dijkstra 算法求解下图 A 点到 E 点的最短路径，采用的算法设计策略是（64）。
A. 分治法 B. 动态规划 C. 贪心算法 D. 回溯法
答案：C
Dijkstra 每次从"未确定集合"中选出当前距离最小的顶点并永久确定，这个"每步取当前最优且不回头"就是贪心的定义；Floyd 求全源最短路才是动态规划。
四、 易错点与相邻考点辨析
| 易错点 | 错误做法 | 正确做法 |
|---|---|---|
| 把归并排序归为动态规划 | 见到"递归+表"就选动规 | 归并左右子数组不重叠，属分治 |
| 把 Dijkstra 归为动态规划 | 与 Floyd 混为一谈 | Dijkstra贪心（单源）；Floyd动规（全源） |
| 认为贪心总能得最优解 | 所有优化问题都用贪心 | 贪心需满足贪心选择性质，0-1 背包用贪心会错（要用动规） |
| 把回溯与分支限界的搜索方式记反 | 认为回溯是广度优先 | 回溯深度优先；分支限界广度优先/最小耗费 |
相邻考点提醒：时间复杂度与排序稳定性在 series_15 已展开，本考点常与"某算法的时间复杂度"连考（如归并 O(nlogn)、快速排序最坏 O(n²)）；哈夫曼编码既属贪心又考 WPL，见 series_12。
附：相关真题与复习资料
本文涉及的算法设计策略专项历年真题解析已归档，需要可自取：
百度网盘: https://pan.baidu.com/s/1SwVEmITKHveCupjP_VH7pA 提取码: rk02 备用通道: https://pan.quark.cn/s/bd0eb7dd5673