🏠

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

选择题 15 题 + 阅读程序 3 段 + 完善程序 2 段 · 含双指针、DFS 最长路、区间覆盖贪心与最大子矩阵

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

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

1. 易 中国计算机学会于（　）年创办全国青少年计算机程序设计竞赛。
A. 1983 B. 1984 C. 1985 D. 1986
✅ 正确答案：B
解析：1984 年创办（同年邓小平提出「计算机的普及要从娃娃抓起」），这就是 NOI 系列赛事的起点。
2. 易 一个 32 位整型变量占用（　）个字节。
A. 4 B. 8 C. 32 D. 128
✅ 正确答案：A
解析：32 bit = 32 ÷ 8 = 4 字节。
3. 易 下列四个不同进制的数中，与其它三项数值上不相等的是（　）。
A. (269)16 B. (617)10 C. (1151)8 D. (1001101011)2
✅ 正确答案：D
解析：A = 2×16² + 6×16 + 9 = 617；B = 617；C = 1×8³ + 1×8² + 5×8 + 1 = 617；D = 512 + 64 + 32 + 8 + 2 + 1 = 619。不同的只有 D。
4. 中 根节点深度为 0，一棵深度为 h 的满 k（k > 1）叉树共有（　）个结点。
A. (kh+1 − 1)/(k − 1) B. kh−1 C. kh D. kh−1/(k − 1)
✅ 正确答案：A
解析：各层结点数 1、k、k²、…、kh，等比数列求和 = (kh+1 − 1)/(k − 1)。
📌 取 k = 2、h = 2 的满二叉树（7 个结点）代入，只有 A 得 7。
5. 中 s = a; for (b = 1; b <= c; b++) s = s + 1;（c > 0），与这段程序功能等价的赋值语句是（　）。
A. s = a + b B. s = a + c C. s = s + c D. s = b + c
✅ 正确答案：B
解析：s 初值为 a，循环执行 c 次、每次加 1 ⇒ s = a + c。
6. 中 一张分辨率为 2048 × 1024 像素的 32 位真彩色图像，需要的存储空间为（　）。
A. 16MB B. 4MB C. 8MB D. 2MB
✅ 正确答案：C
解析：2048 × 1024 × (32 ÷ 8) B = 2048 × 1024 × 4 B = 8 × 1024 × 1024 B = 8 MB。
7. 中 设简单无向图 G 有 16 条边且每个顶点的度数都是 2，则图 G 有（　）个顶点。
A. 10 B. 12 C. 8 D. 16
✅ 正确答案：D
解析：握手定理：度数之和 = 2 × 边数 = 32。每个顶点度数为 2 → 顶点数 = 32 ÷ 2 = 16（图由若干个环组成）。
8. 中 程序欲计算 s = 1 + 1/2 + 1/3 + … + 1/10，但结果错误，导致错误结果的程序行是（　）。
s = 1.0; for(n = 10; n > 1; n--) s = s + 1 / n;
A. s = 1.0; B. for(n = 10; n > 1; n--) C. s = s + 1 / n; D. cout << s << endl;
✅ 正确答案：C
解析：n 是 int，1 / n 是整数除法，n > 1 时恒为 0，累加毫无效果。应改为 1.0 / n 或 (float)1 / n。
9. 中 在 8 位二进制补码中，10101011 表示的数是十进制下的（　）。
A. 43 B. -85 C. -43 D. -84
✅ 正确答案：B
解析：10101011 − 1 = 10101010，取反得 11010101 = −(64 + 16 + 4 + 1) = −85。
10. 难 有五副不同颜色的手套（共 10 只，每副左右手各 1 只），一次性从中取 6 只，恰好能配成两副手套的不同取法有（　）种。
A. 120 B. 180 C. 150 D. 30
✅ 正确答案：A
解析：先从 5 种颜色里选出「配成两副」的 2 种颜色：C(5,2) = 10 种；再从剩下 3 种颜色里挑 2 种各取 1 只（不成对）：C(3,2) = 3 种；每种可左可右：2 × 2 = 4 种。
总数 = 10 × 3 × 4 = 120。
11. 中 如果根的高度为 1，具有 61 个结点的完全二叉树的高度为（　）。
A. 5 B. 6 C. 7 D. 8
✅ 正确答案：B
解析：高度为 h（根为 1）的完全二叉树最多有 2h − 1 个结点。2⁵ − 1 = 31 < 61 ≤ 2⁶ − 1 = 63 ⇒ 高度为 6。
12. 易 下列几个 32 位 IP 地址中，书写错误的是（　）。
A. 162.105.135.27 B. 192.168.0.1 C. 256.256.129.1 D. 10.0.0.1
✅ 正确答案：C
解析：每段取值范围是 0 ~ 255，256 越界，书写错误。
13. 易 寄存器是（　）的重要组成部分。
A. 硬盘 B. 高速缓存 C. 内存 D. 中央处理器（CPU）
✅ 正确答案：D
解析：寄存器在 CPU 内部，是最快的存储单元。
14. 易 下列协议中与电子邮件无关的是（　）。
A. POP3 B. SMTP C. WTO D. IMAP
✅ 正确答案：C
解析：SMTP 发送、POP3 / IMAP 接收，都是邮件协议；WTO 是世界贸易组织。
15. 难 小明洗菜、爸爸切菜、妈妈炒菜，做每道菜都要依次经过这三步、每步 10 分钟；两道不同菜的相同步骤不能同时进行。那么做完三道菜最短需要（　）分钟。
A. 90 B. 60 C. 50 D. 40
✅ 正确答案：C
解析：流水线排程：
0~10：洗菜 1
10~20：切菜 1 ＋ 洗菜 2
20~30：炒菜 1 ＋ 切菜 2 ＋ 洗菜 3
30~40：炒菜 2 ＋ 切菜 3
40~50：炒菜 3
总共 50 分钟。

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

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

