朝外信奥 2 队 2026-06-21 笔试训练题目

答案版
考试时间：6月21日
满分：100 分
题型说明：单项选择题 15 题，每题 2 分，共 30 分；阅读程序题 11 题，共 40 分；完善程序题 5 题，每题 6 分，共 30 分。
一、单项选择题（共15题，每题2分，共30分）
1. 在标准 ASCII 码表中，已知英文字母 c 的 ASCII 码十进制表示是 99，那么英文字母 x 的 ASCII 码十六进制表示是（ ）。
A. 77
B. 78
C. 79
D. 7A
答案：B。本题 2 分。
2. 以下关于 CSP 与 GESP 的描述正确的是（ ）。
A. CSP-J/CSP-S 属于非专业级别软件能力认证，只有中小学生才能参加
B. CSP-J/CSP-S 是中国通信学会举办的程序设计竞赛
C. GESP 是中国电子学会举办的程序设计竞赛
D. GESP C++ 七级成绩 80 分及以上或者八级成绩 60 分及以上，可以申请免 CSP-J 初赛
答案：D。本题 2 分。
3. 以下可以用作 C++ 程序中的变量名的是（ ）。
A. _x1
B. new
C. class
D. public
答案：A。本题 2 分。
4. 以下不属于桌面或者手机操作系统的是（ ）。
A. Linux
B. Android
C. MATLAB
D. Windows 11
答案：C。本题 2 分。
5. 在 C++ 中，如果想用 cout 输出变量 x，并保留 3 位小数，应该写成（ ）。
A. cout << setprecision(3) << x;
B. cout << fixed << setprecision(3) << x;
C. cout << fixed << x << setprecision(3);
D. cout << precision(3) << fixed << x;
答案：B。本题 2 分。
6. 寻找最短路径的广度优先搜索算法经常用到的数据结构是（ ）。
A. 栈
B. 链表
C. 向量
D. 队列
答案：D。本题 2 分。
7. 以下哪个域名后缀不属于中华人民共和国管辖？（ ）
A. cn
B. uk
C. hk
D. mo
答案：B。本题 2 分。
8. 一棵有 n 个结点的树，一定有（ ）条边。
A. n
B. n + 1
C. n - 1
D. 2n
答案：C。本题 2 分。
9. 关于计算机网络，下面的说法中正确的是（ ）。
A. TCP 是网络层协议
B. 计算机病毒只能通过 U 盘等介质传播，不能通过计算机网络传播
C. 计算机网络可以实现资源共享
D. 公司内部的几台计算机组成的网络规模太小，不能称为计算机网络
答案：C。本题 2 分。
10. 序列 (7, 5, 1, 12, 3, 6, 9, 4) 中有（ ）个逆序对。
A. 15
B. 12
C. 13
D. 14
答案：D。本题 2 分。
11. 下列属于图像文件格式的是（ ）。
A. MPEG
B. DOCX
C. JPEG
D. WMV
答案：C。本题 2 分。
12. 无论命题 P、Q 的真假如何取值，以下逻辑表达式中一定为假的是（ ）。
A. P ∨ Q
B. P ∧ Q
C. P ∧ ¬P
D. ¬P ∨ Q
答案：C。本题 2 分。
13. 树的根结点的高度为 1，某完全二叉树有 2025 个结点，其高度是（ ）。
A. 10
B. 11
C. 12
D. 13
答案：B。本题 2 分。
14. 现有 9 个苹果，要放入 5 个不同的盘子，允许有的盘子中放 0 个苹果，则不同的放法共有（ ）种。
A. 720
B. 715
C. 126
D. 252
答案：B。本题 2 分。
设 5 个盘子中分别放 x1,x2,x3,x4,x5 个苹果。因为盘子不同，且允许某些盘子放 0 个，所以问题等价于求非负整数解的个数：x1 + x2 + x3 + x4 + x5 = 9。
用隔板法：9 个苹果排成一排，需要在其中插入 4 块隔板，把它们分成 5 组；允许空盘子，等价于在 9 + 4 = 13 个位置中选择 4 个位置放隔板。
因此共有 C(13,4) = 13 × 12 × 11 × 10 / (4 × 3 × 2 × 1) = 715 种放法。
15. G 是一个非连通无向图（没有重边和自环），共有 36 条边，则该图至少有（ ）个顶点。
A. 6
B. 9
C. 10
D. 8
答案：C。本题 2 分。
二、阅读程序题（共17题，共40分）

