🏠

🧪 CSP 初赛模拟考试 · 第三套模拟

选择题 15 题 + 阅读程序 3 段 + 完善程序 2 段 · 含字符串编码、Floyd、DFS、基环树与二叉查找树

📚 三大模块🎯 选择 30 分📖 阅读 + 完善 70 分⏱ 建议 120 分钟
← 返回主页
正在载入题库…

一、单项选择题（共 15 题，每题 2 分，共 30 分）

1. 中 以下逻辑表达式的值恒为真的是（　）。
A. P ∨ (¬P ∧ Q) ∨ (¬P ∧ ¬Q) B. Q ∨ (¬P ∧ Q) ∨ (P ∧ ¬Q) C. P ∨ Q ∨ (P ∧ ¬Q) ∨ (¬P ∧ Q) D. P ∨ ¬Q ∨ (P ∧ ¬Q) ∨ (¬P ∧ ¬Q)
✅ 正确答案：A
解析：四个选项整体都是「或」连接，只要有一部分为真即为真。逐一代入 (P,Q) 的四种取值：
· A：无论 P、Q 如何，¬P∧Q 与 ¬P∧¬Q 中必有一个在 P = 0 时为真，P = 1 时 P 本身为真 → 恒真
· B：P = 0 且 Q = 0 时全为假；C：同样在该情形为假；D：P = 0、Q = 1 时全为假。
2. 易 在 8 位二进制补码中，10101011 表示的数是十进制下的（　）。
A. 43 B. -85 C. -43 D. -84
✅ 正确答案：B
解析：补码还原：10101011 − 1 = 10101010，逐位取反得 11010101 = −(64 + 16 + 4 + 1) = −85。
或权位法：−128 + 32 + 8 + 2 + 1 = −85。
3. 易 二进制数 11.01 在十进制下是（　）。
A. 3.25 B. 4.125 C. 6.25 D. 11.125
✅ 正确答案：A
解析：11₂ = 3，.01₂ = 2⁻² = 0.25，合起来 3.25。
4. 中 把 64 位非零浮点数强制转换成 32 位浮点数后，不可能（　）。
A. 大于原数 B. 小于原数 C. 等于原数 D. 与原数符号相反
✅ 正确答案：D
解析：双精度转单精度会截掉尾数低 32 位，舍入后结果可能变大、变小或不变；但符号位由最高位单独保存，不会翻转。
5. 易 提出「存储程序」的计算机工作原理的是（　）。
A. 克劳德·香农 B. 戈登·摩尔 C. 查尔斯·巴贝奇 D. 冯·诺依曼
✅ 正确答案：D
解析：冯·诺依曼提出「存储程序 + 程序控制」原理；香农创立信息论，摩尔提出摩尔定律，巴贝奇设计差分机/分析机。
6. 中 开始为小写输入状态，小老鼠按 CapsLock、A、S、D 循环按键（CapsLock、A、S、D、CapsLock、…），屏幕上输出的第 81 个字符是（　）。
A. A B. S C. D D. a
✅ 正确答案：C
解析：CapsLock 不输出字符，每 4 个键输出 3 个字母，循环节为 A S D a s d（6 个字母一轮）。
81 = 6 × 13 + 3 → 循环节第 3 个字母 D。📌 与 2018 真题的区别：那题是 4 个字母（ASDF），这题只有 3 个，别混淆。
7. 中 字符串 "AAABBBCCC" 共有（　）个不同的非空子串。
A. 3 B. 12 C. 36 D. 45
✅ 正确答案：C
解析：子串只能形如 AaBbCc。分类计数：
· 只含 A / B / C 中一段：3 + 3 + 3 = 9
· A+B 或 B+C：3 × 3 × 2 = 18
· A+B+C：3 × 3 × 3 = 27
合计 9 + 18 + 27 = 36（总窗口数 45，其中 9 个重复）。
8. 易 广度优先搜索时，需要用到的数据结构是（　）。
A. 链表 B. 队列 C. 栈 D. 散列表
✅ 正确答案：B
解析：BFS 用队列（先进先出）逐层扩展；DFS 用栈或递归实现。
9. 易 通常在搜索引擎中，对某个关键词加上双引号表示（　）。
A. 排除关键词 B. 将关键词分解 C. 精确搜索，不拆分关键词 D. 站内搜索
✅ 正确答案：C
解析：双引号表示精确匹配，被引号括起来的内容作为一个整体不被拆分。
10. 难 将（2, 6, 10, 17）存到地址区间为 0~10 的哈希表中，如果哈希函数 h(x) = （　），将不会产生冲突。
A. x mod 11 B. x² mod 11 C. (2x) mod 11 D. ⌊√x⌋ mod 11
✅ 正确答案：D
解析：A：2→2、6→6、10→10、17→6（冲突）；B：4、3、1、3（冲突）；C：4、1、9、1（冲突）；D：⌊√2⌋=1、⌊√6⌋=2、⌊√10⌋=3、⌊√17⌋=4 → 1,2,3,4 无冲突。
11. 中 递归算法：n ≤ 1 返回 1；n ≥ 5 返回 n × solve(n − 2)；否则返回 n × solve(n − 1)。调用 solve(7) 的返回结果为（　）。
A. 105 B. 840 C. 210 D. 420
✅ 正确答案：C
解析：solve(7) = 7 × solve(5) = 7 × 5 × solve(3) = 7 × 5 × 3 × solve(2) = 7 × 5 × 3 × 2 × solve(1) = 7 × 5 × 3 × 2 × 1 = 210。
12. 难 最坏情况下，在 N 个互不相同的数中同时找最大与最小，至少需要（　）次比较。
A. ⌈3N/2⌉ − 2 B. ⌊3N/2⌋ − 2 C. 2N − 2 D. 2N − 4
✅ 正确答案：A
解析：成对比较：每两个元素先比 1 次分出大小，再分别更新当前最大 / 最小，每对共 3 次比较 → 约 3N/2 − 2；N 为奇数时向上取整，即 ⌈3N/2⌉ − 2。
13. 中 一家四口人，至少两个人生日属于同一月份的概率是（　）。
A. 1/12 B. 1/144 C. 41/96 D. 3/4
✅ 正确答案：C
解析：对立事件：四人都不同月 = 12×11×10×9 / 12⁴ = 55/96，所求 = 1 − 55/96 = 41/96。
14. 难 一棵二叉树的前序遍历序列是 ABCDEFG，后序遍历序列是 CBFEGDA，则根结点的左子树的结点个数可能是（　）。
A. 2 B. 3 C. 4 D. 5
✅ 正确答案：A
解析：前序首位 A、后序末位 A ⇒ A 是根。去掉 A 后，前序剩 BCDEFG、后序剩 CBFEGD；前序中 D 在 B、C 之后，后序中 D 在末尾附近，说明 D 要么属于右子树，要么整棵树只有左子树。
左子树结点数只能是 2（B、C） 或 6（B、C、D、E、F、G）；选项中只有 2 符合。
15. 中 2017 年 10 月 1 日是星期日，1999 年 10 月 1 日是（　）。
A. 星期三 B. 星期日 C. 星期五 D. 星期二
✅ 正确答案：C
解析：相隔 18 年，其中 2000、2004、2008、2012、2016 为闰年（+5 天），总天数 = 18 × 365 + 5 = 6575；6575 mod 7 = 2。
星期日前推 2 天 → 星期五。

