一、单项选择题

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

【第 1 题】

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

{{ select(1) }}

• $4 \times 10^9$
• $3 \times 10^{10}$
• $2 \times 10^9$
• $2 \times 10^{10}$

【第 2 题】

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

• 255
• 254
• 128
• 0

【第 3 题】

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

{{ 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 \ge 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++ 函数：

在 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 分）

阅读程序（一）

判断题

16. 当输入为 $2$ 时，程序并不会执行第 $16$ 行的判断语句。 {{ select(16) }}

• 正确
• 错误

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

    {{ select(17) }}

• 正确
• 错误

18. 当输入的 $n \ge 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

阅读程序（二）

判断题

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 \le i$
• $a[i]-a[j]>k$
• $j \le n$
• $a[j] < 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) }}

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

阅读程序（三）

判断题

28. 当输入 “$4\ 1\ 2\ 3\ 4\ 1\ 3\ 2\ 2$” 时，输出为 $2$。 {{ select(28) }}

• 正确
• 错误

29. 当程序运行完毕后，对于所有的 $1 \le i,j \le n$，都一定有 $f[i][j] \le 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 分）

程序填空(一)

（字符串解码）“行程长度编码”（Run-Length Encoding）是一种无损压缩算法，常

用于压缩重复字符较多的数据，以减少存储空间。假设原始字符串不包含数字字符。压缩规则

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

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

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

• $i < z.length()$
• $i - 1 \ge 0$
• $i + 1 < z.length()$
• $isdigit(z[i])$

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

• $count + (z[i] - '0')$
• $count \times 10 + (z[i] - '0')$
• $z[i] - '0'$
• $count + 1$

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

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

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

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

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

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

完善程序(二)

（精明与糊涂）有 $N$ 个人，分为两类：i）精明人：永远能正确判断其他人是精明还是糊涂；

ii）糊涂人：判断不可靠，会给出随机的判断。已知精明人严格占据多数，即如果精明人有 $k$个，则满足 $k > N/2$。

你只能通过函数 $query(i,j)$ 让第 $i$ 个人判断第 $j$ 个人：返回 $true$ 表示判断结果为 “精明人”；返回 $false$ 表示判断结果为 “糊涂人”。你的目标是，通过这些互相判断，找出至少一个百分之百能确定的精明人。同时，你无需关心 $query(i,j)$ 的内部实现。

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

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

试补全程序。

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

• $0$
• $1$
• $N$
• $-1$

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

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

41. ③ 处应填（ ）。 {{ 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$

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

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

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

• $N - 1$
• $count$
• $candidate$
• $0$