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

1. 下列关于计算机系统的说法，正确的是（）{{ select(1) }}

• CPU 只能保存程序，不能进行运算
• 操作系统负责管理硬件资源和提供运行环境
• 编译器属于计算机硬件的一部分
• 显示器是输入设备

2. 某存储器容量为 $4\text{ GiB}$，若 $1\text{ GiB}=1024\text{ MiB}$，$1\text{ MiB}=1024\text{ KiB}$，$1\text{ KiB}=1024\text{ Byte}$，则它可存储的 bit 数为（）{{ select(2) }}

• $2^{30}$
• $2^{32}$
• $2^{35}$
• $2^{38}$

3. 十进制整数 $2025$ 转换为十六进制表示为（）{{ select(3) }}

• $(7D9)_{16}$
• $(7E9)_{16}$
• $(8D9)_{16}$
• $(7F9)_{16}$

4. 在 C++ 中，若 unsigned char x = 250;，执行 x += 10; 后，x 的值通常按 $8$ 位无符号整数保存为（）{{ select(4) }}

• -6
• 4
• 260
• 250

5. 运行以下 C++ 代码片段，输出结果是（）{{ select(5) }}

   char a = 'c';
   char b = a - 'a' + 'A';
   cout << b << " " << int('9' - '0');
   

• C 9
• c 9
• C 57
• A 9

6. 设 int mask = 0;，依次执行以下语句后，mask 的十进制值为（）{{ select(6) }}

   mask |= (1 << 1);
   mask |= (1 << 4);
   mask ^= (1 << 1);
   

• 2
• 16
• 18
• 20

7. 下列 C++ 代码片段的输出是（）{{ select(7) }}

   int x = 3;
   {
       int x = 5;
       cout << x;
   }
   cout << x;
   

• 33
• 35
• 53
• 55

8. 已知以下定义，执行语句后输出为（）{{ select(8) }}

   struct Node {
       int val;
       Node *next;
   };
   Node a{1, nullptr}, b{2, nullptr}, c{3, nullptr};
   a.next = &c;
   b.next = a.next;
   a.next = &b;
   cout << a.next->next->val;
   

• 1
• 2
• 3
• 程序一定编译错误

9. 若函数定义如下，则调用 f(5) 的返回值为（）{{ select(9) }}

   int f(int n) {
       if (n <= 1) return 1;
       return f(n - 2) + n;
   }
   

• 6
• 8
• 9
• 10

10. 将中缀表达式 (a+b)*(c-d) 转换为后缀表达式，正确的是（）{{ select(10) }}

• ab+cd-*
• ab+cd*-
• ab+c*d-
• a+b*c-d

11. 一棵树有 $17$ 个结点。若这棵树是连通且无环的无向图，则它有（）条边{{ select(11) }}

• 16
• 17
• 18
• 34

12. 一个有向图有 $5$ 个顶点，其邻接矩阵第 $2$ 行为 0 1 0 1 1，则顶点 $2$ 的出度是（）{{ select(12) }}

• 1
• 2
• 3
• 4

13. 使用计数排序对取值范围为 $0..100$ 的 $n$ 个非负整数排序，其时间复杂度最接近（）{{ select(13) }}

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

14. 从 $1$ 到 $20$ 的整数中，能被 $2$ 或 $5$ 整除的数共有（）个{{ select(14) }}

• 10
• 11
• 12
• 14

15. 要计算 $a^{13}$，若使用快速幂思想并从低位到高位处理指数二进制位，$13$ 的二进制为 $(1101)_2$，需要乘入最终答案的幂包括（）{{ select(15) }}

• $a, a^2, a^4$
• $a, a^4, a^8$
• $a^2, a^4, a^8$
• $a, a^2, a^8$

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

(1)

01  #include <bits/stdc++.h>
02  using namespace std;
03
04  int gcd2(int a, int b) {
05      while (b != 0) {
06          int t = a % b;
07          a = b;
08          b = t;
09      }
10      return a;
11  }
12
13  int main() {
14      int n;
15      cin >> n;
16      vector<int> a(n);
17      for (int i = 0; i < n; i++) cin >> a[i];
18
19      int cur = a[0], same = 0, best = cur;
20      for (int i = 0; i < n; i++) {
21          cur = gcd2(cur + a[i], a[i]);
22          if (i > 0 && cur == a[i - 1]) same++;
23          if (cur > best) best = cur;
24      }
25      cout << cur << " " << same << " " << best << "\n";
26      return 0;
27  }