二、阅读程序（第 16~18 题，含判断题与单选题）

阅读 1：encoder / decoder 字母表重排（第 16 题）中

encoder[] 只给了前 3 项 C、S、P，程序先把 A~Z 中没出现过的字母按顺序补在后面，再用 decoder[encoder[i] − 'A'] = i + 'A' 建立反查表，最后把输入串整体替换输出。

C++程序代码（点击行号可定位）
  1. 01#include <cstdlib>
  2. 02#include <iostream>
  3. 03using namespace std;
  4. 04
  5. 05char encoder[26] = {'C','S','P',0};
  6. 06char decoder[26];
  7. 07
  8. 08string st;
  9. 09
  10. 10int main() {
  11. 11 int k = 0;
  12. 12 for (int i = 0; i < 26; ++i)
  13. 13 if (encoder[i] != 0) ++k;
  14. 14 for (char x = 'A'; x <= 'Z'; ++x) {
  15. 15 bool flag = true;
  16. 16 for (int i = 0; i < 26; ++i)
  17. 17 if (encoder[i] == x) {
  18. 18 flag = false;
  19. 19 break;
  20. 20 }
  21. 21 if (flag) {
  22. 22 encoder[k] = x;
  23. 23 ++k;
  24. 24 }
  25. 25 }
  26. 26 for (int i = 0; i < 26; ++i)
  27. 27 decoder[encoder[i] - 'A'] = i + 'A';
  28. 28 cin >> st;
  29. 29 for (int i = 0; i < st.length(); ++i)
  30. 30 st[i] = decoder[st[i] - 'A'];
  31. 31 cout << st;
  32. 32 return 0;
  33. 33}
