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

1. 在C++程序中，假设一个字符占用的内存空间是1字节，则下列程序中，s占用的内存空间是（）字节

char s[] = "hello oiers";
size_t cnt = strlen(s);
cout << cnt << endl;

{{ select(1) }}

• 10
• 11
• 13
• 12

2. 十六进制数B2025转换成八进制数是（）

{{ select(2) }}

• 2620045
• 2004526
• 729125
• 2420045

3. 以下能正确定义二维数组的是（）

{{ select(3) }}

• int a[3][];
• int a[][];
• int a[][4];
• int a[][2] = {{1,2},{1,2},{3,4}};

4. 二进制[1000001]原码和[100001]补码表示的十进制数值分别是（）

{{ select(4) }}

• -125，-3
• -3，-125
• -3，-3
• -125，-125

5. 在C++中，下列定义方式中，变量的值不能被修改的是（）

{{ select(5) }}

• unsigned int a = 5;
• static double d = 3.14;
• string s = "ccf csp-j";
• const char c = 'k';

6. 走迷宫的深度优先搜索算法经常用到的数据结构是（）

{{ select(6) }}

• 向量
• 栈
• 链表
• 队列

7. 关于递归，以下叙述中正确的是（）

{{ select(7) }}

• 动态规划算法都是用递归实现的
• 递归比递推更高级，占用的内存空间更少
• A函数调用B函数，B函数再调用A函数不属于递归的一种
• 递归是通过调用自身来求解问题的编程技术

8. 以下不属于计算机输入设备的是（）

{{ select(8) }}

• 扫描仪
• 显示器
• 鼠标
• 麦克风

9. 关于排序算法，下面的说法中正确的是（）

{{ select(9) }}

• 快速排序算法在最坏情况下的时间复杂度是$O(n \log n)$
• 插入排序算法的时间复杂度是$O(n \log n)$
• 归并排序算法的时间复杂度是$O(n \log n)$
• 冒泡排序算法是不稳定的

10. 下列关于C++语言的叙述中不正确的是（）

{{ select(10) }}

• 变量没有定义也能使用
• 变量名不能以数字开头，且中间不能有空格
• 变量名不能和C++语言中的关键字重复
• 变量在定义的时候可以不用赋值

11. 如果x和y均为int类型的变量，下列表达式中能正确判断“x等于y”的是（）

{{ select(11) }}

• $1 == (x / y)$
• $x == (x \& y)$
• $0 == (x ^ y)$
• $y == (x | y)$

12. 在如今的智能互联网时代，AI如火如荼，除了计算机领域以外，通信领域的技术发展也做出了很大贡献。被称为“通信之父”的是（）

{{ select(12) }}

• 克劳德·香农
• 莱昂哈德·欧拉
• 约翰·冯·诺依曼
• 戈登·摩尔

13. 一棵满二叉树的深度为3（根结点的深度为1），按照后序遍历的顺序从1开始编号，根结点的右子结点的编号是（）

{{ select(13) }}

• 3
• 6
• 7
• 5

14. 三头奶牛Bessie、Dis和Nancy去参加考试，考场是连续的6间牛棚，用栅栏隔开。为了防止作弊，任意两头奶牛都不能在相邻的牛棚，则考场安排共有（）种不同的方法

{{ select(14) }}

• 18
• 24
• 30
• 48

15. 为强化安全意识，某学校准备在某消防月连续10天内随机抽取3天进行消防紧急疏散演习，抽取的3天为连续3天的概率为（）

{{ select(15) }}

• 3/10
• 3/20
• 1/15
• 1/18

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

（1）

01 #include <iostream>
02 #include <vector>
03 #include <algorithm>
04 using namespace std;
05
06 using i64 = long long;
07
08 int clz(i64 x) {
09     for (int i = 0; i != 64; i++)
10         if ((x >> (63 - i)) & 1)
11             return i;
12     return 64;
13 }
14
15 bool cmp(i64 x, i64 y) {
16     if (clz(x) == clz(y))
17         return x < y;
18     return clz(x) < clz(y);
19 }
20
21 int main() {
22     int n;
23     cin >> n;
24     vector<int> a(n);
25     for (int i = 0; i < n; i++)
26         cin >> a[i];
27     sort(a.begin(), a.end(), cmp);
28     for (int i = 0; i < n; i++)
29         cout << a[i] << "\n"[i == n - 1];
30     return 0;
31 }

判断题

16. 若程序输入5 0 4 2 1 3，则程序输出4 2 3 1 0。（）

{{ select(16) }}

• 正确
• 错误

17. 若将第18行中的<换为>，则当程序输入5 0 4 2 1 3时，程序输出为4 3 2 1 0。（）

{{ select(17) }}

• 正确
• 错误