16. 函数 gcd2(a, b) 使用的是欧几里得算法。（）{{ select(16) }}

• 对
• 错

17. 若输入的所有数均为正整数，则第 21 行执行后 cur 一定为正整数。（）{{ select(17) }}

• 对
• 错

18. 变量 same 统计的是所有满足 cur == a[i] 的位置个数。（）{{ select(18) }}

• 对
• 错

19. 若输入为：

    6
    6 10 15 21 28 36
    

程序输出为（）{{ select(19) }}

• 1 0 6
• 1 1 6
• 6 0 6
• 1 0 36

20. 设输入共有 $n$ 个正整数，最大值为 $V$。该程序的时间复杂度最接近（）{{ select(20) }}

• $O(n)$
• $O(n\log V)$
• $O(nV)$
• $O(V\log n)$

(2)

保证输入的每个数都在 $1..K$ 范围内。

01  #include <bits/stdc++.h>
02  using namespace std;
03
04  int main() {
05      int n, K, target;
06      cin >> n >> K >> target;
07      vector<int> cnt(K + 1, 0);
08      for (int i = 0; i < n; i++) {
09          int x;
10          cin >> x;
11          cnt[x]++;
12      }
13
14      vector<int> pref(K + 1, 0);
15      for (int i = 1; i <= K; i++)
16          pref[i] = pref[i - 1] + cnt[i];
17
18      int distinct = 0, median = -1;
19      int need = (n + 1) / 2;
20      for (int i = 1; i <= K; i++) {
21          if (cnt[i] > 0) distinct++;
22          if (median == -1 && pref[i] >= need) median = i;
23      }
24
25      long long pairs = 0;
26      for (int x = 1; x <= K; x++) {
27          int y = target - x;
28          if (y < x || y > K) continue;
29          if (x == y) pairs += 1LL * cnt[x] * (cnt[x] - 1) / 2;
30          else pairs += 1LL * cnt[x] * cnt[y];
31      }
32
33      cout << distinct << " " << median << " " << pairs << "\n";
34      return 0;
35  }

21. 数组 pref[i] 表示输入中小于等于 i 的数的个数。（）{{ select(21) }}

• 对
• 错

22. 当 $n$ 为偶数时，变量 median 表示排序后第 $\frac n2+1$ 个数。（）{{ select(22) }}

• 对
• 错

23. 第 28 行的条件 y < x 是为了避免把同一对数重复统计。（）{{ select(23) }}

• 对
• 错

24. 若输入为：

    9 9 10
    3 1 4 1 5 9 2 6 5
    

程序输出为（）{{ select(24) }}

• 6 4 4
• 7 4 4
• 7 5 4
• 7 4 5

25. 使用第 24 题的输入，cnt[5] 的值为（）{{ select(25) }}

• 0
• 1
• 2
• 3

26. 设输入规模为 $n$，数值范围为 $1..K$，该程序的时间复杂度和额外空间复杂度最接近（）{{ select(26) }}

• $O(n\log n)$，$O(n)$
• $O(n+K)$，$O(K)$
• $O(nK)$，$O(K)$
• $O(K^2)$，$O(1)$

(3)

输入为一棵二叉树的先序序列，其中 # 表示空树，其他字符表示结点。保证输入合法且长度不超过 $1000$。

01  #include <bits/stdc++.h>
02  using namespace std;
03
04  string s, post;
05  int pos = 0, nodes = 0, leaves = 0;
06
07  int build() {
08      char ch = s[pos++];
09      if (ch == '#') return 0;
10      nodes++;
11      int lh = build();
12      int rh = build();
13      if (lh == 0 && rh == 0) leaves++;
14      post.push_back(ch);
15      return max(lh, rh) + 1;
16  }
17
18  int main() {
19      cin >> s;
20      int height = build();
21      cout << nodes << " " << leaves << " " << height << "\n";
22      cout << post << "\n";
23      return 0;
24  }

27. 函数 build 按先序序列递归读取并处理二叉树。（）{{ select(27) }}

• 对
• 错

28. 对非空结点，程序会先处理左子树和右子树，再把当前结点加入 post。（）{{ select(28) }}