▶ 输入样例 
CSP
▶ 输出样例 
ABC
🪜 建立映射表
1 L11~L13 数出 encoder 中已有 k = 3 个字母
2 L14~L25 从 A 到 Z 扫描，把不在 encoder 中的字母依次追加 → C S P A B D E F …（跳过已出现的 C、S、P）
3 L26~L27 反查表：decoder[C]=A, decoder[S]=B, decoder[P]=C, decoder[A]=D, decoder[B]=E, decoder[D]=F …
4 L29~L30 逐字符替换后输出
5 要点：decoder[输入字符] = 输出字符，所以已知输出要倒着查表
① 输入的字符串应当只由大写字母组成，否则在访问数组时可能越界。
A. 正确 B. 错误
✅ 答案：A（正确）
解析：第 30 行用 st[i] − 'A' 当下标。若是小写字母 a，则 97 − 65 = 32 > 25，访问 decoder[32] 越界。
② 若输入的字符串不是空串，则输入的字符串与输出的字符串一定不一样。
A. 正确 B. 错误
✅ 答案：B（错误）
解析：反例：输入全由字母 T 组成。由表可知 decoder[T] = T（T 在 encoder 第 20 位，映射回 T），输入输出相同。
③ 将第 12 行的 "i < 26" 改为 "i < 16"，程序运行结果不会改变。
A. 正确 B. 错误
✅ 答案：A（正确）
解析：这个循环是统计 encoder 中非 0 元素的个数。非零元素只有前 3 个（C、S、P），后面全是 0，所以改成 i < 16（甚至 i < 3）结果都一样。
④ 将第 26 行的 "i < 26" 改为 "i < 16"，程序运行结果不会改变。
A. 正确 B. 错误
✅ 答案：B（错误）
解析：第 26 行要用 encoder 的全部 26 个位置去填 decoder。改成 i < 16 会导致下标 16~25 对应的字母没有被赋值，结果出错。
⑤ 若输出的字符串为 "ABCABCABCA"，则下列说法正确的是（　）。
A. 输入的字符串中既有 S 又有 P B. 输入的字符串中既有 S 又有 B C. 输入的字符串中既有 A 又有 P D. 输入的字符串中既有 A 又有 B
✅ 答案：A
解析：倒查表：输出 A ← 输入 C；输出 B ← 输入 S；输出 C ← 输入 P。输入串由 C、S、P 循环组成，故「既有 S 又有 P」。
⑥ 若输出的字符串为 "CSPCSPCSPCSP"，则下列说法正确的是（　）。
A. 输入的字符串中既有 P 又有 K B. 输入的字符串中既有 J 又有 R C. 输入的字符串中既有 J 又有 K D. 输入的字符串中既有 P 又有 R
✅ 答案：D
解析：倒查表：输出 C ← 输入 P；输出 S ← 输入 R；输出 P ← 输入 N。输入串由 P、R、N 循环组成，故「既有 P 又有 R」。📌 技巧：把 encoder 表写全，再按输出字符反查输入字符。

阅读 2：Floyd + 免费用一条边（第 17 题）难

先用 Floyd 求任意两点最短路 f，然后枚举每一对 (i, j)，把 i ↔ j 这条边免费（代价置 0），再以 i、j 为中转点松弛，求「所有点对距离之和」的最小值。