与第三套第 16 题同一段程序：先把 A~Z 中未出现的字母补进 encoder，再用 decoder 反查，最后整体替换字符串。

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 补齐后的 encoder：C S P A B D E F …（跳过已出现的 C、S、P）
2 decoder：C→A，S→B，P→C，A→D，B→E，D→F，E→G，F→H，G→I，H→J，I→K，J→L，K→M，L→N，M→O，N→P，O→Q，Q→R，R→S，T→T …
3 第 30 行 st[i] = decoder[st[i] - 'A']：输入字符 → 输出字符
4 由表倒查：输出 A ← 输入 C；输出 B ← 输入 S；输出 C ← 输入 P
5 输出 S ← 输入 R；输出 P ← 输入 N
① 输入的字符串应当只由大写字母组成，否则在访问数组时可能越界。
A. 正确 B. 错误
✅ 答案：A（正确）
解析：下标是 st[i] − 'A'，小写字母会得到 32 以上，越界。
② 若输入的字符串不是空串，则输入的字符串与输出的字符串一定不一样。
A. 正确 B. 错误
✅ 答案：B（错误）
解析：反例：输入全为字母 T（decoder[T] = T），输入输出相同。
③ 将第 12 行的 "i < 26" 改为 "i < 16"，程序运行结果不会改变。
A. 正确 B. 错误
✅ 答案：A（正确）
解析：该循环只统计 encoder 中非 0 的个数，非零元素只有前 3 个。
④ 将第 26 行的 "i < 26" 改为 "i < 16"，程序运行结果不会改变。
A. 正确 B. 错误
✅ 答案：B（错误）
解析：第 26 行要用 26 个位置填满 decoder，改成 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」成立。

阅读 2：双指针扫描（第 17 题）难

ans 是一个「只增不减（但可能被重置）」的右端点。对每个 i：若出现下降则把 ans 重置为 i，然后尽可能向右扩展，最后输出 ans。