• 对
• 错

29. 变量 leaves 统计的是只有一个孩子的结点个数。（）{{ select(29) }}

• 对
• 错

30. 若输入为：

    ABD##E##C#F##
    

程序第一行输出为（）{{ select(30) }}

• 6 2 3
• 6 3 3
• 7 3 3
• 6 3 4

31. 使用第 30 题的输入，程序第二行输出为（）{{ select(31) }}

• DBEFCA
• DEBFCA
• DBEACF
• DEBCAF

32. 设输入字符串长度为 $m$，该程序的时间复杂度为（）{{ select(32) }}

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

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

(1)（矩形覆盖统计）

给定一个 $n \times m$ 的网格和若干个矩形。每个矩形用 x1 y1 x2 y2 表示，覆盖所有满足 x1 <= x <= x2 且 y1 <= y <= y2 的格子。请统计至少被覆盖一次的格子数、恰好被覆盖一次的格子数，以及最大覆盖次数。

01  #include <bits/stdc++.h>
02  using namespace std;
03
04  int main() {
05      int n, m, q;
06      cin >> n >> m >> q;
07      vector<vector<int>> d(n + 2, vector<int>(m + 2, 0));
08      for (int i = 0; i < q; i++) {
09          int x1, y1, x2, y2;
10          cin >> x1 >> y1 >> x2 >> y2;
11          d[x1][y1] += 1;
12          d[①][y1] -= 1;
13          d[x1][②] -= 1;
14          d[③][④] += 1;
15      }
16
17      int covered = 0, once = 0, mx = 0;
18      for (int i = 1; i <= n; i++) {
19          for (int j = 1; j <= m; j++) {
20              d[i][j] += ⑤;
21              if (d[i][j] > 0) covered++;
22              if (d[i][j] == 1) once++;
23              mx = max(mx, d[i][j]);
24          }
25      }
26      cout << covered << " " << once << " " << mx << "\n";
27      return 0;
28  }

33. ① 处应填（）{{ select(33) }}

• x2
• x2 + 1
• x1 + 1
• n + 1

34. ② 处应填（）{{ select(34) }}

• y2
• y1 + 1
• y2 + 1
• m + 1

35. ③ 处应填（）{{ select(35) }}

• x2 + 1
• x2
• x1
• n

36. ④ 处应填（）{{ select(36) }}

• y2 + 1
• y2
• y1
• m

37. ⑤ 处应填（）{{ select(37) }}

• d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1]
• d[i - 1][j] + d[i][j - 1] + d[i - 1][j - 1]
• d[i + 1][j] + d[i][j + 1] - d[i + 1][j + 1]
• d[i - 1][j - 1]

(2)（最长公共子序列长度）

给定两个字符串 a 和 b，求它们的最长公共子序列长度。子序列可以不连续，但相对顺序不能改变。

01  #include <bits/stdc++.h>
02  using namespace std;
03
04  int main() {
05      string a, b;
06      cin >> a >> b;
07      int n = (int)a.size(), m = (int)b.size();
08      vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
09      for (int i = 1; i <= n; i++) {
10          for (int j = 1; j <= m; j++) {
11              if (⑥)
12                  dp[i][j] = ⑦;
13              else
14                  dp[i][j] = ⑧;
15          }
16      }
17      cout << ⑨ << "\n";
18      return 0;
19  }

38. ⑥ 处应填（）{{ select(38) }}

• a[i - 1] == b[j - 1]
• a[i] == b[j]
• a[i - 1] != b[j - 1]
• i == j

39. ⑦ 处应填（）{{ select(39) }}

• dp[i - 1][j - 1] + 1
• dp[i - 1][j] + 1
• dp[i][j - 1] + 1
• dp[i][j] + 1

40. ⑧ 处应填（）{{ select(40) }}

• max(dp[i - 1][j], dp[i][j - 1])
• min(dp[i - 1][j], dp[i][j - 1])
• dp[i - 1][j - 1]
• 0

41. ⑨ 处应填（）{{ select(41) }}

• dp[n][m]
• dp[n - 1][m - 1]
• dp[0][0]
• max(n, m)

42. 若输入为：

    ABCBDAB
    BDCABA
    

补全正确后，程序输出为（）{{ select(42) }}

• 3
• 4
• 5
• 7