C++程序代码（点击行号可定位）
  1. 01#include<cstdio>
  2. 02#include<cstring>
  3. 03using namespace std;
  4. 04int n, m;
  5. 05int f[101][101];
  6. 06int F[101][101];
  7. 07int main(){
  8. 08 scanf("%d%d", &n, &m);
  9. 09 memset(f, -1, sizeof(f));
  10. 10 for(int i = 1; i <= m; i++) {
  11. 11 int u, v, w;
  12. 12 scanf("%d%d%d", &u, &v, &w);
  13. 13 f[u][v] = f[v][u] = w;
  14. 14 }
  15. 15 for(int k = 1; k <= n; k++)
  16. 16 for(int i = 1; i <= n; i++)
  17. 17 for(int j = 1; j <= n; j++)
  18. 18 if(f[i][k] != -1 && f[k][j] != -1)
  19. 19 if(f[i][j] == -1 || f[i][j] > f[k][j] + f[i][k])
  20. 20 f[i][j] = f[i][k] + f[k][j];
  21. 21 int ans = 2147483647;
  22. 22 for(int i = 1; i <= n; i++)
  23. 23 for(int j = 1; j <= n; j++){
  24. 24 for(int x = 1; x <= n; x++)
  25. 25 for(int y = 1; y <= n; y++)
  26. 26 F[x][y] = f[x][y];
  27. 27 F[i][j] = F[j][i] = 0;
  28. 28 for(int x = 1; x <= n; x++)
  29. 29 for(int y = 1; y <= n; y++)
  30. 30 if(F[x][y] == -1 || F[x][y] > F[x][i] + F[i][y])
  31. 31 F[x][y] = F[x][i] + F[i][y];
  32. 32 for(int x = 1; x <= n; x++)
  33. 33 for(int y = 1; y <= n; y++)
  34. 34 if(F[x][y] == -1 || F[x][y] > F[x][j] + F[j][y])
  35. 35 F[x][y] = F[x][j] + F[j][y];
  36. 36 int res = 0;
  37. 37 for(int x = 1; x <= n; x++)
  38. 38 for(int y = 1; y < x; y++)
  39. 39 res += F[x][y];
  40. 40 ans = min(res, ans);
  41. 41 }
  42. 42 printf("%d\n", ans);
  43. 43 return 0;
  44. 44}
▶ 输入样例 
4 5
1 2 3
1 3 6
2 3 4
2 4 7
3 4 2
▶ 输出样例 
14
🪜 样例推演（n = 4, m = 5）
1 Floyd 后各点对距离：d₁₂=3、d₁₃=6、d₁₄=8、d₂₃=4、d₂₄=6、d₃₄=2，原始总和 = 29
2 枚举 (i, j) = (1, 4)：把 1↔4 置为 0 → d₁₄ = 0、d₁₃ = 2、d₂₄ = 3、d₁₂ = 3、d₂₃ = 4、d₃₄ = 2
3 该情形总和 = 3 + 2 + 0 + 4 + 3 + 2 = 14
4 枚举 (2, 3) 得 21、(1, 2) 得 22、(3, 4) 得 27、(1, 3) 得 15、(2, 4) 得 16
5 最小值 14 输出
6 📌 两段松弛（先经 i 再经 j）等价于：d′(x,y) = min( f[x][y], f[x][i]+f[j][y], f[x][j]+f[i][y] )，即免费用一次 (i,j)。
① (1 分) 14 到 16 行，将外层到内层的循环变量依次调整为 i、j、k，程序的运行结果不变。
A. 正确 B. 错误
✅ 答案：B（错误）
解析：Floyd 的中转点 k 必须在最外层。把 k 放到最内层就退化成一次朴素松弛，随机图对比测试中有约 10% 的图结果不同，因此结果会改变。
② 这个程序的时间复杂度和 m 无关。
A. 正确 B. 错误
✅ 答案：A（正确）
解析：主导部分是三重 n 循环（O(n³)）与四重枚举 i、j、x、y（O(n⁴)），只与点数 n 有关，读入 m 条边只是 O(m)。
③ 第 21 行的 ans 如果初始化为 10⁷ 时，可能无法得到正确结果。
A. 正确 B. 错误
✅ 答案：A（正确）
解析：res 是所有点对距离之和，n = 100、每条边权值最大 10⁴ 时，res 可达 5 × 10⁹ 量级，远超 10⁷；若 ans 初值太小，min 取不到真实最小值。
④ 若将第 27 到 30 行的部分和 31 到 34 行的两个部分互换，程序的运行结果不变。
A. 正确 B. 错误
✅ 答案：B（错误）
解析：必须先置 F[i][j] = 0 再松弛。互换后，第一次松弛跑在还没免费的数组上（等于没作用），而「从 j 侧绕过来」的路径会丢失。样例中结果由 14 变成 17。
⑤ 若输入数据为 4 5 / 1 2 3 / 1 3 6 / 2 3 4 / 2 4 7 / 3 4 2（/ 为换行符），则输出为（　）。
A. 14 B. 18 C. 21 D. 28
✅ 答案：A
解析：枚举各对 (i, j) 后最小的「所有点对距离之和」为 14（免费边取 1↔4）。
⑥ 这个程序使用了（　）算法。
A. Floyd B. Dijkstra C. Prim D. Kruskal
✅ 答案：A
解析：三重循环 + 以中转点松弛的形式，是标准的 Floyd 全源最短路。

