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

1. 下列软件中，主要负责把 C++ 源程序翻译成可执行程序的是（）{{ select(1) }}

• 浏览器
• 编译器
• 操作系统
• 文本编辑器

2. 某传感器需要连续缓存若干帧分辨率为 $640 \times 480$ 的灰度图像。虽然每个像素实际只需要 $12$ bit，但为了便于访问，程序按每个像素 $2$ Byte 存储。若缓存区大小为 $6$ MiB，最多能完整保存（）帧图像{{ select(2) }}

• 8
• 10
• 12
• 20

3. 某调试器中显示两个整数分别为 $(3C)_{16}$ 和 $(101011)_2$。若计算前者减去后者，结果用八进制表示为（）{{ select(3) }}

• $(17)_8$
• $(21)_8$
• $(25)_8$
• $(31)_8$

4. 若一个 8 位有符号整数采用补码表示，二进制 11110110 表示的十进制数是（）{{ select(4) }}

• 246
• -10
• -9
• 118

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

   char c = 'C';
   c += '7' - '4';
   cout << c << ('9' - '6');
   

• F3
• E3
• F51
• C3

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

   int x = 52;
   int y = x & -x;
   x += y;
   cout << y << " " << ((x >> 2) & 7);
   

• 4 5
• 4 6
• 8 6
• 4 14

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

   void change(int a, int &b, int *c) {
       a += 5;
       b += 5;
       *c += 5;
       c = &a;
   }
   int x = 1, y = 2, z = 3;
   change(x, y, &z);
   cout << x << " " << y << " " << z;
   

• 6 7 8
• 1 7 8
• 1 2 8
• 1 7 3

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

   int a[5] = {1, 2, 3, 4, 5};
   for (int i = 1; i < 5; i++)
       a[i] += a[i - 1];
   cout << a[3] << " " << a[4];
   

• 7 9
• 9 14
• 10 15
• 6 15

9. 设 $A,B,C$ 都是布尔变量，表达式 !(A && !B) && (A || C) 与下列哪个表达式等价？（）{{ select(9) }}

• A && (B || C)
• (!A && B) || (A && C)
• (A && B) || (!A && C)
• B && C

10. 将 1, 2, 3, 4, 5, 6 依次入栈，中途可以任意出栈。下列哪个出栈序列不可能得到？（）{{ select(10) }}

• 2 1 4 3 6 5
• 3 2 1 6 5 4
• 4 5 3 2 6 1
• 3 1 2 6 5

11. 一个长度为 7 的哈希表，下标为 0..6，哈希函数为 h(k)=k mod 7，采用线性探测法解决冲突。依次插入 10, 3, 17, 24 后，查找 24 需要探测（）个位置{{ select(11) }}

• 1
• 2
• 3
• 4

12. 一棵完全二叉树按层序从 $1$ 开始编号，共有 $83$ 个结点。关于编号为 $42$ 的结点，下列说法正确的是（）{{ select(12) }}

• 父结点编号为 $21$，兄弟结点编号为 $43$，它本身是叶子
• 父结点编号为 $20$，兄弟结点编号为 $43$，它本身是叶子
• 父结点编号为 $21$，左孩子编号为 $84$
• 父结点编号为 $41$，兄弟结点编号为 $43$

13. 已知某二叉树的中序遍历为 B F H M R T Z，后序遍历为 B H F R Z T M，则它的先序遍历为（）{{ select(13) }}

• M F B H T R Z
• M F H B T Z R
• B H F R Z T M
• M T R Z F B H

14. 在网格中从 $(0,0)$ 走到 $(5,4)$，每步只能向右或向上走一格。若路径必须恰好经过 $(2,1)$ 和 $(4,3)$ 这两个点中的一个，则这样的路径共有（）条{{ select(14) }}

• 34
• 58
• 94
• 130

15. 使用栈计算后缀表达式 8 3 1 - / 2 5 + *，结果为（）{{ select(15) }}

• 14
• 21
• 28
• 56

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

(1)

01  #include <bits/stdc++.h>
02  using namespace std;
03
04  pair<int, int> calc(int x) {
05      int cnt = 0, sum = 0;
06      for (int d = 1; 1LL * d * d <= x; d++) {
07          if (x % d == 0) {
08              cnt++;
09              sum += d;
10              if (d * d != x) {
11                  cnt++;
12                  sum += x / d;
13              }
14          }
15      }
16      return {cnt, sum};
17  }
18
19  int main() {
20      int n;
21      cin >> n;
22      vector<int> a(n + 1);
23      int oddCnt = 0, bestPos = 1, bestSum = -1;
24      for (int i = 1; i <= n; i++) {
25          cin >> a[i];
26          auto res = calc(a[i]);
27          if (res.first % 2 == 1) oddCnt++;
28          if (res.second > bestSum) {
29              bestSum = res.second;
30              bestPos = i;
31          }
32      }
33      cout << oddCnt << " " << bestPos << " " << bestSum << "\n";
34      return 0;
35  }

