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

1. 一个 32 位无符号整数可以表示的最大值，最接近下列哪个选项？（ ）

{{ select(1) }}

• $4×10^9$
• $3×10^{10}$
• $2×10^9$
• $2×10^{10}$

2. 在 C++ 中，执行 int x = 255; cout << (x & (x - 1)); 后，输出的结果是？（ ）

{{ select(2) }}

• 255
• 254
• 128
• 0

3. 函数 calc(n) 的定义如下，则 calc(5) 的返回值是多少？（ ）

int calc(int n) {
    if (n <= 1) return 1;
    if (n % 2 == 0) return calc(n / 2) + 1;
    else return calc(n - 1) + calc(n - 2);
}

{{ select(3) }}

• 5
• 6
• 7
• 8

4. 用 5 个权值 $10, 12, 15, 20, 25$ 构造哈夫曼树，该树的带权路径长度是多少？（ ）

{{ select(4) }}

• 176
• 186
• 196
• 206

5. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和，这个总和等于？（ ）

{{ select(5) }}

• 顶点数
• 边数
• 顶点数 + 边数
• 顶点数 * 2

6. 从 5 位男生和 4 位女生中选出 4 人组成一个学习小组，要求学习小组中男生和女生都有。有多少种不同的选举方法？（ ）

{{ select(6) }}

• 126
• 121
• 120
• 100

7. 假设 a、b、c 都是布尔变量，逻辑表达式 (a && b) || (!(c && a)) 的值与下列哪个表达式不始终相等？（ ）

{{ select(7) }}

• a && (b || !c)
• (a || !c) && (b || !c) && (a || !a)
• a && (!b || c)
• (!(a || b)) || (a && !c)

8. 已知 $f[0] = 1, f[1] = 1$，并且对于所有 $n \geq 2$ 有

   $f[n] = (f[n-1] + f[n-2]) \% 7$

   那么 $f[2025]$ 的值是多少？（ ）

{{ select(8) }}

• 2
• 4
• 5
• 6

9. 下列关于 C++ string 类的说法，正确的是？（ ）

{{ select(9) }}

• string 对象的长度在创建后不能改变。
• 可以使用 + 运算符直接连接一个 string 对象和一个 char 类型的字符。
• string 的 length() 和 size() 方法返回的值可能不同。
• string 对象必须以 '\0' 结尾，且这个结尾符计入 length()。

10. 考虑以下 C++ 函数：（ ）

void solve(int &a, int b) {
    a = a + b;
    b = a - b;
    a = a - b;
}
int main() {
    int x = 5, y = 10;
    solve(x, y);
}

在 main 函数调用 solve 后，x 和 y 的值分别是？（ ）

{{ select(10) }}

• 5, 10
• 10, 5
• 10, 10
• 5, 5

11. 一个 $8 \times 8$ 的棋盘，左上角坐标为 $(1,1)$，右下角为 $(8,8)$。一个机器人从 $(1,1)$ 出发，每次只能向右或向下走一步。要到达 $(4,5)$，有多少种不同的路径？（ ）

{{ select(11) }}

• 20
• 35
• 56
• 70

12. 某同学用冒泡排序对数组 $\{6, 1, 5, 2, 4\}$ 进行升序排序，请问需要进行多少次元素交换？（ ）

{{ select(12) }}

• 5
• 6
• 7
• 8

13. 十进制数 $720_{10}$ 和八进制数 $270_8$ 的和用十六进制表示是多少？（ ）

{{ select(13) }}

• $388_{16}$
• $3DE_{16}$
• $288_{16}$
• $990_{16}$

14. 一棵包含 $1000$ 个结点的完全二叉树，其中叶子结点的数量是多少？（ ）

{{ select(14) }}

• 499
• 512
• 500
• 501

15. 给定一个初始为空的整数栈 $S$ 和一个空的队列 $P$。我们按顺序处理输入的整数队列 $A: 7, 5, 8, 3, 1, 4, 2$。对队列 $A$ 中的每一个数，执行以下规则：如果该数是奇数，则将其压入栈 $S$；如果该数是偶数，且栈 $S$ 非空，则弹出一个栈顶元素，并加入到队列 $P$ 的末尾；如果该数是偶数，且栈 $S$ 为空，则不进行任何操作。当队列 $A$ 中的所有数据处理完毕后，队列 $P$ 的内容是什么？（ ）

{{ select(15) }}

• 5, 1, 3
• 7, 5, 3
• 3, 1, 5
• 5, 1, 3, 7

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

1.

01 #include <algorithm>
02 #include <cstdio>
03 #include <cstring>
04 inline int gcd(int a, int b) {
05     if (b == 0)
06         return a;
07     return gcd(b, a % b);
08 }
09 int main() {
10     int n;
11     scanf("%d", &n);
12     int ans = 0;
13     for (int i = 1; i <= n; ++i) {
14         for (int j = i + 1; j <= n; ++j) {
15             for (int k = j + 1; k <= n; ++k) {
16                 if (gcd(i, j) == 1 && gcd(j, k) == 1
17                     && gcd(i, k) == 1) {
18                     ++ans;
19                 }
20             }
21         }
22     }
23     printf("%d\n", ans);
24     return 0;
25 }