阅读 3：DFS 求无向图最长路径（第 18 题）中

邻接矩阵 e 存边权（-1 表示无边），从每个点出发 DFS 枚举所有简单路径，用 ans 记录最大总长度。visited 在回溯时恢复。

C++程序代码（点击行号可定位）
  1. 01#include<iostream>
  2. 02using namespace std;
  3. 03const int V = 100;
  4. 04int n, m, ans, e[V][V];
  5. 05bool visited[V];
  6. 06void dfs(int x, int len)
  7. 07{
  8. 08 int i;
  9. 09 visited[x] = true;
  10. 10 if(len > ans) ans = len;
  11. 11 for(i = 1; i <= n; i++)
  12. 12 if((!visited[i]) && (e[x][i] != -1))
  13. 13 dfs(i, len + e[x][i]);
  14. 14 visited[x] = false;
  15. 15}
  16. 16int main()
  17. 17{
  18. 18 int i, j, a, b, c;
  19. 19 cin >> n >> m;
  20. 20 for(i = 1; i <= n; i++)
  21. 21 for(j = 1; j <= n; j++)
  22. 22 e[i][j] = -1;
  23. 23 for(i = 1; i <= m; i++){
  24. 24 cin >> a >> b >> c;
  25. 25 e[a][b] = c;
  26. 26 e[b][a] = c;
  27. 27 }
  28. 28 for(i = 1; i <= n; i++)
  29. 29 visited[i] = false;
  30. 30 ans = 0;
  31. 31 for(i = 1; i <= n; i++)
  32. 32 dfs(i, 0);
  33. 33 cout << ans << endl;
  34. 34 return 0;
  35. 35}
▶ 输入样例 
4 2
1 2 1
3 4 1
▶ 输出样例 
1
🪜 样例 (3)：n=4，两条边 1−2(1)、3−4(1)
1 L20~L22 邻接矩阵全部初始化为 −1（无边）
2 L23~L27 无向边双向赋值
3 L31~L32 以每个点为起点各搜一次（保证不漏掉任何路径）
4 从 1 出发：只能走到 2，长度 1；从 3 出发：走到 4，长度 1
5 图中没有长度 > 1 的路径，ans = 1
① 第 19 行的输入中，如果满足 m = n × (n − 1) / 2，则 20~22 行的初始化可以省略。
A. 正确 B. 错误
✅ 答案：A（正确）
解析：m = n(n−1)/2 说明是完全图，每个 i ≠ j 的边权都会被读入覆盖；对角线 e[i][i] 虽然保持 0 而非 −1，但 DFS 中 visited[i] 已为真，不会走自己，因此结果不变。
② 将第 31 行的代码换成 "for(i = n; i >= 1; i--)"，程序结果不受任何影响。
A. 正确 B. 错误
✅ 答案：A（正确）
解析：第 31~32 行只是枚举起点，ans 取的是全局最大值，与枚举顺序无关。
(3) 若输入的数据为 4 2 / 1 2 1 / 3 4 1，则程序的输出结果是（　）。
A. 8 B. 4 C. 2 D. 1
✅ 答案：D
解析：图由两条独立边组成，最长路径只有 1 条边，输出 1。
(4) 若输入的数据为 4 6 / 1 2 1 / 2 3 1 / 3 4 1 / 4 1 1 / 1 3 1 / 2 4 1，则程序的输出结果是（　）。
A. 1 B. 3 C. 5 D. 7
✅ 答案：B
解析：这是 4 个点的完全图、边权全为 1，最长简单路径经过 3 条边 → 3。
(5) 若输入的数据为 4 3 / 1 2 10 / 2 3 20 / 3 4 30，则程序的输出结果是（　）。
A. 30 B. 60 C. 90 D. 120
✅ 答案：B
解析：图是一条链 1−2−3−4，最长路径就是整条链：10 + 20 + 30 = 60。
(6) 若输入的数据为 4 6 / 1 2 10 / 2 3 20 / 3 4 30 / 4 1 40 / 1 3 50 / 2 4 60，则程序的输出结果是（　）。
A. 60 B. 100 C. 150 D. 200
✅ 答案：C
解析：枚举 4 个点的所有排列取最大：2→4(60)→1(40)→3(50) = 150（3→1→4→2 同样得 150），其余排列如 1→3→4→2 = 140、1→2→4→3 = 100，故最大为 150。