C++程序代码（点击行号可定位）
  1. 01#include <cstdio>
  2. 02using namespace std;
  3. 03int n;
  4. 04int a[100];
  5. 05
  6. 06int main() {
  7. 07 scanf("%d", &n);
  8. 08 for (int i = 1; i <= n; ++i)
  9. 09 scanf("%d", &a[i]);
  10. 10 int ans = 1;
  11. 11 for (int i = 1; i <= n; ++i) {
  12. 12 if (i > 1 && a[i] < a[i - 1])
  13. 13 ans = i;
  14. 14 while (ans < n && a[i] >= a[ans + 1])
  15. 15 ++ans;
  16. 16 printf("%d\n", ans);
  17. 17 }
  18. 18 return 0;
  19. 19}
▶ 输入样例 
5
1 2 3 4 5
▶ 输出样例 
1
2
3
4
5
🪜 以 a = [2, 1, 3] 为例（n = 3）
1 i = 1：i > 1 不成立，ans 保持 1；while：a[1] = 2 ≥ a[2] = 1 → ans = 2；a[1] = 2 ≥ a[3] = 3？否 → 停。输出 2
2 i = 2：a[2] = 1 < a[1] = 2 → ans 重置为 2；while：a[2] = 1 ≥ a[3] = 3？否 → 停。输出 2
3 i = 3：a[3] = 3 > a[2] = 1，不重置；while：ans = 2 < 3 且 a[3] = 3 ≥ a[3] = 3 → ans = 3。输出 3
4 结论：ans 单调右移，遇到「下降」时被拉回 i，因此最坏情况总代价可达 O(n²)
① （1 分）第 16 行输出 ans 时，ans 的值一定大于 i。
A. 正确 B. 错误
✅ 答案：B（错误）
解析：反例 a = [2, 1, 3]：i = 2 时 a[2] < a[1]，ans 被重置为 2，且 a[2] = 1 < a[3] = 3 无法右移，输出 ans = 2 = i，并不大于 i。
② （1 分）程序输出的 ans 小于等于 n。
A. 正确 B. 错误
✅ 答案：A（正确）
解析：while 的条件是 ans < n，且重置时 ans = i ≤ n，所以 ans 永远不会超过 n。
③ （1.5 分）若将第 12 行的 "<" 改为 "!="，程序输出的结果不会改变。
A. 正确 B. 错误
✅ 答案：B（错误）
解析：改成 != 后，上升（a[i] > a[i−1]）时也会把 ans 重置到 i，而原程序此时保留上一轮的 ans（可能 > i），两者输出不同。
④ （1.5 分）当程序执行到第 16 行时，若 ans − i > 2，则 a[i+1] ≤ a[i]。
A. 正确 B. 错误
✅ 答案：A（正确）
解析：ans − i > 2 说明 while 循环至少进入了 2 次，第一次进入就意味着 a[i] ≥ a[ans+1]（初始 ans = i 时为 a[i] ≥ a[i+1]）成立。
⑤ （3 分）若输入的 a 数组严格单调递增，此程序的时间复杂度为（　）。
A. O(log n) B. O(n²) C. O(n log n) D. O(n)
✅ 答案：D
解析：严格递增时 ans 从不重置，每轮 while 最多走 1 步，总步数 O(n)。
⑥ （4 分）最坏情况下，此程序的时间复杂度是（　）。
A. O(n²) B. O(log n) C. O(n) D. O(n log n)
✅ 答案：A
解析：「先降后升」的序列会让 ans 反复被重置再重新右移，例如 a = [n, n−1, …, 1, n, n−1, …]，每个 i 都可能推进 O(n) 步 → 最坏 O(n²)。

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

邻接矩阵存边权（-1 表示无边），从每个点出发 DFS 枚举所有简单路径取最大值。与第三套第 18 题同一段程序。

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
🪜 通用思路
1 L20~L22 邻接矩阵初始化为 −1
2 L23~L27 无向边双向存储
3 L09/L14 进入标记、回溯时取消标记（枚举所有简单路径）
4 L31~L32 以每个点为起点各搜一遍，保证不漏
① 第 19 行的输入中，如果满足 m = n × (n − 1) / 2，则 20~22 行的初始化可以省略。
A. 正确 B. 错误
✅ 答案：A（正确）
解析：完全图中每条边都会被读入覆盖，对角线虽保持 0 但因 visited 而不会走到，结果不变。
② 将第 31 行换成 "for(i = n; i >= 1; i--)"，程序结果不受任何影响。
A. 正确 B. 错误
✅ 答案：A（正确）
解析：只是改变起点枚举顺序，ans 取全局最大值，与顺序无关。
(3) 若输入的数据为 4 2 / 1 2 1 / 3 4 1，则输出结果是（　）。
A. 8 B. 4 C. 2 D. 1
✅ 答案：D
解析：两条互不相连的边，最长路径长为 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
解析：最优路径 2→4(60)→1(40)→3(50) = 150（或 3→1→4→2 同为 150）。