16. 函数 calc 在遇到一对不同约数 d 和 x/d 时，会把它们都计入 cnt 和 sum。（）{{ select(16) }}

• 对
• 错

17. 对正整数而言，oddCnt 统计的是输入中完全平方数的个数。（）{{ select(17) }}

• 对
• 错

18. 如果两个数的约数和相等，后出现的数一定会替换先出现的数成为 bestPos。（）{{ select(18) }}

• 对
• 错

19. 若输入为：

    5
    6 28 12 18 25
    

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

• 0 2 56
• 1 2 56
• 1 5 56
• 2 2 31

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

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

(2)

01  #include <bits/stdc++.h>
02  using namespace std;
03
04  int main() {
05      int n, L;
06      cin >> n >> L;
07      vector<int> a(n);
08      for (int i = 0; i < n; i++) cin >> a[i];
09      sort(a.begin(), a.end());
10
11      vector<int> b;
12      for (int x : a) {
13          if (b.empty() || b.back() != x) b.push_back(x);
14      }
15
16      vector<long long> pref(b.size() + 1, 0);
17      for (int i = 0; i < (int)b.size(); i++)
18          pref[i + 1] = pref[i] + b[i];
19
20      long long total = 0, bestSum = 0;
21      int left = 0, bestLen = 0;
22      for (int right = 0; right < (int)b.size(); right++) {
23          while (b[right] - b[left] > L) left++;
24          int len = right - left + 1;
25          long long windowSum = pref[right + 1] - pref[left];
26          total += len;
27          if (len > bestLen || (len == bestLen && windowSum > bestSum)) {
28              bestLen = len;
29              bestSum = windowSum;
30          }
31      }
32
33      cout << b.size() << " " << total << " "
34           << bestLen << " " << bestSum << "\n";
35      return 0;
36  }

21. 第 11 至 14 行执行后，b 中的元素严格递增。（）{{ select(21) }}

• 对
• 错

22. 变量 total 统计的是原数组 a 中满足最大值与最小值之差不超过 L 的连续子数组个数。（）{{ select(22) }}

• 对
• 错

23. 对任意 0 <= left <= right < b.size()，表达式 pref[right + 1] - pref[left] 表示 b[left] 到 b[right] 的元素和。（）{{ select(23) }}

• 对
• 错

24. 若输入为：

    7 3
    5 1 3 3 7 8 10
    

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

• 6 12 3 20
• 6 13 25
• 7 13 3 25
• 6 13 4 25

25. 使用第 24 题的输入，当 right 指向值 8 时，第 23 行循环结束后，left 指向的值是（）{{ select(25) }}

• 1
• 3
• 5
• 7

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

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

(3)

01  #include <bits/stdc++.h>
02  using namespace std;
03
04  int main() {
05      int n, m;
06      cin >> n >> m;
07      vector<string> g(n);
08      for (int i = 0; i < n; i++) cin >> g[i];
09
10      vector<vector<int>> dist(n, vector<int>(m, -1));
11      queue<pair<int, int>> q;
12      int sx = 0, sy = 0;
13      for (int i = 0; i < n; i++) {
14          for (int j = 0; j < m; j++) {
15              if (g[i][j] == 'S') {
16                  sx = i;
17                  sy = j;
18              }
19          }
20      }
21
22      dist[sx][sy] = 0;
23      q.push({sx, sy});
24      int dx[4] = {-1, 0, 1, 0};
25      int dy[4] = {0, 1, 0, -1};
26      while (!q.empty()) {
27          auto cur = q.front();
28          q.pop();
29          int x = cur.first, y = cur.second;
30          for (int k = 0; k < 4; k++) {
31              int nx = x + dx[k], ny = y + dy[k];
32              if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
33              if (g[nx][ny] == '#' || dist[nx][ny] != -1) continue;
34              dist[nx][ny] = dist[x][y] + 1;
35              q.push({nx, ny});
36          }
37      }
38
39      int cnt = 0, far = 0, border = 0;
40      for (int i = 0; i < n; i++) {
41          for (int j = 0; j < m; j++) {
42              if (dist[i][j] != -1) {
43                  cnt++;
44                  far = max(far, dist[i][j]);
45                  if (i == 0 || i == n - 1 || j == 0 || j == m - 1)
46                      border++;
47              }
48          }
49      }
50      cout << cnt << " " << far << " " << border << "\n";
51      return 0;
52  }