三、完善程序（第 19~20 题，每空 3 分）

完善 1：封禁 xxs（基环树贪心，第 19 题）难

每个 i 关注 a[i]（i → a[i]）。封禁 i 就不能封禁 a[i]。先处理入度为 0 的链头，沿链交错封禁；再处理剩下的环。in[j] 记录 j 还有多少个前驱没处理完。

C++程序代码（带 ①~⑤ 填空标记）
  1. 01#include<cstdio>
  2. 02using namespace std;
  3. 03#define MAXN 300005
  4. 04int n, ans = 0, a[MAXN], in[MAXN] = {0};
  5. 05bool vis[MAXN] = {0};
  6. 06void dfs(int cur, int w){
  7. 07 if(vis[cur])
  8. 08 return;
  9. 09 vis[cur] = true;
  10. 10 if(w == 1) ans++;
  11. 11 ①
  12. 12 if( ② )
  13. 13 dfs(a[cur], ③ );
  14. 14}
  15. 15int main(){
  16. 16 scanf("%d", &n);
  17. 17 for(int i = 1; i <= n; i++){
  18. 18 scanf("%d", &a[i]);
  19. 19 in[a[i]]++;
  20. 20 }
  21. 21 for(int i = 1; i <= n; i++)
  22. 22 if(!in[i]) ④ ;
  23. 23 for(int i = 1; i <= n; i++)
  24. 24 if( ⑤ ) dfs(i, 0);
  25. 25 printf("%d\n", ans);
  26. 26 return 0;
  27. 27}
第①空选项
A. a[cur] = cur;
B. in[a[cur]] = 0;
C. in[a[cur]]--;
D. in[cur]--;
第②空选项
A. in[a[cur]] != 0 || w == 1
B. in[a[cur]] == 0 || w == 0
C. in[a[cur]] != 0 || w == 0
D. in[a[cur]] == 0 || w == 1
第③空选项
A. 0
B. 1
C. w
D. 1 - w
第④空选项
A. dfs(i, 1)
B. dfs(i, 0)
C. dfs(a[i], 1)
D. dfs(a[i], 0)
第⑤空选项
A. !in[i]
B. in[i]
C. !vis[i]
D. vis[i]
📋 查看各空答案与解析

第①空：C　cur 处理完了，把它对后继的贡献去掉：in[a[cur]]--（a[cur] 少了一个未处理的前驱）。

第②空：D　继续往上走的条件：① a[cur] 的所有前驱都处理完了（in[a[cur]] == 0），或 ② cur 本身已被封禁（w == 1）——此时 a[cur] 一定不能被封禁，可以立刻带着 w = 0 走上去，不必再等。
📌 写成 || w == 0 会出错：cur 没被封禁就急着上去封禁 a[cur]，可能被另一条链上的前驱冲突。

第③空：D　状态取反：本次封禁了 cur，后继就不能封禁；本次没封禁，后继就可以封 → 1 − w。