三、完善程序（第 19~20 题）

完善 1：最小区间覆盖（贪心，第 19 题）难

先用 O(n²) 冒泡按左端点升序排序，再去掉被完全包含的区间，最后贪心：每次在「起点不超过当前已覆盖右端」的区间中选右端点最远的那个。

C++程序代码（带 ①~⑤ 填空标记）
  1. 01#include <iostream>
  2. 02
  3. 03using namespace std;
  4. 04
  5. 05const int MAXN = 5000;
  6. 06int n, m;
  7. 07struct segment { int a, b; } A[MAXN];
  8. 08
  9. 09void sort() // 排序
  10. 10{
  11. 11 for (int i = 0; i < n; i++)
  12. 12 for (int j = 1; j < n; j++)
  13. 13 if ( ① )
  14. 14 {
  15. 15 segment t = A[j];
  16. 16 ②
  17. 17 }
  18. 18}
  19. 19
  20. 20int main()
  21. 21{
  22. 22 cin >> n >> m;
  23. 23 for (int i = 0; i < n; i++)
  24. 24 cin >> A[i].a >> A[i].b;
  25. 25 sort();
  26. 26 int p = 1;
  27. 27 for (int i = 1; i < n; i++)
  28. 28 if ( ③ )
  29. 29 A[p++] = A[i];
  30. 30 n = p;
  31. 31 int ans = 0, r = 0;
  32. 32 int q = 0;
  33. 33 while (r < m)
  34. 34 {
  35. 35 while ( ④ )
  36. 36 q++;
  37. 37 ⑤ ;
  38. 38 ans++;
  39. 39 }
  40. 40 cout << ans << endl;
  41. 41 return 0;
  42. 42}
第①空选项
A. A[j].b &gt; A[j-1].b
B. A[j].a &lt; A[j-1].a
C. A[j].a &gt; A[j-1].a
D. A[j].b &lt; A[j-1].b
第②空选项
A. A[j+1] = A[j]; A[j] = t;
B. A[j-1] = A[j]; A[j] = t;
C. A[j] = A[j+1]; A[j+1] = t;
D. A[j] = A[j-1]; A[j-1] = t;
第③空选项
A. A[i].b &gt; A[p-1].b
B. A[i].b &lt; A[i-1].b
C. A[i].b &gt; A[i-1].b
D. A[i].b &lt; A[p-1].b
第④空选项
A. q + 1 &lt; n &amp;&amp; A[q + 1].a &lt;= r
B. q + 1 &lt; n &amp;&amp; A[q + 1].b &lt;= r
C. q &lt; n &amp;&amp; A[q].a &lt;= r
D. q &lt; n &amp;&amp; A[q].b &lt;= r
第⑤空选项
A. r = max(r, A[q + 1].b)
B. r = max(r, A[q].b)
C. r = max(r, A[q + 1].a)
D. q++
📋 查看各空答案与解析

第①空：B　按左端点升序：A[j].a < A[j−1].a 时交换（冒泡：把小的往前推）。按右端点排序也行，但后面第 3 空要依赖「起点已有序」，所以这里排左端点。

第②空：D　冒泡交换的两步：先用 t 存下 A[j]，把 A[j−1] 挪到 j 位，再把 t 放到 j−1 位。

第③空：A　去重（去掉被包含的区间）：起点已升序，只有当新区间的右端点比已保留的最后一个更远（A[i].b > A[p−1].b）才值得保留。

