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

1. 下列域名中，通常表示教育机构的是（）{{ select(1) }}

• .com
• .edu
• .gov
• .org

2. 若一段声音数据采样率为 $8000$ 次/秒，每次采样使用 $16$ bit，单声道，未压缩保存 $10$ 秒，需要的存储空间为（）{{ select(2) }}

• $80000$ Byte
• $160000$ Byte
• $1280000$ Byte
• $1600000$ Byte

3. 将二进制数 $(101101)_2$ 与十六进制数 $(3A)_{16}$ 相加，结果用八进制表示为（）{{ select(3) }}

• $(121)_8$
• $(147)_8$
• $(157)_8$
• $(205)_8$

4. 若一个 $8$ 位有符号整数采用补码表示，二进制 11110101 表示的值为 a；另有一个 $8$ 位无符号整数 b = 250。计算 a + b 后只保留低 $8$ 位，得到的无符号整数为（）{{ select(4) }}

• 239
• 245
• 250
• 255

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

   char c = 'm';
   int d = c - 'a';
   char t = 'A' + (d + 5) % 26;
   cout << t << " " << d;
   

• M 12
• R 17
• R 12
• Q 12

6. 设 int x = 42;，执行以下语句后，y 的值是（）{{ select(6) }}

   int y = ((x & 15) << 1) ^ (x >> 3);
   

• 17
• 21
• 25
• 29

7. 关于 C++ 中 const int n = 10;，下列说法正确的是（）{{ select(7) }}

• 后续可以执行 n = 12; 修改它
• 它声明的是一个值不可被普通赋值语句修改的整型常量
• 它一定只能作为全局变量使用
• 它不能用于任何数组长度定义

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

   int a = 4, b = 9;
   int *p = &a;
   int &r = b;
   *p += 2;
   r -= a;
   cout << a << " " << b;
   

• 4 5
• 6 3
• 6 5
• 4 3

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

   map<string, int> mp;
   mp["red"]++;
   mp["blue"] += 2;
   mp["red"] += mp["blue"];
   cout << mp["red"];
   

• 1
• 2
• 3
• 程序不能编译

10. 设 int a = 100000, b = 100000;，若计算 a * b 并希望结果正确保存，下列写法最合适的是（）{{ select(10) }}

• int c = a * b;
• long long c = a * b;
• long long c = 1LL * a * b;
• short c = a * b;

11. 一个普通队列初始为空，依次执行：入队 3、入队 5、出队、入队 7、入队 9、出队。此时从队首到队尾依次为（）{{ select(11) }}

• 3 5
• 5 7
• 7 9
• 9 7

12. 使用哈希函数 $h(x)=x\bmod5$，将 $7,12,17$ 插入哈希表时，若采用链地址法处理冲突，则这三个数会被放入（）{{ select(12) }}

• 同一个桶中
• 三个不同桶中
• 其中两个在同一桶，另一个在不同桶
• 无法插入

13. 某哈夫曼树有 $4$ 个叶子结点，权值分别为 $2,3,7,8$。其最小带权路径长度 WPL 为（）{{ select(13) }}

• 32
• 37
• 40
• 45

14. 有 $8$ 个相同的小球放入 $3$ 个不同的盒子，每个盒子至少 $1$ 个。共有（）种放法{{ select(14) }}

• 10
• 15
• 21
• 56

15. 关于高精度整数运算，下列说法最合理的是（）{{ select(15) }}

• 高精度加法通常可以用数组或字符串逐位模拟
• 只要使用 long long 就能保存任意大的整数
• 高精度整数不能进行加法
• 高精度整数只能用浮点数保存

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

(1)

01  #include <bits/stdc++.h>
02  using namespace std;
03
04  int main() {
05      string s, t;
06      cin >> s;
07      int blocks = 0, removed = 0, best = 0;
08      for (int i = 0; i < (int)s.size(); ) {
09          int j = i;
10          while (j < (int)s.size() && s[j] == s[i]) j++;
11          int len = j - i;
12          blocks++;
13          best = max(best, len);
14          if (len == 1) {
15              t.push_back(s[i]);
16          } else {
17              t.push_back(s[i]);
18              t += to_string(len);
19              removed += len - 1;
20          }
21          i = j;
22      }
23      cout << t << "\n";
24      cout << blocks << " " << removed << " " << best << "\n";
25      return 0;
26  }

16. 变量 blocks 统计的是原字符串中连续相同字符段的个数。（）{{ select(16) }}

• 对
• 错

17. 当某个连续段长度为 1 时，程序不会在 t 中追加数字 1。（）{{ select(17) }}

• 对
• 错

18. 变量 removed 统计的是压缩后字符串 t 比原字符串少的字符数。（）{{ select(18) }}

• 对
• 错

19. 若输入为：

    aaabbcddddaa
    

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

• a3b2cd4a2
• a3b2c1d4a2
• ab cda
• 3a2b1c4d2a

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

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

(2)

01  #include <bits/stdc++.h>
02  using namespace std;
03
04  struct Seg {
05      int l, r;
06  };
07
08  int main() {
09      int n;
10      cin >> n;
11      vector<Seg> a(n);
12      for (int i = 0; i < n; i++) cin >> a[i].l >> a[i].r;
13      sort(a.begin(), a.end(), [](const Seg &x, const Seg &y) {
14          if (x.r != y.r) return x.r < y.r;
15          return x.l < y.l;
16      });
17
18      int last = -1000000000;
19      int cnt = 0, total = 0;
20      for (auto s : a) {
21          if (s.l >= last) {
22              cnt++;
23              total += s.r - s.l;
24              last = s.r;
25          }
26      }
27      cout << cnt << " " << total << " " << last << "\n";
28      return 0;
29  }

