一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）

1. 在标准ASCII码表中，已知英文字母c的ASCII码十进制表示是99，那么英文字母x的ASCII码十六进制表示是（）

{{ select(1) }}

• 77
• 78
• 79
• 7A

2. 以下关于CSP与GESP的描述正确的是（）

{{ select(2) }}

• CSP-J/CSP-S属于非专业级别软件能力认证，只有中小学生才能参加
• CSP-J/CSP-S是中国通信学会举办的程序设计竞赛
• GESP是中国电子学会举办的程序设计竞赛
• GESP C++七级成绩80分及以上或者八级成绩60分及以上，可以申请免CSP-J初赛

3. 以下可以用作C++程序中的变量名的是（）

{{ select(3) }}

• _x1
• new
• class
• public

4. 以下不属于桌面或者手机操作系统的是（）

{{ select(4) }}

• Linux
• Android
• MATLAB
• Windows 11

5. C++中使用输入和输出函数cin和cout会用到（）头文件

{{ select(5) }}

• iostream
• cmath
• cstdio
• algorithm

6. 寻找最短路径的广度优先搜索算法经常用到的数据结构是（）

{{ select(6) }}

• 栈
• 链表
• 向量
• 队列

7. 以下哪个域名后缀不属于中华人民共和国管辖？（）

{{ select(7) }}

• cn
• uk
• hk
• mo

8. 下列排序算法中，平均情况下（）算法的时间复杂度最小

{{ select(8) }}

• 插入排序
• 选择排序
• 归并排序
• 冒泡排序

9. 关于计算机网络，下面的说法中正确的是（）

{{ select(9) }}

• TCP是网络层协议
• 计算机病毒只能通过U盘等介质传播，不能通过计算机网络传播
• 计算机网络可以实现资源共享
• 公司内部的几台计算机组成的网络规模太小，不能称为计算机网络

10. 序列（7，5，1，12，3，6，9，4）的逆序对有（）个

{{ select(10) }}

• 15
• 12
• 13
• 14

11. 下列属于图像文件格式的是（）

{{ select(11) }}

• MPEG
• DOCX
• JPEG
• WMV

12. 不管P、Q如何取值，以下逻辑表达式中取值恒为假的是（）

{{ select(12) }}

• $(\neg Q \land P) \lor (Q \land \neg P)$
• $((\neg P \lor Q) \lor (P \lor \neg Q)) \land P \land \neg Q$
• $\neg P \land (\neg Q \lor P) \lor (Q \lor \neg P) \land P$
• $((\neg P \lor Q) \lor (Q \lor \neg P)) \land Q \land \neg P$

13. 树的根结点的高度为1，某完全二叉树有2025个结点，其高度是（）

{{ select(13) }}

• 10
• 11
• 12
• 13

14. 现有9个苹果，要放入5个不同的盘子，允许有的盘子中放0个苹果，则不同的放法共有（）种

{{ select(14) }}

• 720
• 715
• 126
• 252

15. G是一个非连通无向图（没有重边和自环），共有36条边，则该图至少有（）个顶点

{{ select(15) }}

• 6
• 9
• 10
• 8

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特殊说明外，判断题每题1.5分，选择题每题3分，共计40分）

（1）

01 #include <bits/stdc++.h>
02 using namespace std;
03
04 using i64 = long long;
05
06 int popcount(i64 x)
07 {
08     int res = 0;
09     while (x)
10     {
11         if (x & 1 == 1)
12             res++;
13         x >>= 1;
14     }
15     return res;
16 }
17
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 }
25
26 int sum(i64 l, i64 r)
27 {
28     return calc(r) - calc(l);
29 }
30
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。（）

{{ select(16) }}

• 正确
• 错误

17. 若将第11行中的&符号改为^符号，程序输出结果一定不会改变。（）

{{ select(17) }}

• 正确
• 错误

18. 若将头文件#include <bits/stdc++.h>改成#include <stdio.h>，程序仍能正常运行。（）

{{ select(18) }}

• 正确
• 错误

选择题

19. 若输入为1 12，则输出是什么？（）

{{ select(19) }}

• 1 21
• 1 20
• 1 22
• 2 22

20. 程序中的sum函数实现了什么功能？（）

{{ select(20) }}

• 计算了$[l, r]$区间内的每个数二进制位上1的个数之和
• 计算了$[1, r]$区间内的每个数二进制位上0的个数之和
• 计算了$(l, r]$区间内的每个数二进制位上1的个数之和
• 计算了$(l, r]$区间内的每个数二进制位上0的个数之和

（2）

01 #include <bits/stdc++.h>
02 using namespace std;
03
04 const int inf = 0x3f3f3f3f;
05
06 int solve(vector<int> cur)
07 {
08     int n = cur.size();
09     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 }
23
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。（）

{{ select(21) }}

• 正确
• 错误

22. 计算dp数组的时间复杂度为$O(n^2)$。（）

{{ select(22) }}

• 正确
• 错误

23. （2分）若将第28行改为vector<int> cost(n + 1)，则当输入3 1 2 3时，solve函数中的$n = 3$。（）

{{ select(23) }}

• 正确
• 错误

选择题

24. 当输入的cost数组为{4，0，0，5，6}时，程序的输出为（）

{{ select(24) }}

• 23
• 25
• 24
• 22

25. 若将第17行改为dp[i][j] = min(dp[i][j], dp[i - 1][j] - dp[i][j - 1]);，则当输入的cost数组为{4，0，0，5，6}时，程序的输出为（）

{{ select(25) }}

• 20
• 21
• 22
• 23

26. （4分）当输入的cost数组为{4，0，0，5，6}时，在solve函数中，dp[2][3]的值为（）