第④空：A　找最后一个「起点 ≤ 当前覆盖右端 r」的区间：条件写成 A[q + 1].a <= r 就让 q 最终停在最后一个可行区间上（若写成 A[q].a <= r，q 会停在第一个不可行区间，第 5 空就得改成 q − 1）。

第⑤空：B　用这个区间的右端点去延伸覆盖：r = max(r, A[q].b)，然后 ans++。

🪜 贪心流程串讲
1 第 1、2 空：按左端点从小到大排序（题面要求的 O(n²) 冒泡）
2 第 3 空：扫描一遍，只保留「右端点比上一个保留的更远」的区间 → 去掉被包含的
3 第 4 空：内层 while 把 q 推进到最后一个起点不超过 r 的区间
4 第 5 空：r = max(r, A[q].b)，即选这些区间里右端点最远的（贪心）
5 ans++ 表示多选了一个区间；直到 r ≥ m 结束

完善 2：最大子矩阵和（第 20 题）难

先算每一行的前缀和 rowsum，再枚举子矩阵的左右列 first、last，把每一行的贡献累加起来做一次「最大子段和」（Kadane）。

C++程序代码（带 ①~⑤ 填空标记）
  1. 01#include <iostream>
  2. 02using namespace std;
  3. 03const int SIZE = 100;
  4. 04int matrix[SIZE + 1][SIZE + 1];
  5. 05int rowsum[SIZE + 1][SIZE + 1]; /* rowsum[i][j] 记录第 i 行前 j 个数的和 */
  6. 06int m, n, i, j, first, last, area, ans;
  7. 07int main()
  8. 08{
  9. 09 cin >> m >> n;
  10. 10 for ( i = 1; i <= m; i++ )
  11. 11 for ( j = 1; j <= n; j++ )
  12. 12 cin >> matrix[i][j];
  13. 13 ans = matrix ① ;
  14. 14 for ( i = 1; i <= m; i++ )
  15. 15 ② ;
  16. 16 for ( i = 1; i <= m; i++ )
  17. 17 for ( j = 1; j <= n; j++ )
  18. 18 rowsum[i][j] = ③ ;
  19. 19 for ( first = 1; first <= n; first++ )
  20. 20 for ( last = first; last <= n; last++ )
  21. 21 {
  22. 22 ④ ;
  23. 23 for ( i = 1; i <= m; i++ )
  24. 24 {
  25. 25 area += ⑤ ;
  26. 26 if ( area > ans )
  27. 27 ans = area;
  28. 28 if ( area < 0 )
  29. 29 area = 0;
  30. 30 }
  31. 31 }
  32. 32 cout << ans << endl;
  33. 33 return 0;
  34. 34}
📋 查看各空答案与解析

第①空：[1][1]（矩阵中任意一个元素，如 [m][n] 也可）　ans 的初值必须取矩阵里的某个元素（子矩阵不能为空，且元素可能为负），写成 0 会在全负矩阵上出错。取 matrix[1][1]、[1][n]、[m][1]、[m][n] 都可以。

第②空：rowsum[i][0] = 0　第 i 行前 0 个数的和为 0，这是后面前缀和递推的边界。

第③空：rowsum[i][j - 1] + matrix[i][j]　前缀和递推：前 j 列的和 = 前 j−1 列的和 + 第 j 列的元素。

第④空：area = 0　每次更换 (first, last) 都要把累加器清零，重新开始一次最大子段和。

第⑤空：rowsum[i][last] - rowsum[i][first - 1]　第 i 行从 first 到 last 的和 = 前 last 列的和 − 前 first−1 列的和。

🪜 用题面样例验证（4×4 矩阵，答案 15）
1 样例矩阵：0 −2 −7 0 / 9 2 −6 2 / −4 1 −4 1 / −1 8 0 −2
2 逐行求前缀和 rowsum
3 枚举 first = 2、last = 3（第 2~3 列）时：各行贡献 −9、−4、−3、8
4 对这几项做最大子段和：8 + (−3) + (−4)…取到 15（对应子矩阵 9 2 / −4 1 / −1 8，和 = 15）
5 枚举完所有 (first, last) 后 ans = 15，与题面一致 ✓