18. 当调用cmp(3, 3)时，函数的返回值为false。（）

{{ select(18) }}

• 正确
• 错误

选择题

19. 若输入5 4 2 1 3 1，则输出是什么？（）

{{ select(19) }}

• 3 4 2 1 1
• 3 2 4 1 1
• 4 3 2 1 1
• 4 2 3 1 1

20. 这个程序实现了什么功能？（）

{{ select(20) }}

• 将输入的数组按照二进制位上从左到右第一个1前0的个数由多到少进行排序
• 将输入的数组按照二进制位上从左到右第一个1前0的个数由少到多进行排序
• 将输入的数组按照二进制位上从左到右第一个1前0的个数由多到少进行排序，当0的个数相同时，按照原数字由小到大进行排序
• 将输入的数组按照二进制位上从左到右第一个1前0的个数由少到多进行排序，当0的个数相同时，按照原数字由小到大进行排序

（2）

01 #include <iostream>
02 #include <vector>
03 #include <algorithm>
04 #include <set>
05 #include <string>
06 using namespace std;
07
08 const int inf = 0x3f3f3f3f;
09
10 int calc(vector<vector<int>> grid) {
11     int m = grid.size(), n = grid[0].size();
12     vector<vector<int>> dp(m + 1, vector<int>(n + 1, inf));
13     dp[0][0] = grid[0][0];
14     for (int i = 0; i < m; i++)
15         for (int j = 0; j < n; j++) {
16             if (i > 0)
17                 dp[i][j] = min(dp[i][j], dp[i - 1][j] + grid[i][j]);
18             if (j > 0)
19                 dp[i][j] = min(dp[i][j], dp[i][j - 1] + grid[i][j]);
20         }
21     return dp[m - 1][n - 1];
22 }
23
24 int main() {
25     int m, n;
26     cin >> m >> n;
27     vector<vector<int>> a(m, vector<int>(n));
28     for (int i = 0; i < m; i++)
29         for (int j = 0; j < n; j++)
30             cin >> a[i][j];
31     cout << calc(a) << endl;
32     return 0;
33 }

假设$m \leq 100$，$n \leq 10000$，完成下面的问题。

判断题

21. 若输入2 3 1 2 3 4 5 6，则输出为10。（）

{{ select(21) }}

• 正确
• 错误

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

{{ select(22) }}

• 正确
• 错误

23. （2分）在calc函数中，访问dp[m][n]不会发生越界错误。（）

{{ select(23) }}

• 正确
• 错误

选择题

24. 当输入的a数组为{{1,3,1}, {1,5,1}, {4,2,1}}时，程序输出为（）

{{ select(24) }}

• 4
• 7
• 6
• 5

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

{{ select(25) }}

• -3
• -2
• -1
• 0

26. （4分）若将第10行中的&符号去除，可能出现什么情况？（）

{{ select(26) }}

• dp数组计算错误
• calc函数中的grid数组和a数组不一致
• 无影响
• 发生编译错误

（3）

01 #include <iostream>
02 #include <vector>
03 #include <algorithm>
04 #include <set>
05 #include <string>
06 using namespace std;
07
08 const int N = 1010;
09
10 vector<int> E[N];
11 int V[N];
12 int n;
13
14 void add(int x, int y) {
15     E[x].push_back(y);
16 }
17
18 int gcd(int x, int y) {
19     return !y ? x : gcd(y, x % y);
20 }
21
22 void calc(int cur, int fa) {
23     V[cur] = (gcd(cur, fa) != 1);
24     for (auto v : E[cur]) {
25         if (v == fa)
26             continue;
27         calc(v, cur);
28         V[cur] += V[v];
29     }
30     return;
31 }
32
33 int main() {
34     cin >> n;
35     for (int i = 1; i < n; i++) {
36         int x, y;
37         cin >> x >> y;
38         add(x, y);
39         add(y, x);
40     }
41     calc(1, 1);
42     for (int i = 1; i <= n; i++)
43         cout << V[i] << "\n"[i == n];
44     return 0;
45 }

已知$gcd(x, y)$的时间复杂度为$O(\log(\min(x, y)))$，输入中$1 \leq x$，$y \leq n$且$x \neq y$，回答下面的问题。

判断题

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

{{ select(27) }}

• 正确
• 错误

28. gcd函数用来计算两个数x和y的最大公约数。（）

{{ select(28) }}

• 正确
• 错误

29. 当输入为4 1 2 1 3 2 4时，calc函数的递归调用次数为4次。（）

{{ select(29) }}

• 正确
• 错误

选择题

30. 当输入为4 1 2 1 3 2 4时，程序的输出为（）

{{ select(30) }}

• 0 0 0 0
• 1 1 0 1
• 0 0 1 0
• 1 1 1 1