判断题正确填 A，错误填 B。阅读程序题共 40 分：第 16~18、21~23 题每题 3 分，第 19~20、24~25 题每题 4 分，第 26 题 6 分。

（一）阅读下面程序，回答第 16~20 题
  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. using i64 = long long;
  6. int popcount(i64 x)
  7. {
  8. int res = 0;
  9. while (x)
  10. {
  11. if (x & 1 == 1)
  12. res++;
  13. x >>= 1;
  14. }
  15. return res;
  16. }
  18. int calc(i64 x)
  19. {
  20. int sum = 0;
  21. for (i64 i = 1; i <= x; i++)
  22. sum += popcount(i);
  23. return sum;
  24. }
  26. int sum(i64 l, i64 r)
  27. {
  28. return calc(r) - calc(l);
  29. }
  31. int main()
  32. {
  33. i64 l, r;
  34. cin >> l >> r;
  35. cout << calc(l) << ' ' << sum(l, r) << endl;
  36. return 0;
  37. }
16. 若程序输入为 5 8，则程序输出 7 6。（ ）
A. TRUE
B. FALSE
答案：A。本题 3 分。
popcount(x) 统计 x 的二进制中 1 的个数，calc(x) 统计 1 到 x 的所有 1 的个数。
输入 5 8 时，calc(5)=1+1+2+1+2=7；sum(5,8)=calc(8)-calc(5)，也就是统计 6,7,8，结果为 2+3+1=6，所以输出 7 6。
17. 若将第 11 行中的 & 符号改为 ^ 符号，程序输出结果一定不会改变。（ ）
A. TRUE
B. FALSE
答案：B。本题 3 分。
原式 x & 1 == 1 会按优先级理解为 x & (1 == 1)，等价于 x & 1，用于判断最低位是否为 1。
若改成 x ^ 1 == 1，会变成 x ^ (1 == 1)，即 x ^ 1，含义完全不同。例如 x=1 时原判断为真，修改后为假，因此输出可能改变。
18. 若将头文件 #include <bits/stdc++.h> 改成 #include <stdio.h>，程序仍能正常运行。（ ）
A. TRUE
B. FALSE
答案：B。本题 3 分。
程序使用了 cin、cout、endl 等 C++ 输入输出对象，它们来自 C++ 标准库相关头文件。stdio.h 是 C 风格输入输出头文件，不提供这些对象，所以替换后程序不能正常编译运行。
19. 若输入为 1 12，则输出是什么？（ ）
A. 1 21
B. 1 20
C. 1 22
D. 2 22
答案：A。本题 4 分。
第一项输出 calc(1)，只统计数字 1 的二进制中 1 的个数，所以为 1。
第二项为 sum(1,12)=calc(12)-calc(1)，等价于统计 2 到 12 的二进制 1 的总数：1+2+1+2+2+3+1+2+2+3+2=21。因此输出 1 21。
20. 程序中的 sum 函数实现了什么功能？（ ）
A. 计算 [l,r] 区间内每个数二进制位上 1 的个数之和
B. 计算 [l,r] 区间内每个数二进制位上 0 的个数之和
C. 计算 (l,r] 区间内每个数二进制位上 1 的个数之和
D. 计算 (l,r] 区间内每个数二进制位上 0 的个数之和
答案：C。本题 4 分。
calc(r) 统计 1 到 r 每个数二进制中 1 的个数之和，calc(l) 统计 1 到 l。
两者相减后，1 到 l 的部分被抵消，剩下的就是 l+1 到 r，也就是区间 (l,r] 内每个数二进制位上 1 的个数之和。
（二）阅读下面程序，回答第 21~26 题
  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int inf = 0x3f3f3f3f;
  6. int solve(vector<int> &cur)
  7. {
  8. int n = cur.size();
  9. vector<vector<int>> dp(n + 1, vector<int>(n + 1, inf));
  10. for (int i = 0; i <= n; i++)
  11. dp[0][i] = dp[i][0] = 0;
  12. for (int i = 1; i <= n; i++)
  13. dp[i][i] = cur[i - 1];
  14. for (int i = 1; i <= n; i++)
  15. for (int j = 1; j <= n; j++)
  16. if (i != j)
  17. dp[i][j] = min(dp[i][j], dp[i - 1][j] + dp[i][j - 1]);
  18. int ans = 0;
  19. for (int i = 1; i <= n; i++)
  20. ans = max(ans, dp[n][i]);
  21. return ans;
  22. }
  24. int main()
  25. {
  26. int n;
  27. cin >> n;
  28. vector<int> cost(n);
  29. for (int i = 0; i < n; i++)
  30. cin >> cost[i];
  31. cout << solve(cost) << endl;
  32. return 0;
  33. }