21. 第 13 至 16 行将区间按右端点从小到大排序，右端点相同时按左端点从小到大排序。（）{{ select(21) }}

• 对
• 错

22. 若一个区间的左端点等于上一个被选区间的右端点，该区间可以被选择。（）{{ select(22) }}

• 对
• 错

23. 变量 total 统计的是所有输入区间长度之和。（）{{ select(23) }}

• 对
• 错

24. 若输入为：

    5
    1 3
    2 5
    4 6
    6 8
    7 9
    

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

• 2 5 8
• 3 6 8
• 3 7 9
• 4 8 9

25. 使用第 24 题的输入，排序后第 3 个区间是（）{{ select(25) }}

• [2,5]
• [4,6]
• [6,8]
• [7,9]

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

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

(3)

01  #include <bits/stdc++.h>
02  using namespace std;
03
04  int findRoot(vector<int> &fa, int x) {
05      if (fa[x] == x) return x;
06      fa[x] = findRoot(fa, fa[x]);
07      return fa[x];
08  }
09
10  int main() {
11      int n, m;
12      cin >> n >> m;
13      vector<int> fa(n + 1), sz(n + 1, 1);
14      for (int i = 1; i <= n; i++) fa[i] = i;
15
16      int merges = 0, redundant = 0, largest = 1;
17      for (int i = 0; i < m; i++) {
18          int u, v;
19          cin >> u >> v;
20          int ru = findRoot(fa, u);
21          int rv = findRoot(fa, v);
22          if (ru == rv) {
23              redundant++;
24          } else {
25              if (sz[ru] < sz[rv]) swap(ru, rv);
26              fa[rv] = ru;
27              sz[ru] += sz[rv];
28              merges++;
29              largest = max(largest, sz[ru]);
30          }
31      }
32      cout << merges << " " << redundant << " " << largest << "\n";
33      return 0;
34  }

27. findRoot 函数中第 6 行进行了路径压缩。（）{{ select(27) }}

• 对
• 错

28. 若读入的一条边的两个端点已经在同一连通块内，变量 redundant 会增加。（）{{ select(28) }}

• 对
• 错

29. 变量 largest 始终表示当前所有连通块大小之和。（）{{ select(29) }}

• 对
• 错

30. 若输入为：

    7 7
    1 2
    2 3
    4 5
    6 7
    5 6
    3 7
    1 7
    

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

• 5 2 7
• 6 1 7
• 6 0 7
• 7 1 7

31. 使用第 30 题的输入，读入前 4 条边后，连通块个数为（）{{ select(31) }}

• 2
• 3
• 4
• 5

32. 设有 $n$ 个点、$m$ 条边，若认为并查集单次操作近似为常数，则该程序时间复杂度为（）{{ select(32) }}

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

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

(1)（后缀表达式求值）

给定一个只含非负整数和 + - * / 的后缀表达式，记号之间用空格分隔。除法为整数除法，保证中间计算不会除以 0，且表达式合法。

01  #include <bits/stdc++.h>
02  using namespace std;
03
04  int main() {
05      string line, token;
06      getline(cin, line);
07      stringstream ss(line);
08      stack<int> st;
09      while (ss >> token) {
10          if (token == "+" || token == "-" || token == "*" || token == "/") {
11              int b = ①;
12              ②;
13              int a = st.top();
14              st.pop();
15              if (token == "+") st.push(③);
16              else if (token == "-") st.push(④);
17              else if (token == "*") st.push(a * b);
18              else st.push(a / b);
19          } else {
20              st.push(⑤);
21          }
22      }
23      cout << st.top() << "\n";
24      return 0;
25  }

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

• st.top()
• st.size()
• 0
• token[0]

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

• st.push(b)
• st.pop()
• st.top()
• b = st.top()

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

• a + b
• a - b
• b - a
• a * b

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

• a + b
• a - b
• b - a
• a * b

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

• stoi(token)
• token.size()
• token[0]
• 0

(2)（前缀和与二分查询）

给定长度为 $n$ 的正整数数组。每次查询给出 l, r, k，要求从位置 l 开始向右取尽量多的连续元素，但不能超过 r，并且这些元素的和不超过 k，输出可取元素个数。

01  #include <bits/stdc++.h>
02  using namespace std;
03
04  int main() {
05      int n, q;
06      cin >> n >> q;
07      vector<long long> pre(n + 1, 0);
08      for (int i = 1; i <= n; i++) {
09          long long x;
10          cin >> x;
11          pre[i] = ⑥;
12      }
13      while (q--) {
14          int l, r;
15          long long k;
16          cin >> l >> r >> k;
17          long long limit = ⑦;
18          int pos = int(⑧ - pre.begin()) - 1;
19          if (⑨) pos = r;
20          cout << ⑩ << "\n";
21      }
22      return 0;
23  }

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

• pre[i - 1] + x
• pre[i] + x
• pre[i - 1] - x
• x

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

• pre[l - 1] + k
• pre[l] + k
• pre[r] - k
• k

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

• upper_bound(pre.begin(), pre.end(), limit)
• lower_bound(pre.begin(), pre.end(), limit)
• find(pre.begin(), pre.end(), limit)
• max_element(pre.begin(), pre.end())

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

• pos > r
• pos < l
• pos == r
• pos == 0

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

• pos - l + 1
• pos - l
• r - pos + 1
• pos