{{ select(26) }}

• 1
• 2
• 3
• 4

（3）

01 #include <bits/stdc++.h>
02 using namespace std;
03
04 int func(int a, int b)
05 {
06     if (a == 0)
07         return b;
08     if (b == 0)
09         return a;
10     return a + func(b, a % b);
11 }
12
13 int main()
14 {
15     int x, y;
16     cin >> x >> y;
17     cout << func(x, y) << endl;
18     return 0;
19 }

假设输入均为非负整数，完成下面的问题。

判断题

27. 当输入为2 3时，程序的输出为5。（）

{{ select(27) }}

• 正确
• 错误

28. 若输入只有一个为0，则程序的输出为输入的另一个数字。（）

{{ select(28) }}

• 正确
• 错误

29. 当输入为6 8时，func函数将会被进入4次。（）

{{ select(29) }}

• 正确
• 错误

选择题

30. 当输入为6 8时，程序的输出为（）

{{ select(30) }}

• 20
• 21
• 22
• 23

31. 当输入为3 5时，func函数的调用顺序是（）

{{ select(31) }}

• func(3,5)→func(5,3)→func(3,2)→func(2,1)→func(1,0)
• func(3,5)→func(5,3)→func(3,2)→func(2,1)→func(1,1)→func(1,0)
• func(3,5)→func(5,2)→func(2,1)→func(1,1)→func(1,0)
• func(3,5)→func(5,2)→func(2,1)→func(1,0)

32. （4分）若将第10行的代码改为return a + func(b, a - b)，则当输入为3 5时，得到的输出为（）

{{ select(32) }}

• 14
• 8
• 6
• 产生未定义行为，结果未知

三、完善程序（单选题，每小题3分，共计30分）

（1）题目描述： 给定一个整数数组colors和一个整数k，其中colors表示一个由红色瓷砖和蓝色瓷砖组成的环，第i块瓷砖的颜色为colors[i]（1代表红色，0代表蓝色）。环中连续k块瓷砖的颜色如果是交替颜色（除了第一块和最后一块瓷砖以外，中间瓷砖的颜色与它左边瓷砖和右边瓷砖的颜色都不同），那么它被称为一个交替组。现在，请你找出交替组的个数。

01 #include <iostream>
02 #include <①>
03
04 using namespace std;
05
06 int main()
07 {
08     int n, k;
09     cin >> n >> k;
10     vector<int> colors(n);
11     for (int i = 0; i < n; i++)
12         cin >> colors[i];
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     cout << ans << endl;
22     return 0;
23 }

33. ①处应填（）

{{ select(33) }}

• vector
• set
• string
• map

34. ②处应填（）

{{ select(34) }}

• -1
• 0
• 1
• 2

35. ③处应填（）

{{ select(35) }}

• n
• n - 1
• 2 * n
• 2 * (n - 1)

36. ④处应填（）

{{ select(36) }}

• colors[i] == colors[i - 1]
• colors[i] != colors[i - 1]
• colors[i % n] == colors[(i - 1) % n]
• colors[i % n] != colors[(i - 1) % n]

37. ⑤处应填（）

{{ select(37) }}

• i > n
• i >= n
• i < n
• i <= n

（2）题目描述： 在国际象棋中，马的一次移动定义为：垂直移动两个方格后再水平移动一个方格，或者水平移动两个方格后再垂直移动一个方格（两者都形成一个L的形状）。 现在，我们有一个马和一个电话垫（如下所示），马只能站在数字单元格上。你可以将马放置在任何数字单元格上，然后你应该执行$n - 1$次移动来获得长度为n的号码。马所有的移动应该是符合规则的有效的移动。马在一次移动的过程中可以经过符号单元格，但必须保证这次移动结束后马站在数字单元格上。 给定一个整数n，请你计算可以得到多少个长度为n的数字串。由于答案可能很大，请你输出答案对$10^9 + 7$取模后的结果。

01 #include <iostream>
02 #include <vector>
03
04 using namespace std;
05
06 const int mod = 1e9 + 7;
07 vector<vector<int>> pos = { {}, {6, 8}, {7, 9}, {4, 8}, {3, 9, 0}, ①, {0, 1, 7}, {2, 6}, {1, 3}, {2, 4} };
08
09 int main()
10 {
11     int n;
12     cin >> n;
13     vector<vector<int>> dp(10, vector<int>(n + 1, 0));
14     for (int i = 0; i <10; i++)
15         ② = 1;
16     for (int j = 2; j <= n; j++)
17     {
18         for (int i = 0; i < 10; i++)
19         {
20             for (int k = 0; k < pos[i].size(); k++)
21             {
22                 dp[i][j] += dp[③][j - 1];
23                 ④;
24             }
25         }
26     }
27     int ans = 0;
28     for (int i = 0; i < 10; i++)
29     {
30         ⑤;
31         ans %= mod;
32     }
33     cout << ans << endl;
34     return 0;
35 }

38. ①处应填（）

{{ select(38) }}

• {1, 3, 7, 9}
• {*, #}
• {2, 8, 0}
• {}

39. ②处应填（）

{{ select(39) }}

• dp[i][1]
• dp[1][i]
• dp[i][0]
• dp[0][i]

40. ③处应填（）

{{ select(40) }}

• k
• pos[k][i]
• pos[i][k]
• pos[i - 1][k]

41. ④处应填（）

{{ select(41) }}

• dp[i][k] %= mod
• dp[j][i] -= mod
• dp[i][j] %= mod
• dp[i][j] -= mod

42. ⑤处应填（）

{{ select(42) }}

• ans += dp[i][n]
• ans += dp[i][n - 1]
• ans += dp[n][i]
• ans += dp[n - 1][i]