21. 若输入为 3 1 2 3，则输出为 3。（ ）
A. TRUE
B. FALSE
答案：A。本题 3 分。
输入 3 1 2 3 时，n=3，cur={1,2,3}。先令 dp[1][1]=1、dp[2][2]=2、dp[3][3]=3，再按 dp[i][j]=dp[i-1][j]+dp[i][j-1] 递推非对角位置。
最后一行为 dp[3][1]=1、dp[3][2]=3、dp[3][3]=3，取最大值得 3，所以输出为 3。
22. 计算 dp 数组的时间复杂度是 O(n^2)。（ ）
A. TRUE
B. FALSE
答案：A。本题 3 分。
dp 的主要计算在两层循环中完成：外层 i=1..n，内层 j=1..n。每个状态只进行一次常数时间的判断和转移。
因此计算 dp 数组的时间复杂度是 O(n^2)。
23. 若将第 28 行改为 vector<int> cost(n + 1)，输入仍为 3 1 2 3，则 solve 函数中的 n=3。（ ）
A. TRUE
B. FALSE
答案：B。本题 3 分。
solve 函数中的 n 来自 cur.size()，不是来自输入变量 n 本身。
如果把 vector<int> cost(n) 改成 vector<int> cost(n + 1)，那么传入 solve(cost) 的数组长度变为 4，所以函数内 n=4，题干说 n=3 是错误的。
24. 当输入的 cost 数组为 {4,0,0,5,6} 时，程序的输出为（ ）。
A. 23
B. 25
C. 24
D. 22
答案：B。本题 4 分。
对 cost={4,0,0,5,6}，对角线初值为 dp[1][1]=4、dp[2][2]=0、dp[3][3]=0、dp[4][4]=5、dp[5][5]=6。
按加法转移后，最后一行为 dp[5][1]=4、dp[5][2]=12、dp[5][3]=20、dp[5][4]=25、dp[5][5]=6，最大值是 25，所以程序输出 25。
25. 若将第 17 行改为 dp[i][j] = min(dp[i][j], dp[i - 1][j] - dp[i][j - 1]);，当输入的 cost 数组为 {4,0,0,5,6} 时，程序的输出为（ ）。
A. 20
B. 21
C. 22
D. 23
答案：A。本题 4 分。
把转移改成减法后，非对角位置按 dp[i-1][j]-dp[i][j-1] 更新。对 cost={4,0,0,5,6} 计算后，最后一行变为 4,-12,20,-15,6。
ans 取最后一行最大值，因此最大值为 20，程序输出 20。
26. （6 分）当输入的 cost 数组为 {4,0,0,5,6} 时，在 solve 函数中，dp[2][3] 的值为（ ）。
A. 1
B. 2
C. 3
D. 4
答案：D。本题 6 分。
dp[2][3] 不是对角线位置，所以会由转移式计算：dp[2][3]=min(inf, dp[1][3]+dp[2][2])。
先有 dp[2][2]=0；而 dp[1][3]=dp[0][3]+dp[1][2]=0+4=4。因此 dp[2][3]=4+0=4，选 D。
三、完善程序题（共5题，每题6分，共30分）
（一）交替组计数