31. （4分）calc函数的时间复杂度为（）

{{ select(31) }}

• $O(n \log n)$
• $O(n^2)$
• $O(n)$
• $O(\log n)$

32. 若将第28行中的代码改为V[cur] *= V[v]，则当输入为4 1 2 1 3 2 4时，得到的输出为（）

{{ select(32) }}

• 1 1 1 0
• 1 1 0 1
• 0 0 1 0
• 0 0 0 1

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

（1）题目描述： 给定一个长为n（1 < n ≤ 2×10⁵）的数组a（-10⁹ ≤ a[i] ≤ 10⁹），执行如下操作，直到a中只剩下1个数： 删除a[i]。如果a[i]左右两边都有数字，则把a[i-1]和a[i+1]合并成一个数。 输出最后剩下的那个数的最大值。

01 #include <bits/stdc++.h>
02 using namespace std;
03
04 using i64 = long long;
05
06 void solve() {
07     int n, flag = 0, mx = ①;
08     cin >> n;
09     vector<int> a(n + 1);
10     for (int i = 1; i <= n; i++) {
11         cin >> a[i];
12         if (a[i] < 0)
13             flag++;
14         mx = max(mx, a[i]);
15     }
16     if (②) {
17         cout << mx << endl;
18         return;
19     }
20     ③ sum1 = 0, sum2 = 0;
21     for (int i = 1; i <= n; i += 2)
22         sum1 += max(a[i], 0);
23     for (int i = 2; i <= n; i += 2)
24         ④;
25     cout << ⑤ << endl;
26     return;
27 }
28
29 int main() {
30     int t = 1;
31    ```cpp
    cin >> t;
32     while (t--)
33         solve();
34     return 0;
35 }

33. ①处应填（）

{{ select(33) }}

• 0
• 1E9
• -1E8
• -2E9

34. ②处应填（）

{{ select(34) }}

• flag == n
• flag == 0
• flag != 0
• flag != n

35. ③处应填（）

{{ select(35) }}

• int
• i64
• i32
• unsigned int

36. ④处应填（）

{{ select(36) }}

• sum2 += max(a[i], 0)
• sum2 += min(a[i], 0)
• sum2 -= min(a[i], 0)
• sum2 -= max(a[i], 0)

37. ⑤处应填（）

{{ select(37) }}

• min(sum1, sum2)
• max(sum1, sum2)
• sum1 + sum2
• sum1 - sum2

（2）题目描述： 给定一个字符串t和一个字符串列表s作为字典。保证s中的字符串互不相同，且t和s[]中均只包含小写英文字母。 如果可以利用字典中出现的一个或多个单词拼接出t，则返回true。注意：不要求字典中出现的单词全部使用，并且字典中的单词可以重复使用。 数据限制：1 ≤ t.Length() ≤ 300，1 ≤ s.size() ≤ 1000，1 ≤ s[i].length() ≤ 20。

01 #include <iostream>
02 #include <vector>
03 #include <algorithm>
04 #include <set>
05 #include <string>
06 using namespace std;
07
08 const int N = 1010;
09
10 int n, mx, m;
11 vector<string> s;
12 vector<int> mem;
13 string t;
14 set<string> st;
15
16 int dfs(int i) {
17     if (i == 0)
18         return 1;
19     if (①)
20         return mem[i];
21     for (int j = i - 1; j >= max(i - mx, 0); j--)
22         if (st.find(②) != st.end() && dfs(j))
23             return mem[i] = 1;
24     return ③;
25 }
26
27 int main() {
28     cin >> n;
29     s.resize(n);
30     for (int i = 0; i < n; i++) {
31         cin >> s[i];
32         mx = max(mx, ④);
33     }
34     st = set<string>(s.begin(), s.end());
35     cin >> t;
36     m = (int)t.length();
37     mem.resize(m + 1, -1);
38     if (⑤)
39         cout << "Yes\n";
40     else
41         cout << "No\n";
42     return 0;
43 }

38. ①处应填（）

{{ select(38) }}

• mem[i] != -1
• mem[i] == -1
• mem[i] == 0
• mem[i] != 0

39. ②处应填（）

{{ select(39) }}

• t.substr(i, j - i)
• t.substr(j, i - j)
• t.substr(j)
• t.substr(i)

40. ③处应填（）

{{ select(40) }}

• 1
• mem[i] = 1
• 0
• mem[i] = 0

41. ④处应填（）

{{ select(41) }}

• s[i].length()
• (int)s[i].Length()
• s[i].length() - 1
• (int)s[i].Length() - 1

42. ⑤处应填（）

{{ select(42) }}

• !dfs(m)
• !dfs(n)
• dfs(m)
• dfs(n)