DFS 与 BFS 的核心区别是？
考点：搜索回顾（A1）。
解析：DFS 用栈（递归）一路到底、BFS 用队列层层扩展——BFS 求最短路（边权 1）、DFS 找解与回溯。✅ 正确
排除法：B 显然错；C 无依据；D 反了。
关联 · A6 进阶总表：进阶都建立在两者之上。
判断题：搜索 = 在状态空间（所有可能局面）中找目标状态——搜索题的规模 = 状态空间大小。
考点：状态空间（A2）。
解析：搜索 = 在状态空间（所有可能局面）中找目标状态——搜索题规模 = 状态空间大小。✅ 正确
排除法：无（判断题）。混淆点：状态空间爆炸是搜索的敌人。
关联 · A3 搜索树：展开过程成树。
判断题：搜索过程展开成搜索树——节点是状态、边是转移；剪枝 = 砍掉不必展开的子树。
考点：搜索树（A3）。
解析：搜索过程展开成搜索树——节点是状态、边是转移；剪枝 = 砍掉不必展开的子树。✅ 正确
排除法：无（判断题）。混淆点：同一状态可能对应多个节点（判重的作用）。
关联 · A4 剪枝意义：砍子树。
判断题：剪枝不改变答案，只减少展开的节点数——好剪枝能让指数级搜索变得可过。
考点：剪枝意义（A4）。
解析：剪枝不改变答案，只减少展开节点数——好剪枝能让指数级搜索变得可过。✅ 正确
排除法：无（判断题）。混淆点：剪枝是"优化"不是"改算法"。
关联 · B 组剪枝：五类剪枝。
判断题：搜索与 DP 完全等价——所有搜索题都能改写成多项式 DP。
考点：搜索与 DP（A5）。
解析：搜索与 DP 不完全等价——NP 难问题（如 TSP 的精确解）只能搜索/状压指数级，写不出多项式 DP。✅ 答案 B（错误）
排除法：无（判断题）。混淆点：只有"状态数多项式"的搜索才等价于 DP。
关联 · G4 搜索 vs 其他：能 DP 则 DP。
搜索进阶总表是？
考点：进阶总表（A6）。
解析：剪枝 / 迭代加深（IDDFS/IDA*）/ 双向搜索（双向 BFS/MITM）/ A* 启发式 / 状态压缩与记忆化。✅ 正确
排除法：B/C/D 以偏概全。
关联 · 本章各板块：总表即目录。
可行性剪枝是？
考点：可行性剪枝（B1）。
解析：当前状态已不可能到达目标（如子集和已超）就立即返回。✅ 正确
排除法：B 是搜索终点处理；C/D 无关。
关联 · I6 代码：sum > target 即返回。
最优性剪枝是？
考点：最优性剪枝（B2）。
解析：当前代价已 ≥ 已知最优解就立即返回（找最小代价时）。✅ 正确
排除法：B 只找第一个解（非最优）；C/D 无关。
关联 · I5/O2 填空：
cnt >= ans剪枝。
判断题：顺序剪枝——优先尝试"看起来更有希望"的分支（如先放大的数、先走离目标近的方向），配合最优性剪枝更快收紧上界。
考点：顺序剪枝（B3）。
解析：优先尝试"更有希望"的分支（先放大的数、先走近方向）——配合最优性剪枝更快收紧上界。✅ 正确
排除法：无（判断题）。混淆点：顺序不影响正确性，只影响效率。
关联 · B2 最优性：好顺序 + 好上界 = 强剪枝。
判断题：对称性/冗余剪枝——本质相同的状态只搜一个（如 N 皇后第一行只放前一半列、旋转镜像去重）。
考点：对称性剪枝（B4）。
解析：本质相同的状态只搜一个（N 皇后第一行只放前一半列、旋转镜像去重）。✅ 正确
排除法：无（判断题）。混淆点：对称去重要"等价关系"成立。
关联 · I1 四皇后：4×4 解数 2（对称即一对）。
判断题：估价剪枝思想——用下界估价：当前 + 剩余最优下界 已知解就剪（IDA* 的基础）。
考点：估价剪枝思想（B5）。
解析：用下界估价——当前 + 剩余最优下界 ≥ 已知解就剪（IDA* 的基础）。✅ 正确
排除法：无（判断题）。混淆点：下界要"绝对下界"，高估会剪错。
关联 · E3 IDA*：f=g+h 超限剪枝。
判断题：剪枝必须不改变答案——可行性/最优性/对称性剪枝都保持正确性，剪错才会丢解。
考点：剪枝效果（B6）。
解析：剪枝必须不改变答案——可行/最优/对称剪枝都保持正确性。✅ 正确
排除法：无（判断题）。混淆点：剪错 = 丢解（P1 实证输出 0）。
关联 · P1 剪枝写反：实证丢解。
判断题：剪枝总表——可行（不可达）、最优（不更优）、顺序（先优后劣）、对称（去重）、估价（下界）五类。
考点：剪枝总表（B7）。
解析：可行（不可达）、最优（不更优）、顺序（先优后劣）、对称（去重）、估价（下界）五类。✅ 正确
排除法：无（判断题）。混淆点：五类可叠加使用。
关联 · B1~B5：五类汇总。
迭代加深（IDDFS）的核心思想是？
考点：IDDFS 思想（C1）。
解析：限制最大深度逐层加深——每次从头 DFS 到 maxdep，直到找到解。✅ 正确
排除法：B 是普通 DFS；C/D 无依据。
关联 · J1 代码：二叉树找 7 输出 2。
IDDFS 的适用场景是？
考点：适用场景（C2）。
解析：目标深度未知但不太深、状态空间大、BFS 存不下整层时用 IDDFS。✅ 正确
排除法：B/C/D 一刀切。
关联 · C6 例题：埃及分数/骑士精神。
判断题：IDDFS 兼具二者优点——像 BFS 一样找最短解（按深度递增），像 DFS 一样省空间。
考点：与 BFS/DFS 对比（C3）。
解析：IDDFS 兼具二者优点——像 BFS 找最短解（按深度递增），像 DFS 省空间。✅ 正确
排除法：无（判断题）。混淆点：代价是重复展开浅层。
关联 · C4 重复展开代价：代价可接受。
判断题：IDDFS 每层从头搜有重复展开，但浅层重复代价小——总复杂度与 BFS 同阶（分叉大的树）。
考点：重复展开代价（C4）。
解析：浅层重复代价小——分叉大的树总复杂度与 BFS 同阶。✅ 正确
排除法：无（判断题）。混淆点：最后一层的节点数往往超过前面所有层之和。
关联 · C3：为什么重复可接受。
判断题：IDA* = 迭代加深 + 估价剪枝——每层用 超过限深就剪，兼具 A* 的引导与 IDDFS 的省空间。
考点：IDA* 思想（C5）。
解析：IDA* = 迭代加深 + 估价剪枝——每层用 f=g+h 超过限深就剪。✅ 正确
排除法：无（判断题）。混淆点：A* 的引导 + IDDFS 的省空间。
关联 · J3 代码：限深 0 1 2 迭代。
判断题：经典例题（埃及分数、骑士精神）用迭代加深——因为解深度未知、状态巨大且不宜全存。
考点：例题思想（C6）。
解析：埃及分数、骑士精神用迭代加深——解深度未知、状态巨大且不宜全存。✅ 正确
排除法：无（判断题）。混淆点：都是"解在哪层不知道"的问题。
关联 · C2 适用：例题即场景。
判断题：IDDFS 因为每层深度浅，任何情况下都不需要判重。
考点：判重（C7）。
解析：IDDFS 也需要判重——同一状态在浅层重复出现时，不判重会在各层反复展开。"任何情况下都不需要"是错的。✅ 答案 B（错误）
排除法：无（判断题）。混淆点：判重与"每层重置"是两件事。
关联 · P3 忘重置：vis 不清空是另一类 bug。
双向 BFS 的核心思想是？
考点：双向 BFS 思想（D1）。
解析：从起点与终点同时扩展，两方向在中间相遇时拼出路径。✅ 正确
排除法：B/C 单向；D 无依据。
关联 · K3 代码：3x3 输出 4。
判断题：双向 BFS 要求终点已知且转移可逆——迷宫、数码、变换类问题适用。
考点：适用条件（D2）。
解析：要求终点已知且转移可逆——迷宫、数码、变换类问题适用。✅ 正确
排除法：无（判断题）。混淆点：终点未知时无法反向扩展。
关联 · D3 复杂度：适用才有收益。
判断题：双向 BFS 把 降到 ——分叉 b、深度 d 时两方向各走一半相遇。
考点：复杂度优化（D3）。
解析：双向 BFS 把 降到 ——两方向各走一半相遇。✅ 正确
排除法：无（判断题）。混淆点：，指数砍半。
关联 · G3 复杂度估计：总表之一。
折半搜索（MITM）的核心思想是？
考点：MITM 思想（D4）。
解析：把 n 个元素拆两半分别枚举，再合并两半结果（排序 + 二分/双指针）。✅ 正确
排除法：B 只枚举一半（漏解）；C/D 无依据。
关联 · K1 代码：{2,3,5,7} 得 2。
判断题：MITM 例题——子集和/大背包： 时 不可枚举，拆两半各 再合并即可。
考点：例题思想（D5）。
解析：n=40 时 2^40 不可枚举，拆两半各 2^20 再合并即可。✅ 正确
排除法：无（判断题）。混淆点：2^20 ≈ 100 万，两半都跑得起。
关联 · D6 状态合并：排序二分。
判断题：MITM 合并——一半排序后，另一半每个值用二分/双指针查匹配，。
考点：状态合并（D6）。
解析：一半排序后，另一半每个值用二分/双指针查匹配，。✅ 正确
排除法：无（判断题）。混淆点：P4 排序方向错则二分落空。
关联 · O6 填空：
target - s2查配对。
判断题：双向搜索必须判重——两方向都记已访问状态，否则相遇检测失效、状态爆炸。
考点：哈希判重（D7）。
解析：双向搜索必须判重——两方向都记已访问状态，否则相遇检测失效、状态爆炸。✅ 正确
排除法：无（判断题）。混淆点：判重是双向搜索正确性的关键。
关联 · K5 填空：
vis2.count(u)判相遇。
A* 的核心思想是？
考点：A* 思想（E1）。
解析：优先队列按 f = g + h 排序——g 已走代价、h 到目标估价，先扩展最有希望的状态。✅ 正确
排除法：B/C/D 都不是 A*。
关联 · L4 填空：f = g + h。
判断题：估价函数 h 可以任意大于真实距离——A* 仍然保证找到最优解。
考点：h 可采纳性（E2）。
解析：h 不能任意大于真实距离——高估时 A* 可能返回非最优解。"可以任意大"是错的。✅ 答案 B（错误）
排除法：无（判断题）。混淆点：可采纳 = h ≤ 真实代价。
关联 · H2 估价不可采纳：概念与易错呼应。
判断题：IDA* 用限深代替优先队列—— 超过当前限深就剪，逐步增大限深。
考点：IDA* 思想（E3）。
解析：IDA* 用限深代替优先队列——f=g+h 超过当前限深就剪，逐步增大限深。✅ 正确
排除法：无（判断题）。混淆点：限深递增步长影响效率。
关联 · C5：同思想再考。
判断题：启发式设计——曼哈顿距离（数码/网格）是常用的可采纳估价（不绕路不可能更短）。
考点：启发式设计（E4）。
解析：曼哈顿距离是常用的可采纳估价（不绕路不可能更短）。✅ 正确
排除法：无（判断题）。混淆点：L2 实测 (1,1)→(5,5) 曼哈顿 8。
关联 · L2 代码：曼哈顿输出 8。
判断题：A* 是 Dijkstra 的推广—— 时 A* 退化为 Dijkstra。
考点：与 Dijkstra 关系（E5）。
解析：A* 是 Dijkstra 的推广——h≡0 时 A* 退化为 Dijkstra。✅ 正确
排除法：无（判断题）。混淆点：Dijkstra 是"零启发"的 A*。
关联 · 第 31 章最短路：跨章衔接。
判断题：适用判断——能设计出"不太离谱且可采纳"的估价函数时用 A*/IDA*；估价越准扩展越少。
考点：适用判断（E6）。
解析：能设计出"不太离谱且可采纳"的估价函数时用 A*/IDA*；估价越准扩展越少。✅ 正确
排除法：无（判断题）。混淆点：没有好估价就别硬上 A*。
关联 · G1 搜索选型：有估价→A*。
个不同元素的排列数是？
考点：排列生成（F1）。
解析：n 个不同元素的排列数 = n!（DFS 逐位选 + 访问标记）。✅ 正确
排除法：B 是子集数；C/D 无依据。
关联 · I2/M2 代码：3! = 6、第 3 个 2 1 3。
选 的组合数是？
考点：组合生成（F2）。
解析：n 选 k 组合数 = C(n,k)（DFS 每次从上一个位置之后选，天然去重）。✅ 正确
排除法：B 是排列；C 是子集；D 无依据。
关联 · I3/M3 代码：C(5,3)=10、第 3 个 1 2 5。
判断题：迷宫变体——最短路用 BFS（双向更优）、可行路径用 DFS、方案数用 DFS/DP、带权用 Dijkstra。
考点：迷宫变体（F3）。
解析：最短路用 BFS（双向更优）、可行路径用 DFS、方案数用 DFS/DP、带权用 Dijkstra。✅ 正确
排除法：无（判断题）。混淆点：按"问什么"选算法。
关联 · I4 代码：3x3 路径数 6。
判断题：数独 = 回溯搜索——逐格填数，用行/列/宫三个约束剪枝，不合法立即回退。
考点：数独思想（F4）。
解析：数独 = 回溯搜索——逐格填数，用行/列/宫三个约束剪枝，不合法立即回退。✅ 正确
排除法：无（判断题）。混淆点：M1/M6 实测 4x4 数独唯一解。
关联 · M4 填空：行/列/宫约束。
判断题：状态压缩搜索——棋盘类状态用二进制位表示（如每行皇后位置、访问集合），便于哈希与判重。
考点：状态压缩搜索（F5）。
解析：棋盘类状态用二进制位表示（皇后位置、访问集合），便于哈希与判重。✅ 正确
排除法：无（判断题）。混淆点：衔接第 33 章状压 DP。
关联 · 第 33 章状压：跨章衔接。
判断题：记忆化搜索——递归 DP 加查表：算过的状态直接返回，避免指数级重复展开。
考点：记忆化搜索应用（F6）。
解析：递归 DP 加查表——算过的状态直接返回，避免指数级重复展开。✅ 正确
排除法：无（判断题）。混淆点：M5 实测 fib(10)=55。
关联 · M5/O7 代码：memo 查表。
搜索选型流程是？
考点：搜索选型（G1）。
解析：最短路→BFS/双向；找解→DFS+剪枝；深度未知→IDDFS；有估价→A*/IDA*；n 略大→MITM。✅ 正确
排除法：B/C/D 一刀切。
关联 · 本章各算法：选型总表。
剪枝选型是？
考点：剪枝选型（G2）。
解析：先可行/最优（最常用），再顺序/对称，最后估价下界（进阶）。✅ 正确
排除法：B/C/D 无依据。
关联 · B7 剪枝总表：按性价比叠加。
判断题：复杂度估计——分叉 、深度 ：DFS 、BFS 空间、IDDFS 时间同阶空间 、双向 。
考点：复杂度估计（G3）。
解析：DFS 、BFS 空间、IDDFS 时间同阶空间 、双向 。✅ 正确
排除法：无（判断题）。混淆点：BFS 的瓶颈是空间。
关联 · C4/D3：两个优化的由来。
搜索 vs 其他算法的选择是？
考点：搜索 vs 其他（G4）。
解析：能 DP 就 DP（快）；DP 不了（状态爆炸/无最优子结构）再上搜索+剪枝。✅ 正确
排除法：B/C/D 一刀切。
关联 · A5 搜索与 DP：不完全等价。
判断题：时间管理——搜索题先写朴素暴力拿部分分，再逐步加剪枝；剪枝复杂度分析不清就实测跑极限数据。
考点：时间管理（G5）。
解析：先写朴素暴力拿部分分，再逐步加剪枝；复杂度不清就实测极限数据。✅ 正确
排除法：无（判断题）。混淆点：考试策略——搜索题拿分优先。
关联 · G6 选择综合：策略总结。
判断题：选择综合——"小数据枚举、中等剪枝/MITM、最短路双向 BFS、有估价 A*"是搜索题四板斧。
考点：选择综合（G6）。
解析："小数据枚举、中等剪枝/MITM、最短路双向 BFS、有估价 A*"是搜索题四板斧。✅ 正确
排除法：无（判断题）。混淆点：按数据规模选武器。
关联 · G1 选型：四板斧汇总。
判断题：剪枝条件写反（如可行性剪成"不满足才继续"）会把合法解全剪掉——剪枝必须保持"只剪必错的分支"。
考点：剪枝过度（H1）。
解析：剪枝条件写反（可行性剪成"不满足才继续"）会把合法解全剪掉。✅ 正确
排除法：无（判断题）。混淆点：P1 实证输出 0。
关联 · P1 代码：剪枝反实证。
判断题：h 不可采纳（高估真实代价）时 A* 可能返回非最优路径——可采纳性是 A* 正确性的前提。
考点：估价不可采纳（H2）。
解析：h 高估真实代价时 A* 可能返回非最优路径——可采纳性是正确性前提。✅ 正确
排除法：无（判断题）。混淆点：宁可低估不可高估。
关联 · E2：概念呼应。
判断题：IDDFS 每轮之间不清空访问标记/状态，会导致后续轮次"走不进去"而漏解。
考点：迭代加深漏判（H3）。
解析：IDDFS 每轮之间不清空访问标记，后续轮次"走不进去"而漏解。✅ 正确
排除法：无（判断题）。混淆点：P3 实证输出 -1。
关联 · P3 代码：vis 不重置实证。
判断题：双向搜索合并时漏判相遇（只查一端标记）或忘算两端距离，会得到错误步数甚至死循环。
考点：双向状态合并（H4）。
解析：漏判相遇（只查一端标记）或忘算两端距离，会得到错误步数甚至死循环。✅ 正确
排除法：无（判断题）。混淆点：合并 = 判相遇 + 两边距离相加。
关联 · K5 填空：相遇检测。
判断题：以下结论全部正确——"剪枝不改答案；IDDFS 逐层加深且省空间；双向 BFS 把 降到 ；A* 的 h 必须可采纳；MITM 拆两半合并"。
考点：综合判断（H5）。
解析：五结论全对——剪枝不改答案；IDDFS 逐层加深且省空间；双向 BFS 降到 ；A* 的 h 必须可采纳；MITM 拆两半合并。✅ 正确
排除法：无（判断题）。混淆点：本章核心结论自检清单。
关联 · 本章全部核心结论：收官判断题。
01#include <bits/stdc++.h> 02using namespace std; 03int n = 4, cnt = 0; 04int col[5]; // col[r] = 第 r 行皇后所在列 05void dfs(int r) { 06 if (r > n) { cnt++; return; } 07 for (int c = 1; c <= n; c++) { 08 bool ok = true; 09 for (int i = 1; i < r; i++) 10 if (col[i] == c || abs(col[i] - c) == r - i) ok = false; // 同列/同对角线 11 if (ok) { col[r] = c; dfs(r + 1); } 12 } 13} 14int main() { dfs(1); cout << cnt; return 0; }
单选题：程序输出是？（4×4 棋盘 N 皇后解数）
考点：N 皇后 DFS（I1）。
解析：4×4 棋盘 4 皇后共 2 个解（(1,2)(2,4)(3,1)(4,3) 与其镜像）。✅ 答案 B
排除法：A 1 只数一半；C/D 是 8 皇后量级错记。
关联 · B4 对称性：两解互为镜像。
01#include <bits/stdc++.h> 02using namespace std; 03int n = 3, cnt = 0, vis[4] = {0}, a[4]; 04void dfs(int dep) { 05 if (dep > n) { cnt++; return; } 06 for (int i = 1; i <= n; i++) 07 if (!vis[i]) { 08 vis[i] = 1; 09 a[dep] = i; 10 dfs(dep + 1); 11 vis[i] = 0; 12 } 13} 14int main() { dfs(1); cout << cnt; return 0; }
单选题：程序输出是？（1~3 的全排列数）
考点：全排列数（I2）。
解析：3! = 6（123/132/213/231/312/321）。✅ 答案 C
排除法：A 3 是元素数；B 9 是 n²；D 8 是 2³。
关联 · F1 排列生成：vis 标记 + 回溯。
01#include <bits/stdc++.h> 02using namespace std; 03int n = 5, k = 3, cnt = 0, a[6]; 04void dfs(int dep, int st) { // st = 上一个选的位置 05 if (dep > k) { cnt++; return; } 06 for (int i = st + 1; i <= n; i++) { 07 a[dep] = i; 08 dfs(dep + 1, i); 09 } 10} 11int main() { dfs(1, 0); cout << cnt; return 0; }
单选题：程序输出是？（5 选 3 的组合数）
考点：组合数（I3）。
解析：C(5,3) = 10（st 参数保证只往后选、天然去重）。✅ 答案 D
排除法：A 6 是 C(4,2)；B 5；C 20 是排列 A(5,3)。
关联 · F2 组合生成：从 st+1 起选。
01#include <bits/stdc++.h> 02using namespace std; 03int n = 3, cnt = 0; 04void dfs(int x, int y) { // 3x3 网格，只能向右/向下 05 if (x == n && y == n) { cnt++; return; } 06 if (x < n) dfs(x + 1, y); 07 if (y < n) dfs(x, y + 1); 08} 09int main() { dfs(1, 1); cout << cnt; return 0; }
单选题：程序输出是？（(1,1) 到 (3,3) 的路径数）
考点：网格路径计数（I4）。
解析：3x3 只能右/下：(1,1)→(3,3) 共 C(4,2) = 6 条。✅ 答案 A
排除法：B 4 漏；C 8 是 2³；D 2 只对角线。
关联 · F3 迷宫变体：计数用 DFS。
01void dfs(int dep, int cnt) { // 已走 cnt 步，找最小步数 02 if (______) return; // 最优性剪枝：不比当前最优更优 03 if (到达目标) { ans = cnt; return; } 04 ... 05}
单选题：横线处应填入？
考点：最优性剪枝（I5）。
解析：cnt >= ans 时不可能更优，立即返回。✅ 答案 B
排除法：A 是"已更优才剪"（写反）；C/D 无依据。
关联 · B2 最优性剪枝：填空即剪枝行。
01#include <bits/stdc++.h> 02using namespace std; 03int a[5] = {0, 2, 3, 5, 7}, n = 4, target = 10, cnt = 0; 04void dfs(int i, int sum) { 05 if (sum > target) return; // 可行性剪枝 06 if (i > n) { if (sum == target) cnt++; return; } 07 dfs(i + 1, sum + a[i]); 08 dfs(i + 1, sum); 09} 10int main() { dfs(1, 0); cout << cnt; return 0; }
单选题：程序输出是？（子集和为 10 的方案数）
考点：可行性剪枝 + 子集和（I6）。
解析：{2,3,5,7} 和为 10：{3,7}、{2,3,5} → 2 种。✅ 答案 C
排除法：A 1 漏一种；B/D 无依据。
关联 · B1 可行性剪枝：sum > target 即返回。
// 二叉树：1 的孩子 2、3；2 的孩子 4、5；3 的孩子 6、7。目标 = 7（深度 2） // IDDFS：maxdep 从 0 起逐层加深，找到目标就输出 maxdep // maxdep=0 访问 1（无）；maxdep=1 访问 1 2 3（无）；maxdep=2 找到 7
单选题：程序输出是？
考点：逐层加深找到目标（J1）。
解析：目标 7 在二叉树深度 2——maxdep=2 时找到，输出 2。✅ 答案 B
排除法：A 1 只搜到第 1 层；C/D 无依据。
关联 · C1 IDDFS 思想：逐层加深。
// 二叉树同 J1，IDDFS 输出每一轮访问的节点序列： // maxdep=0: 1 // maxdep=1: 1 2 3 // maxdep=2: 1 2 4 5 3 6 7
单选题：程序输出是？
考点：每轮访问节点（J2）。
解析：三轮分别访问 1 / 1 2 3 / 1 2 4 5 3 6 7（先序遍历到限深）。✅ 答案 A
排除法：B 漏第一轮；C/D 序列错。
关联 · C4 重复展开：1 每轮都被重访。
01// IDA*：限深 maxf 从 0 起逐步增大，每次输出当前限深： 02for (int maxf = 0; ; maxf++) { 03 cout << maxf << " "; 04 if (ida_star(0, maxf)) break; 05} 06// 假设第 3 次迭代（maxf = 2）找到解
单选题：程序输出是？
考点：限深迭代（J3）。
解析：maxf 从 0 递增输出 0 1 2（第三次找到）。✅ 答案 C
排除法：A 从 1 起；B 只最后值；D 无依据。
关联 · C5 IDA*：限深序列。
01bool dfs(int u, int dep, int maxdep) { 02 if (u == target) return true; 03 if (______) return false; // 到达限深仍未找到 04 for (int v : g[u]) 05 if (dfs(v, dep + 1, maxdep)) return true; 06 return false; 07}
单选题：横线处应填入？
考点：限深判断（J4）。
解析：到达限深仍未找到 → dep == maxdep 返回 false。✅ 答案 A
排除法：B 方向反；C/D 无依据。
关联 · O3：同函数另一空。
// 链 1-2-3-4，目标 = 4（深度 3），IDDFS 逐层加深直到找到
单选题：程序输出是？（找到目标时的 maxdep）
考点：链上 IDDFS（J5）。
解析：链 1-2-3-4 目标 4 在深度 3——maxdep=3 时找到。✅ 答案 D
排除法：A/B 深度不够；C 4 是节点编号。
关联 · J1：不同结构同法。
// 二叉树同 J1，IDDFS 统计：maxdep=0/1/2 三轮各访问 1 / 3 / 7 个节点， // 最后输出找到目标时的 maxdep 与三轮总访问次数
单选题：程序输出是？
考点：访问次数统计（J6）。
解析：三轮访问 1 + 3 + 7 = 11 次，maxdep = 2。✅ 答案 B
排除法：A 7 只是第三轮；C/D 数错。
关联 · C4 重复展开代价：11 = 1+3+7 实证。
// {2,3,5,7} 拆两半：{2,3} 与 {5,7}，求子集和为 10 的方案数
// 半 A = {2,3} 子集和：{0,2,3,5}；半 B = {5,7} 子集和：{0,5,7,12}
// 合并：5+5=10、3+7=10 → 2 种
单选题：程序输出是？
考点：折半搜索（K1）。
解析：{2,3} 和 {0,2,3,5}、{5,7} 和 {0,5,7,12}：5+5=10、3+7=10 → 2。✅ 答案 C
排除法：A 1 漏；B/D 无依据。
关联 · D4 MITM 思想：拆两半合并。
// 半 A = {2,3}，枚举其全部子集和并排序输出
单选题：程序输出是？
考点：子集和枚举（K2）。
解析：{2,3} 的全部子集和排序：0、2、3、5。✅ 答案 D
排除法：A 混入 7（另一半元素）；B 漏空集；C 漏 3。
关联 · D6 状态合并：合并前的准备。
// 3x3 网格，(1,1) 到 (3,3) 双向 BFS：
// 正向 2 层 {(1,1)}→{(1,2),(2,1)}→{(1,3),(2,2),(3,1)}
// 反向 2 层 {(3,3)}→{(2,3),(3,2)}→{(1,3),(2,2),(3,1)}
// 在 (2,2) 相遇：总步数 = 2 + 2 = 4
单选题：程序输出是？
考点：双向 BFS（K3）。
解析：3x3 网格正反各走 2 层在 (2,2) 相遇：2+2 = 4 步。✅ 答案 B
排除法：A 2 是单方向层数；C/D 无依据。
关联 · D1 双向 BFS 思想：相遇拼路径。
// 双向 BFS 同 K3，输出相遇时正反两方向已扩展的层数
单选题：程序输出是？
考点：两方向层数（K4）。
解析：正向 2 层、反向 2 层相遇。✅ 答案 A
排除法：B 1 层未相遇；C/D 不对称错。
关联 · K3：层数即步数的一半。
01// 双向 BFS 扩展状态 u（正向）时： 02if (______) { // 反向已访问过 u → 相遇 03 return dist1[u] + dist2[u]; 04}
单选题：横线处应填入？
考点：相遇判断（K5）。
解析：反向已访问过 u → vis2.count(u) 成立即相遇。✅ 答案 C
排除法：A 查自己方向；B/D 语义错。
关联 · D7 哈希判重：两方向标记。
// {2,3,5} 的子集和 ≤ 7 的子集数：0、2、3、5、2+3、2+5 → 共 6 个（7 以内的和）
单选题：程序输出是？
考点：子集和 ≤ 容量（K6）。
解析：{2,3,5} 子集和：0,2,3,5,5,7,8,10，≤7 的有 6 个。✅ 答案 A
排除法：B 5 漏空集；C 7 含 8；D 8 全数。
关联 · D5 例题：背包类 MITM。
// MITM 综合：半 A = {2,3} 排序后 {0,2,3,5}，半 B = {5,7}，求子集和为 10 的方案数
// 输出半 A 排序结果与方案数
单选题：程序输出是？
考点：MITM 完整流程（K7）。
解析：半 A 排序 {0,2,3,5}，配对 5+5 与 3+7 → 方案数 2。✅ 答案 B
排除法：A 1 漏一种；C 混入 7；D 无依据。
关联 · K1/K2：合并输出。
// 5x5 空网格，(1,1) 到 (5,5)，A* 用曼哈顿估价（可采纳） // 最短路长度 = 4 + 4 = 8
单选题：程序输出是？
考点：A* 空网格（L1）。
解析：5x5 空网格最短路 = 4+4 = 8（曼哈顿直达）。✅ 答案 D
排除法：A 4 单方向；B/C 无依据。
关联 · E1 A 思想*：f=g+h 引导。
01#include <bits/stdc++.h> 02using namespace std; 03int main() { 04 int x1 = 1, y1 = 1, x2 = 5, y2 = 5; 05 cout << abs(x1 - x2) + abs(y1 - y2); // 曼哈顿距离 06 return 0; 07}
单选题：程序输出是？
考点：曼哈顿距离（L2）。
解析：|1-5| + |1-5| = 8。✅ 答案 C
排除法：A 4 单方向；B 16 是乘；D 无依据。
关联 · E4 启发式设计：曼哈顿即 h。
// 4x4 网格，(1,1) 到 (4,4)，障碍 (2,2)、(2,3) // A* 最短路：右右右 + 下下下 = 6（绕过障碍不影响步数）
单选题：程序输出是？
考点：障碍不改变最短步数（L3）。
解析：4x4 障碍 (2,2)(2,3) 只挡路不增步——右右右 + 下下下 = 6。✅ 答案 B
排除法：A 4 少算两方向；C/D 无依据。
关联 · L1：A* 绕过障碍。
01struct Node { int g, h; }; 02// 优先队列按 f 值排序： 03bool operator<(Node a, Node b) { return ______ > ______; }
单选题：横线处应填入？（f = g + h，小根堆）
考点：f 值比较（L4）。
解析：小根堆按 f = g + h 比较：a.g + a.h > b.g + b.h。✅ 答案 A
排除法：B 只 g（Dijkstra）；C 只 h（贪心）；D 无意义。
关联 · E1 A 思想*：比较器即核心。
// 2x3 数码（宽 3 为奇数），可解 ⟺ 逆序数为偶数
// 局面 {1,2,3,4,5,0}：逆序数 0（偶）→ 可解
单选题：程序输出是？
考点：逆序数判可解（L5）。
解析：宽 3（奇）→ 可解 ⟺ 逆序数偶。{1,2,3,4,5,0} 逆序 0 → YES。✅ 答案 A
排除法：B 误判；C/D 不是输出。
关联 · F5 状态压缩搜索：数码类判据。
// 3x3 网格 A*，(1,1) 到 (3,3)：目标处 g = 4、h = 0、f = 4
单选题：程序输出是？
考点：目标处三值（L6）。
解析：3x3 目标 (3,3)：g = 4（走 4 步）、h = 0（已到）、f = 4。✅ 答案 D
排除法：A/B/C 顺序或值错。
关联 · L4：f = g + h 实例。
// 4x4 数独（2x2 宫）： // 1 . 3 . // . 3 . 1 // 2 . 4 . // . 4 . 2 // 回溯搜索唯一解后输出第 2 行第 1 列
单选题：程序输出是？
考点：4x4 数独回溯（M1）。
解析：唯一解第 2 行 = 4 3 2 1 → r2c1 = 4。✅ 答案 B
排除法：A 2 是 r2c3；C/D 无依据。
关联 · F4 数独思想：三约束剪枝。
// 1~3 全排列按字典序：123、132、213、231、312、321 // 输出第 3 个排列
单选题：程序输出是？
考点：字典序第 3 个排列（M2）。
解析：123、132、213、... → 第 3 个 2 1 3。✅ 答案 C
排除法：A 是第 2 个；B 是第 4 个；D 是第 6 个。
关联 · F1 排列生成：字典序枚举。
// 5 选 3 组合按字典序：123、124、125、134、... // 输出第 3 个组合
单选题：程序输出是？
考点：字典序第 3 个组合（M3）。
解析：123、124、125 → 第 3 个 1 2 5。✅ 答案 A
排除法：B 是第 2 个；C 是第 4 个；D 是第 1 个。
关联 · F2 组合生成：字典序枚举。
01for (int x = 1; x <= 4; x++) { 02 if (______) continue; // 行/列/宫已有数字 x 03 row[r][x] = col[c][x] = blk[b][x] = 1; 04 a[r][c] = x; 05 dfs(next); 06 row[r][x] = col[c][x] = blk[b][x] = 0; 07}
单选题：横线处应填入？
考点：三约束剪枝（M4）。
解析：行/列/宫任一已有 x 就跳过：row[r][x] || col[c][x] || blk[b][x]。✅ 答案 D
排除法：A 只查行；B 语义反；C 只判等于 0 漏了另两维。
关联 · M1：填空即剪枝行。
01#include <bits/stdc++.h> 02using namespace std; 03long long memo[100]; 04long long fib(int n) { 05 if (n <= 1) return n; 06 if (memo[n] != -1) return memo[n]; // 记忆化查表 07 return memo[n] = fib(n - 1) + fib(n - 2); 08} 09int main() { 10 memset(memo, -1, sizeof memo); 11 cout << fib(10); 12 return 0; 13}
单选题：程序输出是？
考点：记忆化查表（M5）。
解析：fib(10) = 55，memo 使每个 n 只算一次。✅ 答案 C
排除法：A 34 是 fib(9)；B 89 是 fib(11)；D 21 是 fib(8)。
关联 · F6 记忆化应用：查表避免重复。
// 数独同 M1，输出第 2 行第 3 列（解为 2）
单选题：程序输出是？
考点：同一数独另一格（M6）。
解析：r2c3 = 2（第 2 行 4 3 2 1）。✅ 答案 A
排除法：B 4 是 r2c1；C/D 无依据。
关联 · M1：同一唯一解。
// {1,2,3,4} 的子集和为 5 的方案数：{1,4}、{2,3} → 2
单选题：程序输出是？
考点：子集和 5（N1）。
解析：{1,2,3,4} 和为 5：{1,4}、{2,3} → 2。✅ 答案 B
排除法：A 1 漏；C/D 无依据。
关联 · I6：同法换数据。
// 链 1-2-3-4，目标 4（深度 3），IDDFS 找到后输出 maxdep
单选题：程序输出是？
考点：链上 IDDFS（N2）。
解析：链 1-2-3-4 目标 4 深度 3 → 输出 3。✅ 答案 D
排除法：A/B 深度不够；C 4 是编号。
关联 · J5：同题回顾。
// {2,3,5,7} 折半搜索求子集和为 10 的方案数
单选题：程序输出是？
考点：折半搜索（N3）。
解析：{2,3,5,7} 拆 {2,3}（和 {0,2,3,5}）与 {5,7}（和 {0,5,7,12}），配出 10 的组合：5+5 与 3+7 → 2 种。✅ 答案 C
排除法：A 1 漏了 3+7 或 5+5 之一；B/D 无依据。
关联 · K1：同题回顾。
// 5x5 空网格 (1,1) 到 (5,5)，A* 输出最短路长度
单选题：程序输出是？
考点：A* 空网格（N4）。
解析：5x5 空网格 (1,1)→(5,5)：向右 4 步向下 4 步，最短路 8，A* 用曼哈顿估价（可采纳）正确求得。✅ 答案 D
排除法：A 4 只算单方向；B/C 无依据。
关联 · L1：同题回顾。
01int h(int x1, int y1, int x2, int y2) { 02 return ______; // 曼哈顿估价 03}
单选题：横线处应填入？
考点：曼哈顿估价式（N5）。
解析：abs(x1-x2) + abs(y1-y2)。✅ 答案 A
排除法：B 是乘；C/D 无绝对值。
关联 · E4 启发式设计：填空即 h。
// 3x3 网格 (1,1) 到 (3,3)，双向 BFS 输出总步数
单选题：程序输出是？
考点：双向 BFS（N6）。
解析：3x3 网格：正向从 (1,1) 走 2 层到 {(1,3),(2,2),(3,1)}，反向从 (3,3) 走 2 层到同集合，在 (2,2) 相遇，总步数 2+2 = 4。✅ 答案 B
排除法：A 2 是单方向层数；C/D 无依据。
关联 · K3：同题回顾。
01void dfs(int dep) { 02 if (dep > n) { 输出; return; } 03 for (int i = 1; i <= n; i++) { 04 if (①) continue; // i 已用过 05 vis[i] = 1; 06 a[dep] = i; 07 dfs(dep + 1); 08 vis[i] = 0; 09 } 10}
单选题：①处应填？
考点：访问标记（O1）。
解析：i 已用过 → vis[i] 为真则 continue。✅ 答案 B
排除法：A/C 是"未用过"语义（反了）；D 无依据。
关联 · I2 排列：填空即核心行。
01void dfs(int dep, int cnt) { 02 if (①) return; // 最优性剪枝 03 if (到目标) { ans = cnt; return; } 04 ... 05}
单选题：①处应填？
考点：最优性剪枝（O2）。
解析：cnt >= ans 不可能更优 → return。✅ 答案 C
排除法：A/B 方向反；D 无意义。
关联 · I5：同空再考。
01bool dfs(int u, int dep, int maxdep) { 02 if (u == target) return true; 03 if (dep == maxdep) return false; 04 for (int v : g[u]) 05 if (dfs(v, ①, maxdep)) return true; 06 return false; 07}
单选题：①处应填？
考点：递归加深（O3）。
解析：往下一层递归时深度加 1：dep + 1。✅ 答案 A
排除法：B dep 不加深会死循环；C 反向减；D 传错参数。
关联 · J4：同函数两空。
01// 正向扩展出状态 u： 02if (①) return dist1[u] + dist2[u]; // 反向已访问 → 相遇
单选题：①处应填？
考点：相遇检测（O4）。
解析：反向已访问 → vis2.count(u)。✅ 答案 D
排除法：A 查自己方向；B/C 语义错。
关联 · K5：同空再考。
01// 优先队列按 f = g + h 从小到大： 02priority_queue<Node, vector<Node>, greater<Node>> q; 03struct Node { int g, h; }; 04bool operator>(Node a, Node b) { return ① > ②; }
单选题：①、②处应填？
考点：f 值比较（O5）。
解析：a.g + a.h > b.g + b.h。✅ 答案 B
排除法：A 只 g；C 只 h；D 无意义。
关联 · L4：同空再考。
01for (int s2 : halfB) { 02 // 与 s2 配对成 target 的 halfA 值： 03 int need = ①; 04 cnt += upper_bound(halfA.begin(), halfA.end(), need) 05 - lower_bound(halfA.begin(), halfA.end(), need); 06}
单选题：①处应填？
考点：配对值（O6）。
解析：与 s2 配成 target 需 target - s2。✅ 答案 C
排除法：A/B/D 算术错。
关联 · D6 状态合并：二分查配对。
01long long f(int n) { 02 if (n <= 1) return n; 03 if (①) return memo[n]; // 已算过直接返回 04 return memo[n] = f(n - 1) + f(n - 2); 05}
单选题：①处应填？
考点：查表判断（O7）。
解析：已算过（memo ≠ -1）直接返回。✅ 答案 A
排除法：B 是"没算过才返回"；C/D 无依据。
关联 · M5：同函数填空。
01// 子集和 {2,3,5,7} 目标 10，但可行性剪枝写反了： 02void dfs(int i, int sum) { 03 if (sum < target) return; // 注意：写成了"小于就剪"（应为大于才剪） 04 if (i > n) { if (sum == target) cnt++; return; } 05 dfs(i + 1, sum + a[i]); 06 dfs(i + 1, sum); 07} 08// 从 sum = 0 出发立刻被剪 → 一个解都找不到
单选题：程序输出是？（正确结果应为 2）
考点：剪枝反丢解（P1）。
解析：sum < target 就返回——从 sum=0 出发立刻被剪，输出 0（正确 2）。✅ 答案 A
排除法：B 2 是正确结果；C/D 无依据。
关联 · H1 剪枝过度：概念对应实证。
01// 4x4 迷宫，(1,1) 到 (2,4)，障碍 (2,2)、(2,3)；方向顺序 D,R,U,L 02// 最优性剪枝写反：if (cnt < ans) return;（应为 cnt >= ans 才剪） 03// ans 初值 INF → 第一个找到的解（8 步）就被当作答案 04// 正确最短路 = 4（右右右下）
单选题：程序输出是？（正确结果应为 4）
考点：剪枝反得非最优（P2）。
解析：DFS 方向序 D,R,U,L 先走远路（8 步），cnt < ans 剪枝让首个解即答案——输出 8（正确 4）。✅ 答案 D
排除法：A 4 是正确结果；B/C 无依据。
关联 · H1/B2：剪枝反的另一面。
// 链 1-2-3-4，目标 4（深度 3），IDDFS 但 vis 数组在每轮之间没有清零： // maxdep=0 访问 1 并标记；maxdep=1 想走 1→2 但 1 已标记……逐轮都被卡住 // 所有轮次都失败 → 输出 -1
单选题：程序输出是？（正确结果应为 3）
考点：vis 不清零漏解（P3）。
解析：vis 跨轮不清——后续轮次从 1 出发被标记挡住，全失败输出 -1（正确 3）。✅ 答案 B
排除法：A 3 是正确结果；C/D 无依据。
关联 · H3 迭代加深漏判：概念对应实证。
// {2,3,5,7} 拆 {2,3} 与 {5,7}，求子集和为 10 的方案数
// halfA = {0,2,3,5} 但排序比较器写反，排成了降序 {5,3,2,0}
// lower_bound/upper_bound 要求升序——在降序数组上二分全部落空
// 输出 0
单选题：程序输出是？（正确结果应为 2）
考点：降序二分落空（P4）。
解析：halfA 排成降序 {5,3,2,0}——lower/upper_bound 要求升序，二分全部落空，输出 0（正确 2）。✅ 答案 C
排除法：A 2 是正确结果；B/D 无依据。
关联 · D6 状态合并：排序方向是前提。
// 3x3 网格，(1,1) 到 (3,3)，障碍 (2,3)；只用 h（曼哈顿）贪心、不回退： // (1,1)→(1,2) h=3 →(1,3) h=2 →(2,3) 被挡、(1,2) 已访问 → 死路 // 贪心无路可走 → 输出 -1 // 正确最短路 = 4（下下右右）
单选题：程序输出是？（正确结果应为 4）
考点：无回溯贪心死路（P5）。
解析：只用 h 不回退：走到 (1,3) 被障碍 (2,3) 挡住、邻居全访问过 → 死路输出 -1（正确 4）。✅ 答案 A
排除法：B 4 是正确结果；C/D 无依据。
关联 · E1 A 思想*：g 项保证"能回头"，h 项提供方向。
判断题：以下五种易错写法都会导致程序出错——①可行性剪枝写反（解全被剪）②最优性剪枝写反（首个解即答案、非最优）③IDDFS 每轮不清 vis（逐轮卡死漏解）④MITM 半数组排成降序就二分（查找落空）⑤只用 h 贪心不回退（陷入死路）。
考点：五种易错综合判断（P6）。
解析：五条全对——剪枝反丢解、最优性反非最优、IDDFS 不清 vis 漏解、MITM 降序二分落空、只 h 贪心死路。✅ 正确
排除法：无（判断题）。混淆点：每条对应 P1~P5 一道实证题。
关联 · P1~P5：易错清单自查。