给定一个整数数组 colors 和一个整数 k，其中 colors 表示由红蓝瓷砖组成的环，第 i 块瓷砖的颜色为 colors[i]（1 代表红色，0 代表蓝色）。环中连续 k 块瓷砖的颜色如果是交替颜色，则称为一个交替组。请找出交替组的个数。

  1. #include <iostream>
  2. #include <①>
  3. using namespace std;
  4. 04
  5. int main()
  6. {
  7. int n, k;
  8. cin >> n >> k;
  9. vector<int> colors(n);
  10. for (int i = 0; i < n; i++)
  11. cin >> colors[i];
  12. 12
  13. int ans = 0, cnt = ②;
  14. for (int i = 0; i < ③; i++)
  15. {
  16. if (i > 0 && ④)
  17. cnt = 0;
  18. cnt++;
  19. ans += (⑤ && cnt >= k);
  20. }
  21. 21
  22. cout << ans << endl;
  23. return 0;
  24. }
27. ① 处应填（ ）。
A. vector
B. set
C. string
D. map
答案：A。本题 6 分。
程序中第 9 行使用了 vector<int> colors(n);，说明需要使用 C++ 标准库中的 vector 容器。
vector 定义在头文件 <vector> 中，因此第 ① 处应填 vector。
set、string、map 分别对应集合、字符串和映射容器，都不能提供这里需要的 vector<int> 定义。
28. ② 处应填（ ）。
A. -1
B. 0
C. 1
D. 2
答案：B。本题 6 分。
cnt 用来记录当前已经连续交替的瓷砖数量。刚开始还没有处理任何瓷砖，所以连续长度应从 0 开始。
进入循环后，无论当前位置是否与前一个位置同色，程序都会执行一次 cnt++，表示把当前瓷砖计入当前连续段。
如果初值设为 1 或更大，会导致第一块瓷砖被多算；如果设为 -1，又会少算。因此第 ② 处应填 0。
29. ③ 处应填（ ）。
A. n
B. n - 1
C. 2 * n
D. 2 * (n - 1)
答案：C。本题 6 分。
题目中的瓷砖排成一个环，连续 k 块可能会跨过数组末尾回到数组开头。为了处理这种跨越边界的情况，程序使用 i % n 把下标映射回原数组。
如果只循环到 n，只能检查从每个位置开始但不跨边界的情况；如果多遍历一圈，到 2 * n，就能把环展开成两段相同序列，从而检查跨边界的交替组。
因此第 ③ 处应填 2 * n。
30. ④ 处应填（ ）。
A. colors[i] == colors[i - 1]
B. colors[i] != colors[i - 1]
C. colors[i % n] == colors[(i - 1) % n]
D. colors[i % n] != colors[(i - 1) % n]
答案：C。本题 6 分。
交替组要求相邻瓷砖颜色不同。也就是说，如果当前位置和前一个位置颜色相同，当前连续交替段就被打断，需要把 cnt 清零后重新计数。
由于循环会走到 2 * n，下标 i 可能超过原数组范围，所以访问颜色时必须写成 colors[i % n] 和 colors[(i - 1) % n]。
判断“交替被打断”的条件就是二者相等，因此第 ④ 处应填 colors[i % n] == colors[(i - 1) % n]。
31. ⑤ 处应填（ ）。
A. i > n
B. i >= n
C. i < n
D. i <= n
答案：B。本题 6 分。
cnt >= k 表示当前已经形成了至少 k 个连续交替瓷砖，可以贡献一个交替组。
但前 n 次遍历主要是在建立连续交替长度；真正统计以环中每个位置为终点的交替组时，需要等到展开后的第二圈，也就是 i >= n 后再计数。这样可以避免同一组在第一圈和第二圈中被重复统计。
因此第 ⑤ 处应填 i >= n，完整语句为 ans += (i >= n && cnt >= k);。