第④空：A　从入度为 0 的链头出发，第一个点应当被封禁（贪心最优）→ dfs(i, 1)。

第⑤空：C　第二遍处理环：还有没访问过的点说明它在一个环上，随便挑一个进入即可 → !vis[i]，并用 w = 0 起步（环上最优为 ⌊len/2⌋）。

🪜 样例：n = 3，a = [2, 3, 1]（一个三元环）
1 读入后 in[1] = in[2] = in[3] = 1，没有入度为 0 的点，第一遍循环直接跳过
2 第二遍 i = 1：!vis[1] 成立 → dfs(1, 0)：w = 0 不封禁，in[a[1]] = in[2]-- → 0
3 条件：in[2] == 0 ✓ → dfs(2, 1 - 0 = 1)：封禁 2，ans = 1，in[3]-- → 0
4 条件 ✓ → dfs(3, 1 - 1 = 0)：不封禁 3，in[1]-- → 0
5 条件 ✓ → dfs(1, 1) 但 vis[1] 已为真，直接返回
6 输出 ans = 1（环长 3，最多封禁 ⌊3/2⌋ = 1 个 ✓）

完善 2：判断二叉查找树（第 20 题）中

递归判断：当前结点的值必须落在 (lower_bound, upper_bound) 开区间内，左子树上界收缩为当前值，右子树下界抬升为当前值。

C++程序代码（带 ①~⑤ 填空标记）
  1. 01#include <iostream>
  2. 02using namespace std;
  3. 03const int SIZE = 100;
  4. 04const int INFINITE = 1000000;
  5. 05struct node
  6. 06{
  7. 07 int left_child, right_child, value;
  8. 08}; node a[SIZE];
  9. 09int is_bst( int root, int lower_bound, int upper_bound )
  10. 10{
  11. 11 int cur;
  12. 12 if ( root == 0 )
  13. 13 return(1);
  14. 14 cur = a[root].value;
  15. 15 if ( (cur > lower_bound) && ( ① ) && (is_bst( a[root].left_child, lower_bound, cur ) == 1) && (is_bst( ② , ③ , ④ ) == 1) )
  16. 16 return(1);
  17. 17 return(0);
  18. 18}
  19. 19
  20. 20int main()
  21. 21{
  22. 22 int i, n; cin >> n;
  23. 23 for ( i = 1; i <= n; i++ )
  24. 24 cin >> a[i].value >> a[i].left_child >> a[i].right_child;
  25. 25 cout << is_bst( ⑤ , -INFINITE, INFINITE ) << endl;
  26. 26 return(0);
  27. 27}
第①空选项
A. cur &lt; upper_bound
B. cur &gt;= upper_bound
C. cur &lt; lower_bound
D. cur != upper_bound
第②空选项
A. root
B. a[root].left_child
C. a[root].right_child
D. a[root].value
第③空选项
A. lower_bound
B. upper_bound
C. cur
D. -INFINITE
第④空选项
A. lower_bound
B. upper_bound
C. cur
D. INFINITE
第⑤空选项
A. a[1].left_child
B. a[1].right_child
C. a[1].value
D. 1
📋 查看各空答案与解析

第①空：A　当前值还要小于上界：cur < upper_bound，与前面的 cur > lower_bound 配对成开区间。

第②空：C　递归右子树，结点编号为 a[root].right_child。

第③空：C　右子树的新下界 = 当前结点的值 cur（右子树所有值都要大于它）。

第④空：B　右子树的上界不变，仍是 upper_bound。对比上一行左子树调用 is_bst(a[root].left_child, lower_bound, cur)，左右两边是对称的「一界收缩、一界不变」。

第⑤空：D　题目说明 1 号结点是根，且第一个参数是编号不是值 → 传 1。

🪜 为什么要用「上下界」而不是只比较父子
1 只比较「左孩子 < 根 < 右孩子」是不够的：右子树里可能出现比根更小的结点，那样也破坏 BST 性质
2 正确做法：给每个结点带一个允许取值的开区间 (lower, upper)
3 往左走：上界变成根的值；往右走：下界变成根的值
4 根结点 1 的初始区间是 (−INFINITE, INFINITE)
5 每个结点只做 O(1) 判断，整体 O(n)