27. 程序使用广度优先搜索，求出从 S 到每个可达非障碍格子的最短步数。（）{{ select(27) }}

• 对
• 错

28. 改变第 24、25 行中四个方向的枚举顺序，所有可达格子的 dist 值一定可能发生变化。（）{{ select(28) }}

• 对
• 错

29. 若 S 位于网格边界上，并且可达，则它会被计入 border。（）{{ select(29) }}

• 对
• 错

30. 若输入为：

    4 6
    S..#..
    .#....
    ..##..
    ......
    

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

• 19 8 14
• 20 8 15
• 20 7 15
• 21 8 15

31. 使用第 30 题的输入，距离 S 恰好为 6 的格子共有（）个{{ select(31) }}

• 2
• 3
• 4
• 5

32. 设网格大小为 $n × m$，该程序时间复杂度和空间复杂度均为（）{{ select(32) }}

• $O(n + m)$
• $O(nm)$
• $O(nm \log(nm))$
• $O(2^{n+m})$

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

(1)（包含密码字符的子串数）

给定两个只含数字字符的字符串 s 和 key，其中 key 长度至少为 1。请统计 s 中有多少个连续子串，使得该子串中每个数字出现次数都不少于它在 key 中出现的次数。

01  #include <bits/stdc++.h>
02  using namespace std;
03
04  int main() {
05      string s, key;
06      cin >> s >> key;
07      vector<int> need(10, 0), cur(10, 0);
08      for (char c : key) need[c - '0'];
09
10      int kinds = 0;
11      for (int i = 0; i < 10; i++)
12          if (need[i] > 0) kinds++;
13
14      int have = 0, left = 0;
15      long long ans = 0;
16      int n = (int)s.size();
17      for (int right = 0; right < n; right++) {
18          int x = ①;
19          cur[x]++;
20          if (②) have++;
21          while (③) {
22              ans += ④;
23              int y = s[left] - '0';
24              if (⑤) have--;
25              cur[y]--;
26              left++;
27          }
28      }
29      cout << ans << "\n";
30      return 0;
31  }

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

• s[right] - '0'
• s[left] - '0'
• key[right] - '0'
• right - '0'

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

• cur[x] == need[x]
• cur[x] > need[x]
• need[x] == 0
• cur[x] == 0

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

• have == kinds
• have < kinds
• left > right
• cur[x] >= need[x]

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

• n - right
• right - left + 1
• left + 1
• n - left

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

• cur[y] == need[y]
• cur[y] < need[y]
• need[y] == 0
• cur[y] == 0

(2)（任务最早完成时间）

有 $n$ 个任务，编号为 $1..n$。第 $i$ 个任务耗时 $t[i]$。共有 $m$ 条依赖关系 $u v$，表示任务 $u$ 必须在任务 $v$ 开始前完成。若依赖关系无环，输出完成所有任务所需的最短时间；若有环，输出 Cycle。

01  #include <bits/stdc++.h>
02  using namespace std;
03
04  int main() {
05      int n, m;
06      cin >> n >> m;
07      vector<int> t(n + 1), indeg(n + 1, 0), dp(n + 1, 0);
08      vector<vector<int>> g(n + 1);
09
10      for (int i = 1; i <= n; i++) cin >> t[i];
11      for (int i = 0; i < m; i++) {
12          int u, v;
13          cin >> u >> v;
14          g[u].push_back(v);
15          ⑥;
16      }
17
18      queue<int> q;
19      for (int i = 1; i <= n; i++) {
20          if (⑦) {
21              q.push(i);
22              dp[i] = t[i];
23          }
24      }
25
26      int seen = 0, ans = 0;
27      while (!q.empty()) {
28          int u = q.front();
29          q.pop();
30          seen++;
31          ⑧;
32          for (int v : g[u]) {
33              dp[v] = ⑨;
34              indeg[v]--;
35              if (⑩) q.push(v);
36          }
37      }
38
39      if (seen < n) cout << "Cycle\n";
40      else cout << ans << "\n";
41      return 0;
42  }

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

• indeg[v]++
• indeg[u]++
• indeg[v]--
• dp[v]++

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

• indeg[i] == 0
• indeg[i] == 1
• t[i] == 0
• g[i].empty()

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

• ans = max(ans, dp[u])
• ans += dp[u]
• ans = dp[u]
• ans = max(ans, t[u])

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

• max(dp[v], dp[u] + t[v])
• max(dp[u], dp[v] + t[u])
• dp[u] + t[u]
• min(dp[v], dp[u] + t[v])

42. ⑩ 处应填（）{{ select(42) }}

• indeg[v] == 0
• indeg[u] == 0
• dp[v] == 0
• g[v].empty()