下面哪个说法最符合算法竞赛里「搜索」这个词的含义？
规则：算法课里的「搜索」指在状态空间中系统枚举所有可能，是穷举的规律化升级，不是数组查找，也不是碰运气。
考点：搜索的基本含义。
解析：搜索把问题建模成「状态 + 决策」：从初始状态出发，一步步做决策进入新状态，把所有可能的决策序列都走一遍。遇到走不通的分支（死路）就回到上一个分叉点换一条路，这就是回溯。因为把所有可能性都考虑过，所以答案不会漏；代价是可能很慢。
排除法：「随机碰运气」没有系统性，不能保证找全；「在有序数组里找数」是查找/二分，属于数据结构检索，不是状态空间搜索；「公式直接算」是递推或数学做法，不是搜索。
不加错误剪枝的暴力搜索「保证不遗漏正确答案」的根本原因是什么？
规则：搜索树的叶子覆盖全部可能结果，暴力搜索把它们全部访问一遍，所以任何解都在其中。
考点：搜索的完备性。
解析：从根到每个叶子是一条完整的决策序列，所有叶子合起来就是「所有可能」。只要不错误剪枝，解必然作为某个叶子被访问到——这是搜索正确性的根源。代价是叶子数可能是指数级。
排除法：「编译器自动检查」没有这回事；「只访问正确分支」是剪枝后的行为，暴力搜索不挑分支；「访问更少状态」是优化的结果，不是完备性的原因。
有人把「搜索」理解成「随机挑几个方案试一试」。为什么搜索必须是「有组织地枚举」，而不是随机尝试？
01int tries = 0; 02while (tries < 100) { 03 int p = rand() % N; 04 if (valid(p)) { cout << p << endl; return 0; } 05 tries++; 06}
规则：随机尝试不构成覆盖——它不保证遍历全部状态，可能永远错过解；系统枚举以「不重不漏」为组织原则。
考点：搜索「有组织」的含义。
解析：随机抽样重复尝试，除非恰好把所有方案都试过，否则没有任何「考虑完全」的保证。搜索树逐分支枚举，从根到叶覆盖每条决策路径，「保证正确」靠的就是这个系统性和完整性。竞赛题要求确定性正确，所以必须用系统枚举；随机只能当概率做法。
排除法：「随机更快」——快但没有正确性保证，两者不兼得；「不需要定义状态」——随机同样要判断方案是否合法，也要定义状态；「编译器优化」没有这回事。
一棵「每层做一次二选一决策」的搜索树，从根出发做 3 次决策，一共会得到多少种不同的结果（叶子）？
规则： 个叶子。
考点：搜索树叶子数 = 分支数的「深度」次方（）。
解析：每次决策有 2 个选择，3 次决策形成 3 层满二叉搜索树，叶子数 。推广：每层 个分支、深度 ，叶子数 。
排除法： 是把 当成总数（加法而非连乘）； 是 （方向弄反）； 是 （多做了一层决策）。
枚举时每层可选项数递减：全排列问题（，5 个不同数字排成一列）的叶子数是？子集问题（，每个元素选或不选）的叶子数是？
规则：全排列 （每层可选数递减）；子集 （每层固定两个分支）。
考点：排列与子集的搜索树规模。
解析：全排列第 1 位有 5 个选择、第 2 位剩 4 个……共 。子集对每个元素做「取/不取」二选一，。两种搜索树形状不同：排列是「选择数逐层递减」，子集是「每层两个分支」。
排除法： 是「每位 5 选 1 的重复排列」，不是不重复的全排列； 是 ，不是子集总数；选项 4 把两者的顺序颠倒了。
一个搜索树每层有 3 个分支，深度为 4（从根到叶做 4 次决策），叶子数是多少？
规则： 个叶子。
考点： 计算。
解析：每层 3 个分支，4 层连乘：。
排除法：（分支与深度对调）；（少算一层）；（把连乘当乘法）。
下面哪个问题需要把状态「抽象成隐式状态空间」来做搜索？
规则：显式图搜索在「已经给出的图」上进行；隐式状态空间搜索要自己定义状态与转移。
考点：显式图与隐式图。
解析：倒水问题没有现成的图——每个状态是 两壶水量，转移是灌满/倒空/倒入六种操作，节点和边都要自己枚举出来，是典型的隐式状态空间。图的连通分量（选项 1）在显式图上搜索。
排除法：邻接矩阵图是显式的；数组查找与链表遍历是线性结构操作，不属于状态空间搜索。
倒水问题：一个 3 升壶和一个 5 升壶，状态就是当前水量组合 —— 是 3 升壶里的水量（取 0~3）， 是 5 升壶里的水量（取 0~5）。不管按什么顺序倒，只要两壶水量一样，接下来能做的倒法就完全一样。BFS 把每个到过的 编码进标记数组，整个搜索长这样：
01#include <bits/stdc++.h> 02using namespace std; 03 04int key(int x, int y) { return x * 6 + y; } 05bool vis[24]; 06queue<pair<int, int>> q; 07 08void push(int x, int y) { 09 if (!vis[key(x, y)]) { 10 vis[key(x, y)] = true; 11 q.push({x, y}); 12 } 13} 14 15int main() { 16 push(0, 0); 17 while (!q.empty()) { 18 pair<int, int> u = q.front(); 19 q.pop(); 20 int x = u.first, y = u.second; 21 push(3, y); push(x, 5); 22 push(0, y); push(x, 0); 23 push(max(0, x + y - 5), min(5, x + y)); 24 push(min(3, x + y), max(0, x + y - 3)); 25 } 26}
为什么搜索要盯住「状态」把它抽象成节点来判重（push 里用 vis[key] 拦住重复），而不是直接盯着「倒水操作序列」往下搜？
规则：状态 = 决定「接下来还能怎么倒」的最小信息（两壶各剩多少）；同一状态可由不同操作序列到达，判重让每个状态只展开一次。
考点：把问题状态抽象成节点的意义（判重的前提）。
解析：状态 （两壶全满）：先灌满 3 升壶再灌满 5 升壶能到，先灌满 5 升壶再灌满 3 升壶也能到——操作序列千千万，局面总共只有 种。盯着「操作序列」搜，同一个局面会被反复展开、反复排队，搜索量指数爆炸；上面代码的 push 第一行就用 vis[key(x, y)] 拦住「来过的局面」——重复状态连队列都进不去，每个状态最多入队一次；六种倒法只管枚举转移，判重全权交给标记数组。显式图的节点是题目给的，倒水这类隐式图的状态要自己定义——把状态找对、编成下标判重，正是搜索建模的第一步。
排除法：节点/状态关乎正确性与效率，「画图好看」无关；显式图的访问标记同样是状态判重，并非「只有隐式图才需要」；判重只多开 24 格数组，换来搜索量从爆炸降到最多 24 次展开，是最大的提速而不是拖慢。
搜索树规模是指数级的，为什么竞赛题还是大量使用搜索？
规则：指数复杂度在小数据规模 + 剪枝下可承受；搜索还常作为正确性对照（暴力对拍）。
解析：、 都在 量级的预算内；再配合剪枝，可承受的规模还能更大。此外搜索代码「从定义直接翻译」，不易写错，适合与更优算法对拍验证正确性。
排除法：「编译器优化成多项式」没有这回事；「永不超时」——不剪枝时 的全排列约 4.8 亿个叶子，照样超时；「唯一合法」——很多题有更优算法，搜索是备选与兜底。
关于搜索树，下面哪个说法正确？
规则：搜索树 = 状态作节点、决策作边；根到叶路径 = 一个完整方案；叶子是否「解」取决于是否满足目标条件。
解析：搜索树完整表达所有决策序列。有的叶子是合法解（满足目标），有的叶子是死路（比如走到一半发现所有数字都用光了却不满足要求）。深度 = 决策步数，与状态总数无关。
排除法：「叶子必然正确」——死路叶子不是解；「一定是满二叉」——分支数由每步可选项决定，可以是 3 叉、递减分支；「深度 = 状态数」——深度是决策步数，同一层可以有很多状态。
已知状态数有 个且没有剪枝手段，直接用搜索求答案，后果是什么？
规则：搜索的可行上限约 状态量级（含每状态常数）；超出且无剪枝/无结构 → 超时，应换算法。
解析： 个状态，即便每秒访问 个也要上万秒，远超 1 秒时限。这是「搜索不可行」的典型信号：状态空间巨大、又没有可剪枝的约束结构时，搜索不再适用，应换 DP、贪心或找规律。
排除法：「只是慢几分钟」——不是几分钟，是数量级超时；「自动跳过」——不写剪枝代码搜索不会自己偷懒；「输出错误答案」——这是 TLE（超时），不是 WA（答案错）。
一个搜索树每层 2 个分支、深度 10 时叶子数是 。若每层 3 个分支、深度 6，叶子数是？
规则： 个叶子。
考点： 计算。
解析：每层分支数连乘，。
排除法：（连乘当成乘法）；（用了 2 个分支）；（分支与深度对调）。
DFS（深度优先搜索）借助什么结构保证「先深入、后回退」？
规则：DFS = 递归 = 系统栈（LIFO）：先沿一条路走到最深处，再逐层返回。
考点：DFS 与递归/栈的对应。
解析：递归调用 dfs(k+1) 时当前层的信息压栈，最深层最先返回——这个「后进先出」正好实现「先深入到底、再回溯」。BFS 才用队列。
排除法：「队列」是 BFS；「哈希表」用于判重，不是遍历顺序的控制结构；「数组下标跳转」不是结构化的深度优先。
全排列问题：把 的每个数选恰好一次，按字典序输出全部排列。把下面代码里的恢复行 used[i] = false; 删掉，对 运行，输出什么？
01int a[10]; bool used[10]; int n; 02void dfs(int k) { 03 if (k == n) { 04 for (int i = 0; i < n; i++) cout << a[i]; 05 cout << endl; 06 return; 07 } 08 for (int i = 1; i <= n; i++) { 09 if (used[i]) continue; 10 a[k] = i; 11 used[i] = true; 12 dfs(k + 1); 13 } 14}
规则：不恢复现场，used 里的标记残留，后面的分支能选的数字变少，排列残缺。
解析：追踪：dfs(0) 先选 1（used[1]=true）→ dfs(1) 只能选 2 → 输出 12 → 返回后 used[2] 仍为 true；回到 dfs(0) 的第二个分支 i=2 时，used[2] 还是 true，continue 跳过，第 1 位只有 1 一种可能。所以只输出 12。死循环不会发生（used 不会重置，循环能正常结束）。
排除法：「输出两行」没看到残留标记的影响；「死循环」——循环条件正常，是输出不全不是死循环；「11、22」——used 防止重复选同一数字，非法排列不会出现。
全排列代码里的 used[i] = false;（恢复现场）为什么不能删？
01int a[10]; bool used[10]; int n; 02void dfs(int k) { 03 if (k == n) { 04 for (int i = 0; i < n; i++) cout << a[i]; 05 cout << endl; 06 return; 07 } 08 for (int i = 1; i <= n; i++) { 09 if (used[i]) continue; 10 a[k] = i; 11 used[i] = true; 12 dfs(k + 1); 13 used[i] = false; 14 } 15}
规则：used[] 描述的是「当前递归路径上已占用的数字」，是路径状态不是全局状态——回溯时必须撤销，让同层的兄弟分支看到干净的选择。
考点：回溯三件套里的「恢复现场」。
解析：dfs(0) 第一个分支选 1（used[1]=true），深入生成全部以 1 开头的排列后返回；若不恢复，进入第二个分支（以 2 开头）时 used[1] 仍是 true，第 1 位就选不了 1——排列整体残缺（如 只剩 12）。恢复现场让每个分支从相同的「什么都没选」出发，是排列完整的保证。
排除法：「数字重复出现」——不恢复不是重复，是残留标记导致可选变少、残缺；「为了提速」——恢复是正确性操作，多一行开销可忽略；「清空数组」——恢复是撤销单次选择，不是整体清零。
对 运行全排列程序，按字典序输出的第 4 个排列是什么？
01int a[10]; bool used[10]; int n; 02void dfs(int k) { 03 if (k == n) { 04 for (int i = 0; i < n; i++) cout << a[i]; 05 cout << endl; 06 return; 07 } 08 for (int i = 1; i <= n; i++) { 09 if (used[i]) continue; 10 a[k] = i; 11 used[i] = true; 12 dfs(k + 1); 13 used[i] = false; 14 } 15}
规则：字典序全排列：123, 132, 213, 231, 312, 321，第 4 个是 231。
考点：全排列输出顺序追踪。
解析：for 从小到大取数字，深搜先左后右：以 1 开头的两个（123、132）先生成，再以 2 开头（213、231），再以 3 开头。第 4 个是 231。
排除法：132 是第 2 个；213 是第 3 个；312 是第 5 个。
时全排列程序一共输出多少行？
01int a[10]; bool used[10]; int n; 02void dfs(int k) { 03 if (k == n) { 04 for (int i = 0; i < n; i++) cout << a[i]; 05 cout << endl; 06 return; 07 } 08 for (int i = 1; i <= n; i++) { 09 if (used[i]) continue; 10 a[k] = i; 11 used[i] = true; 12 dfs(k + 1); 13 used[i] = false; 14 } 15}
规则： 行。
考点：全排列个数。
解析：。每行一个排列。
排除法：、、 都不是 。
补全全排列的两处空缺：进入分支前要 ____ 让下一层不再选它，递归返回后要 ____ 让同层其他分支还能用它。
01int a[10]; bool used[10]; int n; 02void dfs(int k) { 03 if (k == n) { for (int i = 0; i < n; i++) cout << a[i]; cout << endl; return; } 04 for (int i = 1; i <= n; i++) { 05 if (used[i]) continue; 06 a[k] = i; 07 used[i] = ____; 08 dfs(k + 1); 09 used[i] = ____; 10 } 11}
规则：标记用 true（已占用），恢复用 false（释放）。
考点：回溯三件套的标记/恢复取值。
解析：进入分支前 used[i] = true 告诉下层「i 已被选」；递归返回后 used[i] = false 撤销，同层下一个分支才能再用 i。这两个值的设定正是「标记 → 递归 → 恢复」。
排除法：false；true 顺序写反，下层不会排除当前数字；true；true 等于从不恢复；1；2 不是布尔语义，used 判断 if (used[i]) 会把 1、2 都当真。
为什么 used[i] = true; 必须放在 dfs(k + 1); 调用之前？
01for (int i = 1; i <= n; i++) { 02 if (used[i]) continue; 03 a[k] = i; 04 used[i] = true; 05 dfs(k + 1); 06 used[i] = false; 07}
规则：标记的语义是「从现在起本数字已被占用」，必须在深入之前生效；下层递归靠它排除当前数字。
解析：若把 used[i] = true 放到 dfs(k+1) 之后，进入下层时 used[i] 还是 false，下层 for 循环到 i 时 if (used[i]) continue 不触发，会把 i 再选一次——排列里出现重复数字。标记顺序写错等于「自环」。
排除法：语法合法，是逻辑错不是编译错；顺序有本质区别；与输出速度无关。
全排列循环里误加了一行 return;，对 运行会怎样？
01int a[10]; bool used[10]; int n; 02void dfs(int k) { 03 if (k == n) { for (int i = 0; i < n; i++) cout << a[i]; cout << endl; return; } 04 for (int i = 1; i <= n; i++) { 05 if (used[i]) continue; 06 a[k] = i; 07 used[i] = true; 08 dfs(k + 1); 09 used[i] = false; 10 return; 11 } 12}
规则：return 提前结束整个函数，for 循环剩下的分支不再执行——每层只走第一个可用数字。
解析：dfs(0) 选 i=1 后深入：dfs(1) 选 2、dfs(2) 选 3，输出 123。返回时每层的 return 让 for 循环立刻结束：dfs(2) 不试 i 的其他值（本来也没了）、dfs(1) 不再试 3、dfs(0) 不再试 2 和 3。所以只输出 123。
排除法：「没有影响」忽略 return 的存在；「死循环」——递归正常收敛，只是分支被截断；「顺序颠倒」——不是顺序问题，是数量丢失。
为什么全排列的输出是字典序（123、132、213…）而不是随机顺序？
01int a[10]; bool used[10]; int n; 02void dfs(int k) { 03 if (k == n) { 04 for (int i = 0; i < n; i++) cout << a[i]; 05 cout << endl; 06 return; 07 } 08 for (int i = 1; i <= n; i++) { 09 if (used[i]) continue; 10 a[k] = i; 11 used[i] = true; 12 dfs(k + 1); 13 used[i] = false; 14 } 15}
规则：字典序 = 深度优先 + 每层按数字从小到大：先穷尽「以 1 开头」的分支，再「以 2 开头」……
解析：dfs(0) 的 for 先选 i=1，递归生成全部以 1 开头的排列（123、132），返回后再选 i=2 生成 213、231……这就是字典序的定义。若把 for 改成从 n 到 1 倒序，输出就是逆字典序。
排除法：「编译器排序」没有这回事；used 只防重复、不决定顺序；顺序由 for 方向完全决定，与电脑无关。
把全排列程序里的选择顺序反过来，输出顺序会怎样？
01for (int i = n; i >= 1; i--) { 02 if (used[i]) continue; 03 a[k] = i; 04 used[i] = true; 05 dfs(k + 1); 06 used[i] = false; 07}
规则：搜索顺序反过来，输出顺序就反过来；排列个数不变。
考点：搜索顺序与输出顺序。
解析：第 1 位从最大数 n 开始尝试，先输出所有以 n 开头的排列……整体是逆字典序。个数仍是 。
排除法：顺序必然改变；个数与顺序无关；只是逻辑顺序变化，语法合法。
用「交换写法」生成全排列与用「标记数组写法」相比，正确的是？
01void perm(int k) { 02 if (k == n) { for (int i = 0; i < n; i++) cout << a[i]; cout << endl; return; } 03 for (int i = k; i < n; i++) { 04 swap(a[k], a[i]); 05 perm(k + 1); 06 swap(a[k], a[i]); 07 } 08}
规则：两种写法生成同一个集合，只是顺序不同；交换写法靠「交换回来」实现恢复现场。
解析：标记写法用 used 控制「数字还没用过」；交换写法把当前位 a[k] 与后面某个位置交换，递归后再换回——「换回」就是它的恢复现场。两者都生成全部排列，但交换写法的输出次序不是字典序（如 {1,2,3} 输出 123,132,213,231,321,312）。
排除法：结果集相同不漏；不是字典序；swap 后必须换回，否则下一分支出错。
为什么「交换写法」对 a = {1, 2, 3} 的输出不是字典序？
01void perm(int k) { 02 if (k == n) { for (int i = 0; i < n; i++) cout << a[i]; cout << endl; return; } 03 for (int i = k; i < n; i++) { 04 swap(a[k], a[i]); 05 perm(k + 1); 06 swap(a[k], a[i]); 07 } 08}
规则：交换写法的搜索树是「先固定当前位置、再交换产生后续」，与「按数字大小递增」的字典序不同构。
解析：模拟 {1,2,3}：k=0 时先 swap(0,0)（不变，1 开头）→ perm(1) 里 swap(1,1) 得 123、swap(1,2) 得 132；返回后 swap(0,1) 把 2 换到前面 → 213、231；再 swap(0,2) 把 3 换到前面 → 321、312。顺序 123,132,213,231,321,312——312 排最后，字典序里 312 应在 321 前。两个结果集相同，只是次序不同。
排除法：分支没少（仍是 叶子）；时间与顺序无关；编译器不重排输出。
用交换写法跑 a = {1, 2, 3}，输出的序列是？
01void perm(int k) { 02 if (k == n) { for (int i = 0; i < n; i++) cout << a[i]; cout << endl; return; } 03 for (int i = k; i < n; i++) { 04 swap(a[k], a[i]); 05 perm(k + 1); 06 swap(a[k], a[i]); 07 } 08}
规则：交换写法输出 123, 132, 213, 231, 321, 312。
考点：交换写法输出顺序追踪。
解析：k=0 三次循环分别对应「1 开头（perm(1) 内换出 123、132）」「2 开头（213、231）」「3 开头（321、312）」。注意 321 在 312 之前——因为 3 开头时 k=1 先 swap(1,1)（2 在中间 → 321）再 swap(1,2)（2 换到最后 → 312）。
排除法：选项 2 的 312、321 顺序错（字典序才是 312 在前）；选项 3、4 的组内顺序不符合交换过程。
的全排列输出第一个排列 123 的那一刹那，used[1]、used[2]、used[3] 的值分别是？
01int a[10]; bool used[10]; int n; 02void dfs(int k) { 03 if (k == n) { 04 for (int i = 0; i < n; i++) cout << a[i]; 05 cout << endl; 06 return; 07 } 08 for (int i = 1; i <= n; i++) { 09 if (used[i]) continue; 10 a[k] = i; 11 used[i] = true; 12 dfs(k + 1); 13 used[i] = false; 14 } 15}
规则：输出发生在地 k == n 时，此时路径正好用完全部 个数字，used 全为 true。
解析：打印 123 时，dfs(0)、dfs(1)、dfs(2) 分别选了 1、2、3，三个 used 位都是 true。紧接着程序开始回溯：dfs(2) 返回前把 used[3] 置 false，再回 dfs(1) 试下一个分支。
排除法：「只有 3 为 true」忽略了前两层；「全 false」与「1 为 true」都没理解 used 是「路径上已选集合」。
全排列代码里 if (used[i]) continue; 这一行的作用是什么？
01for (int i = 1; i <= n; i++) { 02 if (used[i]) continue; 03 a[k] = i; 04 used[i] = true; 05 dfs(k + 1); 06 used[i] = false; 07}
规则：continue = 不进入该分支，跳过一个确定无效的选择，即分支级剪枝。
考点：剪枝的最小形态。
解析：used[i] 为 true 表示 i 已在当前排列路径上，再选它会重复，这一分支注定非法，直接跳过。所有「跳过非法分支」的 continue/return 都是剪枝。
排除法：剪枝省的是无效工作，不是提速技巧；排序由 for 方向决定；i 的范围 1..n 本来就合法，与越界无关。
「从 个元素里选任意多个」是 种，「正好选 个」是 种。为什么搜索树结构不同？
01void sub(int i) { 02 if (i == n) { print(); return; } 03 in[i] = true; sub(i + 1); in[i] = false; 04 sub(i + 1); 05} 06 07void comb(int cnt, int start) { 08 if (cnt == k) { print(); return; } 09 for (int j = start; j < n; j++) { b[cnt] = j; comb(cnt + 1, j + 1); } 10}
规则：子集搜索树是 n 层满二叉（每元素取/不取）；组合搜索树是深度 k、可选项递减的分支树。
解析：选/不选把每个元素当成一次独立二选一，n 次决策 → 叶子。组合固定选 k 个：第 1 个有 n 种、第 2 个只能从后面的挑（start 从 j+1 开始）……叶子数正好 ，且靠 start 参数避免「12、21」这类重复。
排除法：两种树形状明显不同；选/不选每个元素至多一次，不是 ；组合方案数比子集少，不是更多。
对 运行子集「选/不选」代码，输出顺序是？（元素编号 1、2，空集输出空行）
01int in[10]; int n; 02void sub(int i) { 03 if (i == n) { 04 for (int j = 0; j < n; j++) if (in[j]) cout << j + 1; 05 cout << endl; 06 return; 07 } 08 in[i] = true; sub(i + 1); in[i] = false; 09 sub(i + 1); 10}
规则：每个元素先「取」后「不取」，深度优先 → 12、1、2、空。
解析：sub(0) 先 in[0]=true → sub(1) 先 in[1]=true → 输出 12；恢复后输出 1；回到 sub(0) 走「不取」→ sub(1) 先取 1 → 输出 2；再输出空。顺序：12、1、2、空。
排除法：深度优先先左（取）后右（不取），空集最后输出；其他选项把分支方向或左右次序搞错了。
运行组合代码，一共输出几个组合？前三个是什么？（元素编号 0..3）
01int b[10]; int n, k; 02void comb(int cnt, int start) { 03 if (cnt == k) { print(); return; } 04 for (int j = start; j < n; j++) { b[cnt] = j; comb(cnt + 1, j + 1); } 05}
规则： 个；字典序输出 01、02、03、12、13、23。
解析：第 1 位 0 → 第 2 位 1、2、3 → 01、02、03；第 1 位 1 → 12、13；第 1 位 2 → 23。共 6 个。start 从 j+1 开始保证「后选的大于先选的」，不重复。
排除法： 不是 12 或 4；「05」里 5 超出了编号 0..3。
题目：输入 （），输出 1 到 的全部排列，每行一个，按字典序。
01int a[10]; bool used[10]; int n; 02void dfs(int k) { 03 if (k == n) { 04 for (int i = 0; i < n; i++) cout << a[i]; 05 cout << endl; 06 return; 07 } 08 for (int i = 1; i <= n; i++) { 09 if (used[i]) continue; 10 a[k] = i; 11 used[i] = true; 12 dfs(k + 1); 13 used[i] = false; 14 } 15}
n=3 时程序输出几行？
（1 分）n=3 时第 2 行输出什么？
（1 分）为什么递归返回后要 used[i] = false;？
n=1 时程序输出什么？
（1 分）题目：输入 （），输出集合 的全部子集（每个元素选或不选），每行一个子集（元素从小到大，空子集输出空行）。
01int in[10]; int n; 02void sub(int i) { 03 if (i == n) { 04 for (int j = 0; j < n; j++) if (in[j]) cout << j + 1; 05 cout << endl; 06 return; 07 } 08 in[i] = true; sub(i + 1); in[i] = false; 09 sub(i + 1); 10}
n=2 时程序输出几行？
（1 分）n=3 时第一个输出是什么？
（1 分）为什么每个元素两个分支就能覆盖全部子集？
（1 分）n=3 时包含元素 1 的子集有多少个？
（1 分）题目：输入 ，输出从 个元素（编号 0..n-1）中取 个的所有组合，每行一个，元素按从小到大、组合按字典序。
01int b[10]; int n, k; 02void comb(int cnt, int start) { 03 if (cnt == k) { 04 for (int i = 0; i < k; i++) cout << b[i]; 05 cout << endl; 06 return; 07 } 08 for (int j = start; j < n; j++) { 09 b[cnt] = j; 10 comb(cnt + 1, j + 1); 11 } 12}
n=4, k=2 时程序输出几行？
（1 分）为什么下一层要从 j + 1 开始而不是 start？
k=0 时程序输出什么？
（1 分）广度优先搜索（BFS）一定需要用到的数据结构是？
规则：BFS 用队列（FIFO）保存待访问状态，先入先出实现「逐层推进」。
考点：BFS 与队列的对应。
解析：BFS 每层把「下一层所有状态」排队，按到达顺序逐一出队扩展，天然是先进先出 → 队列。栈的 LIFO 会变成深度优先。
排除法：「栈」是 DFS 的载体；「二叉树」「哈希表」不是遍历顺序的控制结构。
BFS 为什么能一层一层地推进？看下面这段 BFS 主循环：
01#include <iostream> 02#include <queue> 03#include <vector> 04using namespace std; 05vector<int> adj[105]; 06int dist[105]; 07void bfs(int start) { 08 for (int i = 0; i < 105; i++) dist[i] = -1; 09 dist[start] = 0; 10 queue<int> q; 11 q.push(start); 12 while (!q.empty()) { 13 int u = q.front(); 14 q.pop(); 15 for (int v : adj[u]) 16 if (dist[v] == -1) { 17 dist[v] = dist[u] + 1; 18 q.push(v); 19 } 20 } 21}
规则：队列先进先出（FIFO）保证「先被发现的先被扩展」——dist 值小的先入队、先出队，第 层全部扩展完才轮到第 层。
考点：BFS 按层推进的机制。
解析：从起点开始：第 0 层入队；出队扩展出的第 1 层邻居排在队尾；第 0 层清空后队头是第 1 层，接着才轮到第 2 层……代码里 dist[v] = dist[u] + 1 让每个状态带着自己的层号入队，先进先出让层号小的永远排在前面，这就是「按层」的机制保证。
排除法：每轮处理一个状态是循环细节，不是分层原因；BFS 顺序确定不随机；队列不排序，靠入队先后天然分层。
为什么 BFS 中第一次访问到目标状态时的层数就一定是最短步数？
01while (!q.empty()) { 02 Node u = q.front(); q.pop(); 03 for (int d = 0; d < 4; d++) { 04 int nx = u.x + dx[d], ny = u.y + dy[d]; 05 if (非法) continue; 06 if (step[nx][ny] != -1) continue; 07 step[nx][ny] = step[u.x][u.y] + 1; 08 q.push({nx, ny}); 09 } 10}
规则：层数单调递增 = 距离单调不减。第一个「发现」目标的层就是最小可达层，即最短步数。
解析：出队顺序按层 0、1、2……严格递增。第 层的所有状态都扩展完，才会扩展第 层。因此一旦某个状态被「发现」（入队标记），它所在层就是能到达它的最小层数——对目标同样成立。
排除法：「每步走最短路径」是结果不是原因；目标多个也不影响（任一个最先被发现都是最短的）；队列不排序，靠层序自然递增。
同样的迷宫，为什么用 DFS 找到终点时路径不一定最短？
01void dfs(int x, int y, int d) { 02 if (x == ex && y == ey) { ans = min(ans, d); return; } 03 for (int k = 0; k < 4; k++) { 04 int nx = x + dx[k], ny = y + dy[k]; 05 if (非法) continue; 06 dfs(nx, ny, d + 1); 07 } 08}
规则：DFS 不按层扩展，第一个到达终点的是「当前搜索路径先走完」的，与最短无关。
解析：DFS 沿着第一条分支一路到底，可能这条路绕远；它不会等「所有第 2 步能到的格子」都试完再去试第 3 步。所以第一次到达终点只是「某条路径先走完」，不是最短路径。要得到最短必须保留 min 或改用 BFS。
排除法：「天生慢」——复杂度同级，是语义差异；「走最短方向」DFS 没有这个保证；「终点访问一次」——DFS 找最短通常要访问多次。
BFS 里 step[nx][ny] != -1 判断（相当于 visited）同时起哪几个作用？
01while (!q.empty()) { 02 Node u = q.front(); q.pop(); 03 for (int d = 0; d < 4; d++) { 04 int nx = u.x + dx[d], ny = u.y + dy[d]; 05 if (非法) continue; 06 if (step[nx][ny] != -1) continue; 07 step[nx][ny] = step[u.x][u.y] + 1; 08 q.push({nx, ny}); 09 } 10}
规则：visited/距离数组三合一：判重（不重复入队）、记步数（顺带就是最短路长度）、防止环导致死循环。
解析：step 初值 -1 表示未访问；不等于 -1 说明到过。它既避免同一个格子被多个邻居重复入队（队列膨胀），又直接存储最短步数，还天然终止了「来回走」的无限循环。
排除法：越界判断是独立的 nx < 0 等条件；判重不是提速小技巧，是正确性必需；路径还原需要额外的 pre 数组，step 只存距离。
为什么 BFS/DFS 遍历图或网格时必须有 visited 标记？以下面的 BFS 为例：
01while (!q.empty()) { 02 Node u = q.front(); q.pop(); 03 for (int d = 0; d < 4; d++) { 04 int nx = u.x + dx[d], ny = u.y + dy[d]; 05 if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; 06 if (g[nx][ny] == '#') continue; 07 step[nx][ny] = step[u.x][u.y] + 1; 08 q.push({nx, ny}); 09 } 10}
规则：判重是遍历的终止性/效率保证——有环结构（或可回头的网格）里，不判重会让状态被反复入队。
解析：去掉 step[nx][ny] != -1 后，从 A 到 B 后，B 的邻居又包含 A，A 再次入队；A 又入队 B……队列长度不收敛。对有限图结果是「无限循环 + 内存爆掉」（等价死循环），不是慢一点。
排除法：这不是效率问题，是终止性问题；与越界无关（越界另有判断）；不是「错误答案但能结束」——它根本结束不了。
BFS 代码里 step[nx][ny] = ...; q.push(...) 是「入队时标记」。若改成「出队时标记」（在 q.pop() 之后才检查/标记），后果是？
01while (!q.empty()) { 02 Node u = q.front(); q.pop(); 03 step[u.x][u.y] = 1; 04 for (int d = 0; d < 4; d++) { 05 int nx = u.x + dx[d], ny = u.y + dy[d]; 06 if (非法) continue; 07 q.push({nx, ny}); 08 } 09}
规则：判重必须在「入队前」完成；拖到出队时判重，重复状态早已被多次入队。
解析：出队时才标记 = 一个格子在被出队之前，它所有邻居都能再次把它入队。网格里一个格子至多 4 个邻居，各自把它入队一次，队列里出现多个副本；副本继续各自扩展，成倍膨胀——搜索量从 膨胀到指数级。正确写法是入队前判重并标记。
排除法：写法有本质区别（指数 vs 线性）；与越界无关；步数本身不错，但队列爆炸 → 超时/内存爆。
在一个 2 格直线迷宫（起点 S 在左格、右边格 E）上运行「没有 visited 标记」的 BFS，会发生什么？
规则：两格互为邻居就是最简单的环：没有判重，互相入队无限循环。
解析：S 出队 → E 入队；E 出队 → S 入队；S 出队 → E 入队……两个状态来回入队，队列永不空。BFS 的「层」概念也被破坏。任何规模网格，去掉判重都这样。
排除法：不判重就找不到「结束」；不会输出正确步数；越界由边界判断管着，这里不越界。
补全网格 BFS：只有「没到过」的格子才扩展，防止重复入队。
01for (int d = 0; d < 4; d++) { 02 int nx = u.x + dx[d], ny = u.y + dy[d]; 03 if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; 04 if (g[nx][ny] == '#') continue; 05 if (____) continue; 06 step[nx][ny] = step[u.x][u.y] + 1; 07 q.push({nx, ny}); 08}
规则：step 初值 -1 表示未访问，判「已访问」则跳过。
解析：step 被初始化为 -1。step[nx][ny] != -1 为真说明到过 → continue。选项 2 恰好写反（等于 -1 才跳过 = 只跳未访问）。
排除法：应检查目标格 [nx][ny] 而不是当前格 [u.x][u.y]；障碍判断已经有单独一行，g[nx][ny] == '.' 会重复且语义错。
3×3 迷宫，S 在 (0,0)，E 在 (2,2)，路径唯一：向右、向下、向右、向下。运行下面的 BFS，step[2][2] 是多少？
01step[sx][sy] = 0; 02queue<Node> q; q.push({sx, sy}); 03while (!q.empty()) { 04 Node u = q.front(); q.pop(); 05 for (int d = 0; d < 4; d++) { 06 int nx = u.x + dx[d], ny = u.y + dy[d]; 07 if (非法) continue; 08 if (step[nx][ny] != -1) continue; 09 step[nx][ny] = step[u.x][u.y] + 1; 10 q.push({nx, ny}); 11 } 12}
规则：路径 4 步（向右、向下、向右、向下），BFS 首达即最短，。
解析：唯一路径长度为 4（4 次移动），首达目标的层数就是 4。
排除法： 是格子的行列差； 是曼哈顿距离的一半； 多算了一步。
网格 BFS 从起点出发，第一轮扩展得到 A、B、C、D 四个邻居入队（按方向数组顺序），第二轮又从 A 扩展到 X。队列当前的顺序是？
01while (!q.empty()) { 02 Node u = q.front(); q.pop(); 03 for (int d = 0; d < 4; d++) { ... q.push({nx, ny}); } 04}
规则：FIFO：先入先出。A 先出队扩展，X 追加到队尾。
解析：初始队列 [A,B,C,D]（按入队顺序）。第一轮循环出 A，X 入队 → [B,C,D,X]。B 下一轮出队。
排除法：「X 在最前」违背 FIFO（后入队的在队尾）；「逆序」是栈的行为；A 已出队不可能还在队列里。
BFS 的时间复杂度是？（V 为状态数、E 为转移数）
01step[sx][sy] = 0; 02queue<Node> q; 03q.push({sx, sy}); 04while (!q.empty()) { 05 Node u = q.front(); q.pop(); 06 for (int d = 0; d < 4; d++) { 07 if (非法) continue; 08 if (step[nx][ny] != -1) continue; 09 step[nx][ny] = step[u.x][u.y] + 1; 10 q.push({nx, ny}); 11 } 12}
规则：每个状态最多入队一次，每个状态的转移（边）被检查一次，合计 。
考点：BFS 复杂度。
解析：判重保证每个状态只入队一次（）；每个状态出队时枚举其邻居（）。合计 ，线性。
排除法： 是稠密图邻接矩阵遍历的极端情形，不是 BFS 一般复杂度；、 都高估了——每条边只被它的起点检查一次。
倒水问题（3 升壶和 5 升壶，每次可灌满、倒空或互相倒，问凑出目标水量最少要几步）：用 BFS 求最少操作数，程序在「出队时」检查 x == c || y == c 并返回层数。起点 (0,0)，目标 c，BFS 第一次弹出满足条件的状态时返回的层数表示什么？
01while (!q.empty()) { 02 int x = q.front().first, y = q.front().second; 03 q.pop(); 04 if (x == c || y == c) return vis[x][y] - 1; 05 ... 06}
规则：BFS 首达即最短，出队时（状态已被按层序发现）第一次命中目标 → 返回的就是最少操作数。
解析：vis 存「发现时的层数」；vis[x][y] - 1 是操作次数（起点记 1）。BFS 层序性保证第一个弹出的目标状态就是最浅的 → 最少操作数。
排除法：BFS 的最短性对隐式状态图同样成立；不是入队总数；不是队列长度。
01#include <iostream> 02#include <queue> 03using namespace std; 04struct Node { int x, y; }; 05int n, m, sx, sy, ex, ey; 06char g[105][105]; 07int step[105][105]; 08const int dx[4] = {-1, 1, 0, 0}; 09const int dy[4] = {0, 0, -1, 1}; 10void bfs() { 11 step[sx][sy] = 0; 12 queue<Node> q; 13 q.push({sx, sy}); 14 while (!q.empty()) { 15 Node u = q.front(); q.pop(); 16 for (int d = 0; d < 4; d++) { 17 int nx = u.x + dx[d], ny = u.y + dy[d]; 18 if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; 19 if (g[nx][ny] == '#') continue; 20 if (step[nx][ny] != -1) continue; 21 step[nx][ny] = step[u.x][u.y] + 1; 22 q.push({nx, ny}); 23 } 24 } 25}
3×4 迷宫，起点 (0,0)、终点 (3,0)，除起点外全部是空地，BFS 后 step[3][0] 是多少？
为什么入队前判重能避免队列膨胀？
（1 分）若方向数组只有 {0,0,1,0} 表示只准向右、向下，起点 (0,0) 终点 (2,2)，step[2][2] 是多少？
判边界为什么必须用 nx < 0 全套四个条件？
01#include <iostream> 02#include <queue> 03using namespace std; 04int a, b, c; 05int vis[105][105]; 06int bfs() { 07 vis[0][0] = 1; 08 queue<pair<int, int> > q; 09 q.push({0, 0}); 10 while (!q.empty()) { 11 int x = q.front().first, y = q.front().second; 12 q.pop(); 13 if (x == c || y == c) return vis[x][y] - 1; 14 int nxt[6][2] = { 15 {a, y}, {x, b}, {0, y}, {x, 0}, 16 {max(0, x - (b - y)), min(b, x + y)}, 17 {min(a, x + y), max(0, y - (a - x))} 18 }; 19 for (int d = 0; d < 6; d++) { 20 int nx = nxt[d][0], ny = nxt[d][1]; 21 if (vis[nx][ny]) continue; 22 vis[nx][ny] = vis[x][y] + 1; 23 q.push({nx, ny}); 24 } 25 } 26 return -1; 27}
容器 1 容量 3、容器 2 容量 5，目标 4 升。程序返回的最少操作数是多少？
（1 分）为什么状态可以编码成 x * (b+1) + y 作 key？
为什么 BFS 里 x == c || y == c 而不是 &&？
若 a=5, b=3, c=0（起点即达成目标），程序返回什么？
（1 分）题目： 棋盘，马从 出发按「日」字跳，求到每个格子的最少步数（不可达输出 -1）。
01#include <iostream> 02#include <queue> 03using namespace std; 04int step[505][505]; 05int n, m; 06const int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2}; 07const int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1}; 08void bfs() { 09 step[1][1] = 0; 10 queue<pair<int, int> > q; 11 q.push({1, 1}); 12 while (!q.empty()) { 13 int x = q.front().first, y = q.front().second; 14 q.pop(); 15 for (int d = 0; d < 8; d++) { 16 int nx = x + dx[d], ny = y + dy[d]; 17 if (nx < 1 || nx > n || ny < 1 || ny > m) continue; 18 if (step[nx][ny] != -1) continue; 19 step[nx][ny] = step[x][y] + 1; 20 q.push({nx, ny}); 21 } 22 } 23}
方向数组为什么有 8 项而不是 4 项？
（1 分）为什么 BFS 能求出「最少步数」而不用 DFS？
（1 分）4×4 棋盘，从 (1,1) 到 (4,4) 的最少步数是多少？
（1 分）若把起点 step[1][1] = 0 误写成保持初值 -1，会怎样？
BFS 主循环的三个要素按顺序是？
规则：BFS 循环 = ①取出队头 ②枚举全部可转移的邻居 ③未访问则标记并入队。
考点：BFS 模板骨架。
解析：出队取得当前状态；扩展它的所有邻居；每个「合法且未访问」的邻居打上步数标记后入队。三要素缺一不可（漏出队死循环、漏判重膨胀、漏扩展搜索不全）。
排除法：顺序必须「先出后扩」；不是先入队；排序与 BFS 无关。
为什么网格 BFS 里必须有 nx < 0 || nx >= n || ny < 0 || ny >= m 这套边界判断？
01for (int d = 0; d < 4; d++) { 02 int nx = u.x + dx[d], ny = u.y + dy[d]; 03 if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; 04 if (g[nx][ny] == '#') continue; 05 if (step[nx][ny] != -1) continue; 06 step[nx][ny] = step[u.x][u.y] + 1; 07 q.push({nx, ny}); 08}
规则：边界判断 = 数组越界防护；越界访问是未定义行为（可能崩溃、可能返回垃圾值）。
考点：网格 BFS 的越界防护。
解析：dx/dy 中 -1 项把 x/y 推到 -1，+1 项推到 n/m。g[-1][0] 这种下标越过数组边界，C++ 不做运行时检查，行为未定义。
排除法：越界不是死循环（是访问错误内存）；步数错误是越界访问的连带后果，根因是越界；规范与否不是关键，正确性才是。
BFS 求最短步数，终点判断放在「出队时」与「入队时」，结果一样吗？
01 02while (!q.empty()) { 03 Node u = q.front(); q.pop(); 04 if (u.x == ex && u.y == ey) return step[u.x][u.y]; 05 ... 06} 07 08while (!q.empty()) { 09 Node u = q.front(); q.pop(); 10 ... 11 if (nx == ex && ny == ey) return step[nx][ny]; 12}
规则：两种写法的返回值等价；唯一差异是「起点即终点」特判：写法甲必须起点先标 0 并参与循环，写法乙在入队时就可能直接返回。
解析：BFS 层序保证任何状态第一次被访问（入队）或第一次被弹出（出队）都在最浅层。写法乙在邻居入队时检查，早一拍返回；写法甲等终点出队时返回。对非起点目标两者步数一致。
排除法：两者都返回最短步数；乙不多算；乙不必然错误；与 DFS 无关。
四连通意义下，网格中「连通块」是指？
规则：连通块 = 由相邻同类格子连成的一片区域；块内两两可达，块与块之间被其他类型隔开。
考点：连通块概念。
解析：四连通只认上下左右相邻。把「上下左右相邻的同类格」连成一片，每一片就是一个连通块。块与块之间必然隔着障碍或边界。
排除法：「同一行」忽略竖向连接；「所有同类格子」合并了被隔开的不同块；「同数字」与连通无关。
八连通与四连通的差别在于？
规则：四连通 = 上下左右；八连通 = 上下左右 + 四个对角。
解析：方向数组从 4 项变 8 项：多了 (-1,-1)、(-1,1)、(1,-1)、(1,1) 四个对角。同一张图按不同连通定义，块数通常不同。
排除法：八连通是四连通加四个对角，不是只加斜上；方向数与名称正好对应，四连通是 4 项；八连通不走直线，是扩展相邻。
4×4 网格，W 位置为：(0,0)、(0,1)、(1,1)、(2,2)、(3,2)、(3,3)。按四连通算有几块？按八连通算有几块？
01 02const int dx[4] = {-1, 1, 0, 0}; 03const int dy[4] = {0, 0, -1, 1};
规则：四连通下 (0,0)-(0,1)-(1,1) 一片、(2,2)-(3,2)-(3,3) 一片 = 2 块；八连通下 (1,1) 与 (2,2) 斜向相邻 → 两片连成 1 块。
解析：四连通：块1 = {(0,0),(0,1),(1,1)}（(0,0)-(0,1) 横邻、(0,1)-(1,1) 竖邻），块2 = {(2,2),(3,2),(3,3)}，(1,1) 与 (2,2) 对角但不四邻。八连通：(1,1) 与 (2,2) 对角相邻，两块连成一块。
排除法：3 块是把块 2 拆错；2 块/1 块是没注意对角是否算相邻。
2×2 网格四格全为 W，四连通下 Flood Fill 后 ans 是多少？
01for (int i = 0; i < n; i++) 02 for (int j = 0; j < m; j++) 03 if (a[i][j] == 'W') { 04 ans++; 05 flood(i, j); 06 }
规则：四格全部上下左右相邻，是一整块，ans = 1。
解析：第一个 W 触发 flood，把整个 2×2 全部标记为 '.'，后续循环再也碰不到 W，ans 只加 1。
排除法：2、3、4 是把「每格一块」或「每行一块」当答案，忽略相邻连片。
为什么 Flood Fill 的计数逻辑「发现新块先 ans++ 再整块淹掉」能保证每块恰好计数一次？
01for (int i = 0; i < n; i++) 02 for (int j = 0; j < m; j++) 03 if (a[i][j] == 'W') { 04 ans++; 05 flood(i, j); 06 }
规则：flood 把整块标记成 '.'，保证块内只有第一个被扫到的 W 会触发 ans++。
解析：若某个 W 已被淹（变 '.'），外层循环跳过；若仍是 W，说明它所属的块之前从未被 flood 覆盖——它所在块还没被计数，此时计数恰好一次。淹掉后该块其他格子都变 '.'，不会再被计数。
排除法：flood 不记录列表、不计数；「每格只进循环一次」是循环结构不是计数保证；ans 只在主循环加。
对 1×3 的一行 W W W 调用 flood(0,0)（四连通），flood 返回后三个格子状态是？
01void flood(int x, int y) { 02 if (x < 0 || x >= n || y < 0 || y >= m) return; 03 if (a[x][y] == '.') return; 04 a[x][y] = '.'; 05 for (int d = 0; d < 4; d++) 06 flood(x + dx[d], y + dy[d]); 07}
规则：flood 对当前格先标后扩，递归把整个连通块淹没。
解析：flood(0,0) 把 (0,0) 标 '.'，向右 flood(0,1) 标 '.'，再向右 flood(0,2) 标 '.'。向左、上下越界或遇到 '.' 返回。整行被淹完。
排除法：不是只标一格；不会死循环——每格标过一次后 a[x][y]=='.' 拦截回头；不会全保留。
Flood Fill 里为什么「先 a[x][y] = '.' 再递归」，而不是「先递归完再标记」？
01void flood(int x, int y) { 02 if (x < 0 || x >= n || y < 0 || y >= m) return; 03 if (a[x][y] == '.') return; 04 a[x][y] = '.'; 05 for (int d = 0; d < 4; d++) 06 flood(x + dx[d], y + dy[d]); 07}
规则：标记必须先于递归——用「已访问」拦截回头路，防止两格互相递归。
解析：若先递归后标记：flood(A) 调 flood(B)，B 的四邻含 A 且 A 还是 W，又调 flood(A)，A 又调 flood(B)……无限递归栈溢出。先标 '.' 后，B 的邻居检查 A 时 a[A]=='.' 直接返回。
排除法：不是效率或语法问题，是终止性问题；顺序调换会栈溢出而不是少淹一格。
同一张图，用 DFS 递归泛洪和用 BFS 队列泛洪，最终算出的连通块数会不同吗？下面两段分别是两种实现：
01#include <iostream> 02#include <queue> 03using namespace std; 04char a[105][105]; 05int n, m; 06const int dx[4] = {-1, 1, 0, 0}; 07const int dy[4] = {0, 0, -1, 1}; 08void flood_dfs(int x, int y) { 09 if (x < 0 || x >= n || y < 0 || y >= m) return; 10 if (a[x][y] == '.') return; 11 a[x][y] = '.'; 12 for (int d = 0; d < 4; d++) 13 flood_dfs(x + dx[d], y + dy[d]); 14} 15void flood_bfs(int sx, int sy) { 16 queue<pair<int, int> > q; 17 q.push({sx, sy}); 18 a[sx][sy] = '.'; 19 while (!q.empty()) { 20 int x = q.front().first, y = q.front().second; 21 q.pop(); 22 for (int d = 0; d < 4; d++) { 23 int nx = x + dx[d], ny = y + dy[d]; 24 if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; 25 if (a[nx][ny] == '.') continue; 26 a[nx][ny] = '.'; 27 q.push({nx, ny}); 28 } 29 } 30}
规则：连通块由「格子是否同类且相邻」决定，与遍历顺序无关；两种实现标记的格子集合完全相同。
考点：DFS/BFS 泛洪的等价性。
解析：对比两段代码：flood_dfs 递归深入、flood_bfs 队列分层，但每一步做的都是同一件事——「把当前格标成 .，再去处理四邻里还没标过的格子」。判重都靠「已标记的 . 拦住回头路」，所以从同一块出发，最终被标成 . 的格子集完全一样。计数逻辑（主循环发现新块 +1 再整块淹掉）相同，块数自然相同。
排除法：块数与遍历算法无关；两者都能算对。
5×5 网格只有中间的 3×3 是 W（其余都是 .）。从中心 W 发起 flood，四连通下会淹掉多少格？
01a[x][y] = '.'; 02for (int d = 0; d < 4; d++) flood(x + dx[d], y + dy[d]);
规则：3×3 的 W 区四连通互相可达，从任意一格发起都能淹掉全部 9 格。
解析：3×3 区域四连通连通：中心的 W 向上下左右扩展，再扩散到整个 3×3。外面的 '.' 挡住扩展，共 9 格。
排除法：3、5 是「一行/十字」的格子数；25 是整个网格，但外围是 '.' 拦住了。
Flood Fill（泛洪）的本质操作是？
规则：泛洪 = 从一个种子出发沿连通关系扩散，淹掉整个连通块。
解析：无论递归 DFS 还是队列 BFS，核心都是「种子的邻居里同类型的也标掉，再扩散它们的邻居」，直到没有新的可标格。这就是「填色」。
排除法：不是全图统一色；不是按行分段；不是只标种子。
4×4 网格，W 在 (0,0) 和 (3,3)，其余为 .。四连通 Flood Fill 后 ans 是多少？
01for (int i = 0; i < n; i++) 02 for (int j = 0; j < m; j++) 03 if (a[i][j] == 'W') { ans++; flood(i, j); }
规则：两个 W 被 '.' 完全隔开，各自成块，ans = 2。
解析：(0,0) 的 flood 只淹自己（周围都是 '.'）；(3,3) 同理。两块互不相邻，各计一次。
排除法：1 误以为 W 总会连成一片；3、4 是把 '.' 也当块。
01#include <iostream> 02using namespace std; 03char a[105][105]; 04int n, m, ans; 05const int dx[4] = {-1, 1, 0, 0}; 06const int dy[4] = {0, 0, -1, 1}; 07void flood(int x, int y) { 08 if (x < 0 || x >= n || y < 0 || y >= m) return; 09 if (a[x][y] == '.') return; 10 a[x][y] = '.'; 11 for (int d = 0; d < 4; d++) 12 flood(x + dx[d], y + dy[d]); 13} 14int main() { 15 cin >> n >> m; 16 for (int i = 0; i < n; i++) 17 for (int j = 0; j < m; j++) 18 cin >> a[i][j]; 19 for (int i = 0; i < n; i++) 20 for (int j = 0; j < m; j++) 21 if (a[i][j] == 'W') { 22 ans++; 23 flood(i, j); 24 } 25 cout << ans << endl; 26 return 0; 27}
2×2 全为 W，程序输出多少？
（1 分）为什么主循环要在格子为 W 时才计数？
（1 分）把方向数组从 4 项改成 8 项（八连通），块数会？
（1 分）若把主循环 if (a[i][j] == 'W') 误写成 if (a[i][j] == '.')，程序输出多少？
题目： 网格，. 为水、# 为陆地，求最大陆地块的面积（格子数）。陆地块 = 四连通的 # 组成的最大区域。
01#include <iostream> 02using namespace std; 03char g[105][105]; 04int n, m, cur; 05const int dx[4] = {-1, 1, 0, 0}; 06const int dy[4] = {0, 0, -1, 1}; 07void dfs(int x, int y) { 08 if (x < 0 || x >= n || y < 0 || y >= m) return; 09 if (g[x][y] != '#') return; 10 g[x][y] = '.'; 11 cur++; 12 for (int d = 0; d < 4; d++) 13 dfs(x + dx[d], y + dy[d]); 14}
cur 每次统计一块的面积，应该在什么时候重置为 0？
（1 分）为什么必须先标 . 再递归？
3×3 网格只有中心一格为 #，其余全为 .，最大陆地面积是多少？
用 BFS 实现本题，结果会不同吗？
（1 分）题目： 网格，W 为水、. 为地。八连通意义下水的连通块（湖泊）有几个？八连通：含对角相邻。
01#include <iostream> 02using namespace std; 03char a[105][105]; 04int n, m, ans; 05const int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}; 06const int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1}; 07void flood(int x, int y) { 08 if (x < 0 || x >= n || y < 0 || y >= m) return; 09 if (a[x][y] == '.') return; 10 a[x][y] = '.'; 11 for (int d = 0; d < 8; d++) 12 flood(x + dx[d], y + dy[d]); 13}
3×3 网格 W 位于四个角，八连通湖泊数是多少？
（1 分）为什么八连通用 8 项方向数组？
（1 分）补全 Flood Fill：进入一个格子后要「先 ____ 再递归」，并用「先判越界再访问」的顺序。
01void flood(int x, int y) { 02 if (x < 0 || x >= n || y < 0 || y >= m) return; 03 if (a[x][y] == '.') return; 04 ____; 05 for (int d = 0; d < 4; d++) 06 flood(x + dx[d], y + dy[d]); 07}
规则：标记 = 把当前格改成已访问（原地改图 a[x][y]='.' 或另开 visited）。
考点：泛洪的标记动作与时机。
解析：先越界判断 → 再判断是否已访问（'.' 拦截）→ 标记当前格 → 递归四邻。标记必须在递归之前。
排除法：return 是出口不是标记；ans++ 是主循环计数，泛洪内不应计数；flood(x,y) 无限递归。
Flood Fill 里如果把标记行 a[x][y] = '.' 删掉，会发生什么？
01void flood(int x, int y) { 02 if (x < 0 || x >= n || y < 0 || y >= m) return; 03 if (a[x][y] == '.') return; 04 a[x][y] = '.'; 05 for (int d = 0; d < 4; d++) flood(x + dx[d], y + dy[d]); 06}
规则：标记是泛洪的终止保证；删掉 = 递归互相调用 = 无限递归。
解析：A、B 相邻：flood(A) → flood(B) → B 四邻含 A（未标记）→ flood(A) → flood(B) …… 永不返回，栈溢出崩溃。
排除法：不是慢一点，是根本停不下来；块数多 1 是标记缺失的连带后果，但最先致命的是无限递归；不只多访问几个格子。
搜索的总时间如何估算？
规则：复杂度 = 节点数 × 单节点代价；节点数包括中间节点。
解析：每个节点要枚举它的所有分支并做合法性判断，这是「单节点代价」；把所有节点的代价加起来就是总时间。中间节点往往比叶子多，只数叶子会低估。
排除法：中间节点也要开销；根节点只有一个；与字节数无关。
搜索里「剪枝」指的是？
规则：剪枝 = 判定某分支「不可行/不可能更优」后不再展开它，跳过一整棵子树。
解析：剪枝必须「判定正确」——只剪确定没希望的分支，否则会丢答案。剪掉一棵子树 = 节省它下面所有节点的计算量。
排除法：「画小」是结果描述不是机制；剪枝不提前返回近似答案（那是启发式终止）；叶子重复在正确搜索里不会出现。
子集和的代码加了 if (sum > t) return;。为什么这一行有时能把超时的程序救回来？
01void dfs(int i, int sum) { 02 if (i == n) { if (sum == t) ok = true; return; } 03 if (sum > t) return; 04 dfs(i + 1, sum); 05 dfs(i + 1, sum + w[i]); 06}
规则：剪枝节省的是整棵子树：从该节点以下不再展开，省掉指数级节点。
解析：所有数都是非负时，一旦 sum 超过 t，继续选只会更大，「和等于 t」永远无法成立——子树里必无答案。直接 return 等于把该节点以下全部节点一次性删除。在 t 较小、w 较大时，很多分支早期就超 t，整棵树大幅变小。
排除法：剪枝的意义在「跳过数量」不是「判断更快」；程序不自动挑数字；正确的剪枝不改变答案，只删无望分支。
fib(5)（朴素递归，不记忆化）一共调用 fib 多少次？
01int fib(int n) { 02 if (n <= 1) return n; 03 return fib(n - 1) + fib(n - 2); 04}
规则：朴素递归调用树：，，。
解析：T(5) = 1 + T(4) + T(3)；T(4) = 1 + T(3) + T(2) = 1+5+3=9；T(3) = 1 + T(2) + T(1) = 1+3+1=5；T(2) = 1 + 1 + 1 = 3。所以 T(5) = 1+9+5 = 15。
排除法：10、8 低估（漏掉重叠子问题的重复计算）；20 高估。
同样求 fibm(5)（记忆化版），fibm 被调用的次数是？
01int f[100]; 02int fibm(int n) { 03 if (n <= 1) return n; 04 if (f[n] != -1) return f[n]; 05 return f[n] = fibm(n - 1) + fibm(n - 2); 06}
规则：记忆化让每个 n 至多算一次：fibm(5), fibm(4), fibm(3), fibm(2), fibm(1), fibm(0) 共 6 个「首次计算」，加 fibm(4) 返回时 fibm(3) 已被计算过等，共 11 次调用（6 次真算 + 5 次查缓存返回）。
解析：调用顺序：fibm(5) 调 fibm(4) → fibm(3) → fibm(2) → fibm(1)（返回）、fibm(0)（返回）→ fibm(2) 算完；fibm(3) 里再调 fibm(1)（缓存返回）；fibm(4) 里再调 fibm(2)（缓存返回）；fibm(5) 里再调 fibm(3)（缓存返回）。真算 6 个、命中缓存 5 次，共 11 次。
排除法：15 是朴素版；9、6 不符合调用计数。
为什么记忆化能把斐波那契从 降到 ？
01int f[100]; 02int fibm(int n) { 03 if (n <= 1) return n; 04 if (f[n] != -1) return f[n]; 05 return f[n] = fibm(n - 1) + fibm(n - 2); 06}
规则：重叠子问题 + 缓存命中 = 每个状态只算一次。
解析：朴素递归里 fib(2) 被 fib(3)、fib(4)…重复计算无数次；f[n] != -1 命中时 返回，省掉整棵子树。n 个不同的参数，每个至多算一次，其余 命中 → 。
排除法：记忆化仍是「递归 + 缓存」，不是改递推（虽然与 DP 同源）；「数组更快」不是本质；与返回值大小无关。
记忆化搜索能加速的前提是？
规则：记忆化 = 空间换时间，价值来自「重叠子问题」的重复计算。
解析：只有不同的路径会到达相同的状态（相同参数），缓存才有意义。无重叠时每个状态只算一次，缓存浪费空间。
排除法：参数可以是任意可哈希状态（数组/字符串编码）；深度与记忆化价值无关；求值类型不限。
状态空间巨大（如 个不同状态）且每条路径状态互不重叠时，记忆化会怎样？
规则：记忆化的收益依赖重叠；状态互异时它是纯开销。
解析：若每个状态只被访问一次，f[n] != -1 从不命中，多花的只是数组空间和判断时间。此时应该用剪枝或换算法，而不是记忆化。
排除法：无重叠时不会降到线性；不会快一倍；不会自动压缩。
子集和：，w = {8, 9, 7, 2, 1}，t = 10。代码带 if (sum > t) return; 剪枝。搜索会不会「提前」跳过以 8 开头的子树？（w 全为正数）
01void dfs(int i, int sum) { 02 if (i == n) { if (sum == t) ok = true; return; } 03 if (sum > t) return; 04 dfs(i + 1, sum); 05 dfs(i + 1, sum + w[i]); 06}
规则：剪枝发生在「当前 sum 已超 t」的节点，剪掉它下面的全部节点。
解析：第一层选 8：dfs(1, 8) 继续。第二层再选 9 → sum = 17 > 10，该节点 return，它下面选 7/2/1 的节点全部跳过。注意 8 这一支还有「不选 9、选 7 → 15 > 10」等分支依次被剪。正确答案 8+2=10 不会丢——8 和 2 的和没超过 t 时才继续。
排除法：8 本身 < t 不会立刻剪；「只剪选 8 那层」理解错位置；正确剪枝不漏答案。
同样一个剪枝搜索，为什么「先搜分支少/约束强」的方向通常更快？
规则：剪枝价值 = 被剪子树的大小 × 剪枝触发时机；约束强的分支更早触发剪枝。
解析：搜索顺序影响「剪枝发生的深度」。越早剪，跳过的节点越多。约束强的方向通常走几步就违反约束（如数独先填已确定多的格子），剪枝提前。
排除法：不是数组大小问题；循环快慢是常数级差异，不是主因；约束强不保证含答案。
求「最长路径」的搜索里，「最优性剪枝」指的是？
规则：最优性剪枝 = 用「上界估计 ≤ 当前最优」判死一个分支：它不可能产出更优解。
解析：先搜出一个可行解，之后任何分支若能证明「就算往最好里走也超不过当前最优」，就没必要再搜。它依赖一个上界函数，估计越紧剪得越多。
排除法：提前停止会漏更优解；走完全部是不剪枝；「只走最长的」是贪心不是搜索。
为什么最优性剪枝必须用「上界 ≤ 当前最优」剪，而不是「当前值 ≤ 当前最优」剪？
规则：要剪的是「注定无法更优」的分支——看它可能达到的上限，而不是当前已取得的局部值。
解析：搜索进行到一半，后面还能继续加分。若「当前 + 剩余最大可能」≤ 当前最优，那它无论如何追不上；若只拿当前值判断，会把还能反超的分支误剪。
排除法：上界难算时通常改用启发式；上界是估计不保证等于最优（等于最优就是精确解了）；效率不是理由。
「走迷宫（网格上每步走到相邻空地）求最短路」该用哪种搜索？「八皇后（在 棋盘上每行放一个皇后，要求任意两个皇后不同列、不同对角线，枚举全部摆法）」又该用哪种搜索？
规则：求「最短」→ BFS；「枚举全解 / 判存在」→ DFS（或 BFS）皆可，DFS 更常用。
解析：BFS 保证首达最短；DFS 第一次到终点不保证最短，但枚举完整解（所有排列/子集/摆法）时 DFS 一条路径探到底的天然结构与递归配合最好。
排除法：两者不能互换场景；枚举全解也可以用 BFS 但通常不优；顺序反了。
只判断「A 能不能走到 B」（不要求最短），DFS 和 BFS 哪个能用？
规则：可达性 = 从起点出发的闭包是否包含 B，与遍历顺序无关，DFS/BFS 都行。
解析：DFS 走遍所有可达状态，BFS 也走遍所有可达状态，只是顺序不同。判断「visited 里有没有 B」两者等价。
排除法：只有要最短步数时才是 BFS 专属；DFS 完全能做可达性。
状态空间巨大时，为什么 BFS 可能内存爆掉而 DFS 不会？对比两种实现的「待处理」存储：
01#include <queue> 02#include <vector> 03using namespace std; 04vector<int> adj[105]; 05bool vis[105]; 06void bfs(int s) { 07 queue<int> q; 08 q.push(s); 09 vis[s] = true; 10 while (!q.empty()) { 11 int u = q.front(); 12 q.pop(); 13 for (int v : adj[u]) 14 if (!vis[v]) { 15 vis[v] = true; 16 q.push(v); 17 } 18 } 19} 20void dfs_stack(int s) { 21 vector<int> st; 22 st.push_back(s); 23 vis[s] = true; 24 while (!st.empty()) { 25 int u = st.back(); 26 st.pop_back(); 27 for (int v : adj[u]) 28 if (!vis[v]) { 29 vis[v] = true; 30 st.push_back(v); 31 } 32 } 33}
规则：BFS 的队列峰值 = 最大层宽；DFS 的栈峰值 = 最大深度。搜索树往往「宽而浅」，层宽远大于深度。
考点：两种遍历的空间开销。
解析：bfs 把「整层待处理」都堆在队列里，队尾可能同时躺着 个状态（最宽那一层）；dfs_stack 的栈里永远只有「一条路径上的点」，最多等于深度 。比如 3 叉深 30 的树：DFS 栈最多 30 个状态，BFS 队尾一层可达 量级。所以大状态空间求最短要留意内存。
排除法：不是单字节差异，是数量级差异；DFS 栈也存状态（一条路径）；BFS 不必然早退出。
关于搜索与数据结构的关系，正确的是？
规则：DFS ↔ 栈（递归），BFS ↔ 队列。
解析：DFS 的「后进先出」靠系统栈实现；BFS 的「先进先出」靠显式队列。判重另用 visited。
排除法：对应关系是固定的；哈希表只用于判重，不决定遍历顺序；数据结构是遍历机制的载体。
每秒能处理约 个状态。全排列（把 的所有排列逐个枚举）： 时共 种，能跑完吗？
规则：，远超可处理量级；不可行的是「超时」而非「栈溢出」。
解析： 秒 ≈ 760 年。搜索树叶子指数爆炸，是典型超时场景。注意递归深度只有 20 层，栈毫无压力——超时不是栈溢出。
排除法：数字级数差太多；「几分钟」低估了十几个数量级；栈深 20 层不会溢出。
01int w[20]; 02int n, t; 03bool ok = false; 04void dfs(int i, int sum) { 05 if (i == n) { 06 if (sum == t) ok = true; 07 return; 08 } 09 if (sum > t) return; 10 dfs(i + 1, sum); 11 dfs(i + 1, sum + w[i]); 12}
n=3, w={1,2,3}, t=3，程序结束时 ok 为？
为什么 sum > t 时可以直接 return 而不会漏答案？
w={1,2,3}, t=6，sum > t 剪枝会剪掉多少分支？
若 w 允许负数，sum > t 剪枝还正确吗？
01int fib(int n) { 02 if (n <= 1) return n; 03 return fib(n - 1) + fib(n - 2); 04} 05 06int f[100]; 07int fibm(int n) { 08 if (n <= 1) return n; 09 if (f[n] != -1) return f[n]; 10 return f[n] = fibm(n - 1) + fibm(n - 2); 11}
fib(6)（朴素递归）一共调用 fib 多少次？
fibm(6)（记忆化）真正需要计算的 n 有几个？（不含缓存命中）
为什么 fibm 里的 f[n] != -1 判断是「查缓存」？
在计算 fibm(4) 的过程中，fibm(2) 已经被 fibm(3) 算过并存进 f[2]。此时再调 fibm(2) 会发生什么？
下面哪一组完整覆盖了常见的剪枝类型？
规则：剪枝三分类：可行性、最优性、搜索顺序优化。
考点：剪枝的分类体系。
解析：可行性剪枝剪「注定非法」的分支；最优性剪枝剪「注定不优」的分支（上界 ≤ 当前最优）；搜索顺序优化不剪枝但通过调整顺序让剪枝更早触发。
排除法：「早/晚」不是分类维度；「超时再剪」是本末倒置；越界判断是正确性不是剪枝。
下面这段 BFS 有一个严重问题。找出它：
01while (!q.empty()) { 02 int x = q.front().first, y = q.front().second; 03 for (int d = 0; d < 4; d++) { 04 int nx = x + dx[d], ny = y + dy[d]; 05 if (非法) continue; 06 step[nx][ny] = step[x][y] + 1; 07 q.push({nx, ny}); 08 } 09}
规则：BFS 主循环三要素缺一不可：出队、扩展、入队。少了出队 = 队头钉死 = 死循环。
解析：代码里 q.front() 取队头却从不 q.pop()。扩展入队不断追加队尾，但队头永远是最初的状态 → 每次循环都是同一个状态，无限循环。
排除法：终点判断确实没有（通常是出队时判断），但最致命的是死循环；方向数组没写错；答案通过 step 记录，不缺变量。
子集和代码里 if (sum > t) return; 放在两个递归调用的前面。若 w 全部为正数，这个剪枝会「漏掉答案」吗？
01void dfs(int i, int sum) { 02 if (i == n) { if (sum == t) ok = true; return; } 03 if (sum > t) return; 04 dfs(i + 1, sum); 05 dfs(i + 1, sum + w[i]); 06}
规则：可行性剪枝的正确性 = 状态的单调性。w 非负 → sum 单调 → 超 t 必无望。
解析：w 全正时 sum 严格单调不减，sum > t 后无论怎么选都回不到 t。剪枝只删无望分支，不漏答案。
排除法：w 为正没有负数可回落；sum 已超 t 时「不选后面的数」还是当前 sum > t，不是答案；与 t 奇偶无关。
「忘恢复现场」和「忘标记」在回溯搜索里的后果有什么不同？第一段删掉了「恢复现场」一行，第二段删掉了「标记」一行：
01int a[10]; bool used[10]; int n; 02void dfs(int k) { 03 if (k == n) { 04 for (int i = 0; i < n; i++) cout << a[i]; 05 cout << endl; 06 return; 07 } 08 for (int i = 1; i <= n; i++) { 09 if (used[i]) continue; 10 a[k] = i; 11 used[i] = true; 12 dfs(k + 1); 13 } 14}
01int a[10]; bool used[10]; int n; 02void dfs(int k) { 03 if (k == n) { 04 for (int i = 0; i < n; i++) cout << a[i]; 05 cout << endl; 06 return; 07 } 08 for (int i = 1; i <= n; i++) { 09 if (used[i]) continue; 10 a[k] = i; 11 dfs(k + 1); 12 used[i] = false; 13 } 14}
规则：恢复与标记是一对对称操作，各管一头：恢复管「同层兄弟分支的干净起点」，标记管「下层不重复选自己」。
考点：回溯三件套两条的各自职责。
解析：第一段缺 used[i] = false;：第一分支选 1 后残留 used[1] = true，返回后第二分支想选 1 时被 if (used[i]) continue 挡掉，可选数字变少，排列残缺。第二段缺 used[i] = true;：used 恒为假，下层看到所有数字都「没用过」，当前数字会被再选一次，出现 11、22 这类重复。两者都破坏「每个方案恰好一次」。
排除法：都不会必然死循环（是全/重问题）；结果不同；与快慢无关。
带限制的全排列：n = 3，限制是「第 k 位数字不能等于前一位数字加 1」（即相邻两个数不能相差恰为 1 且后者大 1）。程序输出多少？
01if (k > 1 && i == p[k - 1] + 1) continue;
规则：枚举 6 个排列，删去「后一位 = 前一位 + 1」的：123（2=1+1）、231（3=2+1）、312（2=1+1）被禁；剩 132、213、321 共 3 个。
解析：逐一检查：123 中第 2 位 2 = 第 1 位 1 + 1 → 禁；132：第 2 位 3 ≠ 2、第 3 位 2 ≠ 4 → 合法；213：第 2 位 1 ≠ 3、第 3 位 3 ≠ 2 → 合法；231：第 2 位 3 = 2 + 1 → 禁；312：第 3 位 2 = 1 + 1 → 禁；321：全部不满足 → 合法。合法 3 个。
排除法：1、2 低估；6 是不带限制的全部排列。
用「画递归树」法读下面的 DFS：n = 2 时输出多少？
01int a[10]; bool used[10]; int n; 02void dfs(int k) { 03 if (k == n) { ans++; return; } 04 for (int i = 1; i <= n; i++) { 05 if (used[i]) continue; 06 used[i] = true; 07 dfs(k + 1); 08 used[i] = false; 09 } 10}
规则：n=2 全排列 2! = 2。
解析：递归树：根分两叉（选1、选2），每叉再分一叉（选剩下的），叶子 2 个，ans=2。
排除法：1 漏了第二个排列；3、4 无依据。
阅读一段 DFS 回溯代码时，最有效的方法是？
规则：DFS 程序 = 搜索树 + 状态迁移，画树是最有效的追踪手段。
解析：dfs 的每次递归调用是「进入子树」，for 循环是「展开兄弟分支」，标记/恢复是「进入/离开」的状态操作。按行号顺序读会丢失这种树形结构。
排除法：逐行读只见代码不见结构；只看主函数漏掉递归体；运行程序是验证不是理解。
CSP 初赛常考「DFS 阅读程序 + 判断/选择」题型。这类题的核心考点通常是？
规则：真题考「读懂代码的行为」：小数据追踪 + 边界 + 删改影响。
解析：如 2020 阅读程序 DFS 块，子题考 n=0 会不会死循环、全 0 输出、输出的上界、删掉某行会怎样。教学卷 M6 就是为这类题型准备的。
排除法：复杂度公式是概念题不是阅读题；库函数与 DFS 阅读无关；初赛阅读程序是代码题。
下面这段 BFS 求起点到终点最短路，哪里错了？
01while (!q.empty()) { 02 int x = q.front().first, y = q.front().second; 03 q.pop(); 04 if (x == ex && y == ey) break; 05 for (int d = 0; d < 4; d++) { 06 int nx = x + dx[d], ny = y + dy[d]; 07 if (非法) continue; 08 if (step[nx][ny] != -1) continue; 09 step[nx][ny] = step[x][y] + 1; 10 q.push({nx, ny}); 11 } 12} 13cout << step[ex][ey] << endl;
规则：终点判断在出队时，若起点=终点，第一次出队就 break；step[起点] 必须已初始化为 0，否则输出错误。
解析：正确实现应在入队前把起点 step 标 0（如 step[sx][sy]=0; q.push({sx,sy})）。若忘记，起点=终点时 break 后 step[ex][ey] = -1 输出 -1。
排除法：pop 存在；方向数组正常；判重正确。
判断「从起点能否到终点」用 DFS 或 BFS 都能完成。为什么都行？下面分别是两种遍历的骨架：
01#include <iostream> 02#include <queue> 03#include <vector> 04using namespace std; 05vector<int> adj[105]; 06bool vis[105]; 07void dfs(int u) { 08 vis[u] = true; 09 for (int v : adj[u]) 10 if (!vis[v]) dfs(v); 11} 12void bfs(int s) { 13 queue<int> q; 14 q.push(s); 15 vis[s] = true; 16 while (!q.empty()) { 17 int u = q.front(); 18 q.pop(); 19 for (int v : adj[u]) 20 if (!vis[v]) { 21 vis[v] = true; 22 q.push(v); 23 } 24 } 25}
规则：可达性 = 起点可达闭包是否含终点；DFS/BFS 的可达闭包相同。
考点：可达性与遍历顺序无关。
解析：dfs 深挖一路、bfs 按层推进，但两者的判重逻辑完全一样——「vis 标到过的点」，且都只沿边扩展。从起点出发能到的点，两种写法都会标到；到不了的，两种都标不到。最终 vis 标记的集合相同，判断「终点在不在集合里」两者等价。
排除法：效率差异不是「都能」的原因；终点未必可达（不可达时 vis 为假）；visited 用法相同但结论与遍历方式无关。
删掉子集和代码里的 if (sum > t) return;，对「ok 最终值」有什么影响？（w 全正）
01void dfs(int i, int sum) { 02 if (i == n) { if (sum == t) ok = true; return; } 03 dfs(i + 1, sum); 04 dfs(i + 1, sum + w[i]); 05}
规则：正确剪枝不改变答案；删掉它 = 回到完整搜索，结果一样、时间更久。
解析：sum > t 的分支本来就无解，保留与否不影响「是否存在子集和等于 t」。删掉只是多遍历这些无望分支。
排除法：答案不因剪枝行变化；不必然 false/true；数据有限时不会死循环（指数遍历能结束）。
BFS 里「层」和 DFS 里「深度」的关系是？
规则：层 = 深度 = 从根到节点的边数；BFS 强调按层处理，DFS 强调递归栈深。
解析：两种遍历中「步数/层数/深度」都指从起点经过的边数。BFS 的「第 d 层」与 DFS 的「第 d 层递归」是同一概念。
排除法：两者等价；相关；都是边数。
01#include <cstdio> 02bool flag[27]; 03int n; 04int p[27]; 05int ans = 0; 06void dfs(int k) { 07 if (k == n + 1) { 08 ans++; 09 return; 10 } 11 for (int i = 1; i <= n; i++) { 12 if (flag[i]) continue; 13 if (k > 1 && i == p[k - 1] + 1) continue; 14 p[k] = i; 15 flag[i] = true; 16 dfs(k + 1); 17 flag[i] = false; 18 } 19} 20int main() { 21 scanf("%d", &n); 22 dfs(1); 23 printf("%d\n", ans); 24 return 0; 25}
n=3 时程序输出的 ans 是多少？
dfs 运行过程中，k 的取值恒满足 ，对吗？
删掉恢复现场行 flag[i] = false;，对 n=3 的答案有影响吗？
删掉判重行 if (flag[i]) continue;，n=2 时程序输出多少？
题目：阅读程序。d 是 行 2 列的数组。dfs(n, sum) 不断把相邻两行「合并」（前一行加后一行的对应列），直到只剩 1 行，枚举所有合并顺序并求加权和的最大值。
01#include <cstdio> 02int n; 03int d[50][2]; 04int ans; 05void dfs(int n, int sum) { 06 if (n == 1) { 07 if (sum > ans) ans = sum; 08 return; 09 } 10 for (int i = 1; i < n; i++) { 11 int a = d[i - 1][0], b = d[i - 1][1]; 12 int x = d[i][0], y = d[i][1]; 13 d[i - 1][0] = a + x; 14 d[i - 1][1] = b + y; 15 for (int j = i; j < n - 1; j++) { 16 d[j][0] = d[j + 1][0]; 17 d[j][1] = d[j + 1][1]; 18 } 19 int s = a + x + abs(b - y); 20 dfs(n - 1, sum + s); 21 for (int j = n - 1; j > i; j--) { 22 d[j][0] = d[j - 1][0]; 23 d[j][1] = d[j - 1][1]; 24 } 25 d[i - 1][0] = a; 26 d[i - 1][1] = b; 27 d[i][0] = x; 28 d[i][1] = y; 29 } 30}
这个程序的功能是？
（1 分）若输入 n=1，程序输出什么？
（1 分）输入的所有数都是 0 时，程序输出多少？
（1 分）程序的输出一定不小于输入的任意一个 d[i][0] 或 d[i][1] 吗？
1 #include <algorithm> 2 #include <iostream> 3 using namespace std; 4 5 int n; 6 int d[50][2]; 7 int ans; 8 9 void dfs(int n, int sum) { 10 if (n == 1) { 11 ans = max(sum, ans); 12 return; 13 } 14 for (int i = 1; i < n; ++i) { 15 int a = d[i - 1][0], b = d[i - 1][1]; 16 int x = d[i][0], y = d[i][1]; 17 d[i - 1][0] = a + x; 18 d[i - 1][1] = b + y; 19 for (int j = i; j < n - 1; ++j) 20 d[j][0] = d[j + 1][0], d[j][1] = d[j + 1][1]; 21 int s = a + x + abs(b - y); 22 dfs(n - 1, sum + s); 23 for (int j = n - 1; j > i; --j) 24 d[j][0] = d[j - 1][0], d[j][1] = d[j - 1][1]; 25 d[i - 1][0] = a, d[i - 1][1] = b; 26 d[i][0] = x, d[i][1] = y; 27 } 28 } 29 30 int main() { 31 cin >> n; 32 for (int i = 0; i < n; ++i) 33 cin >> d[i][0]; 34 for (int i = 0; i < n; ++i) 35 cin >> d[i][1]; 36 ans = 0; 37 dfs(n, 0); 38 cout << ans << endl; 39 return 0; 40 }
假设输入的 是不超过 的正整数，d[i][0]、d[i][1] 都是不超过 的正整数，完成下面的判断题和单选题。
若输入 为 ，此程序可能会死循环或发生运行错误。（ ）
（1 分）若输入 为 ，接下来的输入全为 ，则输出为 。（ ）
（1 分）输出的数一定不小于输入的 d[i][0] 和 d[i][1] 的任意一个。（ ）
若输入的 为 ，接下来的输入是 个 和 个 ，则输出为（ ）。
（1 分）若输入的 为 ，接下来的输入是 个 和 个 ，则输出为（ ）。
（1 分）若输入的 为 ，接下来的输入是 到 ，以及 到 ，则输出为（ ）。
（1 分）