判断题

16. （1 分）当输入为 2 时，程序并不会执行第 16 行的判断语句。（ ）

{{ select(16) }}

• 正确
• 错误

17. 将第 16 行中的 && gcd(i,k)==1 删去不会影响程序运行结果。（ ）

{{ select(17) }}

• 正确
• 错误

18. 当输入的 $n \geq 3$ 时，程序总是输出一个正整数。（ ）

{{ select(18) }}

• 正确
• 错误

单选题

19. 将第 7 行的 gcd(b, a % b) 改为 gcd(a, a % b) 后，程序可能出现的问题是（ ）

{{ select(19) }}

• 输出的答案大于原答案。
• 输出的答案小于原答案。
• 程序有可能陷入死循环。
• 可能发生整型溢出问题。

20. 当输入为 8 的时候，输出为（ ）

{{ select(20) }}

• 37
• 42
• 35
• 25

21. 调用 gcd(36,42) 会返回（ ）

{{ select(21) }}

• 6
• 252
• 3
• 2

2.

01 #include <algorithm>
02 #include <cstdio>
03 #include <cstring>
04 #define ll long long
05 int n, k;
06 int a[200007];
07 int ans[200007];
08 int main() {
09     scanf("%d%d", &n, &k);
10     for (int i = 1; i <= n; ++i) {
11         scanf("%d", &a[i]);
12     }
13     std::sort(a + 1, a + n + 1);
14     n = std::unique(a + 1, a + n + 1) - a - 1;
15     for (int i = 1, j = 0; i <= n; ++i) {
16         for (; j < i && a[i] - a[j + 1] > k; ++j)
17             ;
18         ans[i] = ans[j] + 1;
19     }
20     printf("%d\n", ans[n]);
21     return 0;
22 }

判断题

22. 当输入为 “3 1 3 2 1” 时，输出结果为 2。（ ）

{{ select(22) }}

• 正确
• 错误

23. 假如输入的 $n$ 为正整数，输出的答案一定小于等于 $n$，大于等于 1。

{{ select(23) }}

• 正确
• 错误

24. 将第 14 行的 n = std::unique(a+1, a+n+1) - a - 1; 删除后，有可能出现与原本代码不同的输出结果。（ ）

{{ select(24) }}

• 正确
• 错误

单选题

25. 假设输入的 $a$ 数组和 $k$ 均为正整数，执行第 18 行代码时，一定满足的条件不包括（ ）

{{ select(25) }}

• $j < i$
• $a[i] - a[j] > k$
• $j <= n$
• $a[j] \leq a[i]$

26. 当输入 $n = 100, k = 2, a = \{1, 2, \ldots, 100\}$ 时，输出为（ ）

{{ select(26) }}

• 34
• 100
• 50
• 33

27. 假设输入的 $a$ 数组和 $k$ 均为正整数，但 $a$ 数组不一定有序，则若误删去第 13 行的 std::sort(a+1,a+n+1);，程序又可能出现的问题有（ ）

{{ select(27) }}

• 输出的答案比原本答案更大
• 输出的答案比原本答案更小
• 出现死循环行为
• 以上均可能发生

3.

01 #include <algorithm>
02 #include <cstdio>
03 #include <cstring>
04 #define ll long long
05 int f[5007][5007];
06 int a[5007], b[5007];
07 int n;
08 int main() {
09     scanf("%d", &n);
10     for (int i = 1; i <= n; ++i) {
11         scanf("%d", &a[i]);
12     }
13     for (int i = 1; i <= n; ++i) {
14         scanf("%d", &b[i]);
15     }
16     for (int i = 1; i <= n; ++i) {
17         for (int j = 1; j <= n; ++j) {
18             f[i][j] = std::max(f[i][j], std::max(f[i - 1][j], f[i][j - 1]));
19             if (a[i] == b[j]) {
20                 f[i][j] = std::max(f[i][j], f[i - 1][j - 1] + 1);
21             }
22         }
23     }
24     printf("%d\n", f[n][n]);
25     return 0;
26 }

判断题

28. 当输入为 “4 1 2 3 4 1 3 2 2” 时，输出为 2。（ ）

{{ select(28) }}

• 正确
• 错误

29. 当程序运行完毕后，对于所有的 $1 \leq i, j \leq n$，都一定有 $f[i][j] \leq f[n][n]$。（ ）

{{ select(29) }}

• 正确
• 错误

30. 将第 18 行的

    f[i][j] = std::max(f[i][j], std::max(f[i-1][j], f[i][j-1])); 删除后，并不影响程序运行结果。（ ）

{{ select(30) }}

• 正确
• 错误

单选题

31. 输出的答案满足的性质有（ ）

{{ select(31) }}

• 小于等于 $n$
• 大于等于 $0$
• 不一定大于等于 $1$
• 以上均是

32. 如果在第 16 行的循环前加上以下两行：std::sort(a+1, a+n+1); std::sort(b+1, b+n+1); 则答案会（ ）

{{ select(32) }}

• 变大或不变
• 变小或不变
• 一定变大
• 不变

33. 如果输入的 $a=\{1,2,\ldots,n\}$，而且 $b$ 数组中数字均为 $1 \sim n$ 中的正整数，则上述代码等价于下面哪个问题：（ ）

{{ select(33) }}

• 求 b 数组去重后的长度
• 求 b 数组的最长上升子序列
• 求 b 数组的长度
• 求 b 数组的最大值

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

1. (字符串解码)

“行程长度编码”（Run-Length Encoding）是一种无损压缩算法，常用于压缩重复字符较多的数据，以减少存储空间。假设原始字符串中不包含数字字符。压缩规则如下：

1. 如果原始字符串中一个字符连续出现 $N$ 次（$N \geq 2$），在压缩字符串中它被表示为“字符+数字 N”。
   • 例如，编码 "A12" 代表 12 个连续的字符 A。
2. 如果原始字符串中一个字符只出现 1 次，在压缩字符串中它就表示为该字符本身。
   • 例如，编码 "B" 代表 1 个字符 B。

以下程序实现读取压缩字符串并输出其原始的、解压后的形式。

试补全程序 。

01 #include <cctype>
02 #include <iostream>
03 #include <string>
04 using namespace std;
05 
06 int main() {
07     string z;
08     cin >> z;
09     string s = "";
10 
11     for (int i = 0; i < z.length(); ) {
12         char ch = z[i];
13 
14         if (____①____ && isdigit(z[i + 1])) {
15             i++;
16             int count = 0;
17             while (i < z.length() && isdigit(z[i])) {
18                 count = ____②____;
19                 i++;
20             }
21             for (int j = 0; j < ____③____; ++j) {
22                 s += ch;
23             }
24         } else {
25             s += ____④____;
26             ____⑤____;
27         }
28     }
29 
30     cout << s << endl;
31     return 0;
32 }

1. ①处应填（ ）

{{ select(34) }}

• i < z.length()
• i - 1 >= 0
• i + 1 < z.length()
• isdigit(z[i])

2. ②处应填（ ）

{{ select(35) }}

• count + (z[i] - '0')
• count * 10 + (z[i] - '0')
• z[i] - '0'
• count + 1

3. ③处应填（ ）

{{ select(36) }}

• count - 1
• count
• 10
• z[i] - '0'

4. ④处应填（ ）

{{ select(37) }}

• z[i+1]
• ch
• z.back()
• (char)z[i] + 1

5. ⑤处应填（ ）

{{ select(38) }}

• i--
• i = i + 2
• i++
• // 不执行任何操作

2. （精明与糊涂）

有 $N$ 个人，分为两类：

1. 精明人：永远能正确判断其他人是精明还是糊涂；
2. 糊涂人：判断不可靠，会给出随机的判断。

已知精明人严格占据多数，即如果精明人有 $k$ 个，则满足 $k > N/2$。

你只能通过函数 query(i, j) 让第 $i$ 个人判断第 $j$ 个人：

• 返回 true 表示判断结果为“精明人”；
• 返回 false 表示判断结果为“糊涂人”。

目标：通过这些互相判断，找出至少一个 100% 确定的精明人。

提示：可以利用“精明人占多数”的优势，设置一个“消除”的过程，让人们互相判断并进行抵消。经过若干轮抵消后，最终留下的候选者必然属于多数派，即精明人。

例如，假设有三个人 $0, 1, 2$。

• 如果 $0$ 说 $1$ 是糊涂人，而 $1$ 也说 $0$ 是糊涂人，则 $0$ 和 $1$ 至少有一个是糊涂人。程序将同时淘汰 $0$ 和 $1$。
• 由于三人里至少有两个精明人，我们确定 $2$ 是精明人。

试补全程序。

01 #include <iostream>
02 #include <vector>
03 using namespace std;
04 
05 int N;
06 bool query(int i, int j);
07 
08 int main() {
09     cin >> N;
10     int candidate = 0;
11     int count = ____①____;
12 
13     for (int i = 1; i < N; ++i) {
14         if (____②____) {
15             candidate = i;
16             count = 1;
17         } else {
18             if (____③____) {
19                 ____④____;
20             } else {
21                 count++;
22             }
23         }
24     }
25 
26     cout << ____⑤____ << endl;
27     return 0;
28 }

1. ①处应填（ ）

{{ select(39) }}

• 0
• 1
• N
• -1

2. ②处应填（ ）

{{ select(40) }}

• count < 0
• count == 1
• count == 0
• query(candidate, i) == false

3. ③处应填（ ）

{{ select(41) }}

• query(candidate, i) == false
• query(i, candidate) == true
• query(candidate, i) == false && query(i, candidate) == false
• query(candidate, i) == false || query(i, candidate) == false

4. ④处应填（ ）

{{ select(42) }}

• count--
• break
• count++
• candidate = i

5. ⑤处应填（ ）

{{ select(43) }}

• N - 1
• count
• candidate
• 0