本卷由原试卷转换。题号已按 Hydro 作答顺序展平；程序代码保留为原卷高清截图。

一、选择题（每题 2 分，共 30 分）

1. 根据 NOI 系列比赛的规则，CSP-J 第二轮考场上，不可以（　）。

{{ select(1) }}

• 进行 Deep sleep
• 打开 GUIDE
• 自行重启电脑
• 食用豆包

2. C++ 表达式 bool(4)+bool(-1)+int(-3.7) 的值是（　）。

{{ select(2) }}

• $-4$
• $-3$
• $-2$
• $-1$

3. 现定义数组 int a[10]，想要得到 a[7] 的指针，下列写法正确的是（　）。

{{ select(3) }}

• &(a+7)
• *a+7
• a+28
• a+7

4. 令 $T$ 为一棵有根树，结点 8 的祖先有 1、2、3、5、9，结点 5 的祖先有 2、3、9。那么在结点 1、9、5、2 中，深度最大的结点是（　）。

{{ select(4) }}

• 1
• 8
• 5
• 9

5. 小明有一堆卡片，每张卡片写有 $1\sim9$。一天上午，他找了一些人，每个人恰好分到一张卡片，并告诉他们：卡片上写着几，就在下午几点把卡片还回来（放到卡片堆的最上面），形成一叠卡片。这样，通过所有人合作，就能给所有卡片排序。该方法最接近于（　）。

{{ select(5) }}

• 计数排序
• 冒泡排序
• 选择排序
• 插入排序

6. 现有一个单向链表，有 $n$ 个结点。链表内有两个结点 $p,q$，它们的距离是一个未知数 $d$（和 $n$ 不同阶）。现在想要判断，假如一个指针从链表头开始遍历，会先遍历到 $p$ 还是 $q$，能做到的最好复杂度为（　）。

{{ select(6) }}

• $O(1)$
• $O(d)$
• $O(n)$
• $O(dn)$

7. 计算 $(2026)_8+(2026)_{16}-(10\ 0000\ 0000\ 0000)_2$ 的结果为（　）。

{{ select(7) }}

• 2026
• 1092
• 1084
• 前三个选项都不对

8. 考虑如下程序片段，其输出为（　）。

{{ select(8) }}

• 10
• 15
• 0
• 前三个选项都不对

9. 一棵二叉树的前序遍历为 EBCDAFGH，中序遍历为 CBDFGAEH，则其后序遍历为（　）。

{{ select(9) }}

• HGFADCBE
• CFGADBHE
• HGFADCBE
• 前三个选项都不对

10. 字符串 yundou 有（　）个没有重复字母的、长度为 3 的子序列（下标可以不连续）。

{{ select(10) }}

• 15
• 19
• 119
• 前三个选项都不对

11. 现有一道区间动态规划题，转移方程为

$$f(l,r)= \begin{cases} \max\{f(l,r-1),f(l+1,r)\}+w_{l,r}, & 1\le l<r\le n,\\ w_{l,r}, & 1\le l=r\le n. \end{cases}$$

其中 $n$ 为输入的正整数，$w$ 为输入的二维数组，保证 $3\le n\le500$，$1\le w_{l,r}\le10^6$。下列说法正确的是（　）。

{{ select(11) }}

• 用程序求解动态规划时，无论采用何种写法，$f(2,8)$ 总是先于 $f(5,9)$ 被计算出。
• $f(1,n)$ 可能超过 32 位有符号整数可表示的范围。
• 求解 $f(1,n)$ 的时间复杂度为 $O(n^2)$。
• 如果把 $w_{1,3}$ 增加 $9.9\times10^5$（仍然满足 $w_{l,r}\le10^6$），那么 $f(1,n)$ 至少增加 1。

12. 在如下代码框中每行选取一条语句，从上到下构成一个程序片段，其输出最大值为（　）。

{{ select(12) }}

• 9
• 27
• 28
• 前三个选项都不对

13. yummy 正在做一道图论题，需要存储一张 $n$ 个结点、$m$ 条边的有向图。为此，他把结点依次编号为 $1\sim n$，并使用 vector<int> g[100001] 来存图。具体地，g[u] 存储了 $u$ 所有出边的终点。下列说法正确的是（　）。

{{ select(13) }}

• g[u].size() 记录了结点 $u$ 的度数。
• 要判断是否存在一条边 $x\to y$，只需判断 g[x][y] 是否存在。
• 要在图上加入一条边 $x\to y$，可以写成 g[x].push_back(y);。
• 如果 $n=10^5$、$m=5\times10^5$，那么会发生数组或 vector 溢出。

14. 正整数 $m$ 满足：对于所有整数 $2\le x\le100$，如果 $\gcd(x,m)=1$，那么 $x$ 是素数。那么，$m$ 可以是（　）。

{{ select(14) }}

• 480
• 420
• 2026
• 前三个选项都不对

15. 考虑正十边形的十个顶点。任意选择三个顶点可以构成（　）种三角形（全等的三角形看作同一种）。

{{ select(15) }}

• 8
• 12
• 6
• 120

二、阅读程序（共 40 分）

（一）程序 1（原题 2.1，共 12 分）

输入数据满足：$1\le n\le10$，$0\le x\le1023$。

判断题（每题 1.5 分）

16. 对任意合法的 $x$，trans(x) 的三进制表示与 $x$ 的二进制表示具有相同的数字序列。

{{ select(16) }}

• 正确
• 错误

17. 对任意满足 $0\le x<1023$ 的整数 $x$，均有 trans(x + 1) > trans(x)。

{{ select(17) }}

• 正确
• 错误

18. 若 $x$ 的二进制表示中恰有 $t$ 个数位为 1，则 $\operatorname{trans}(x)=\dfrac{3^t-1}{2}$。

{{ select(18) }}

• 正确
• 错误

19. 将第 9 行的 p *= 3; 改为 p <<= 1;，对任意合法输入，程序输出的数列与输入的 $x$ 数列相同。

{{ select(19) }}

• 正确
• 错误

选择题（每题 3 分）

20. 输入为 5\n0 1 2 5 10 时，程序输出为（　）。

{{ select(20) }}

• 0 1 2 10 30
• 0 1 3 10 30
• 0 1 3 12 30
• 0 1 3 10 27

21. 在给定输入范围内，trans(x) 的最大可能值为（　）。

{{ select(21) }}

• 19682
• 29524
• 59048
• 59049

（二）程序 2（原题 2.2，共 13 分）

输入数据满足：$2\le k\le n\le2\times10^5$，$0\le l_i\le r_i\le10^9$。

判断题（每题 1.5 分）

22. 排序完成后，数组中的线段按右端点从小到大排列；右端点相同时，按左端点从大到小排列。

{{ select(22) }}

• 正确
• 错误

23. 对任意整数 $d\ge2$，若 check(d) 的返回值为真，则 check(d - 1) 的返回值也一定为真。

{{ select(23) }}

• 正确
• 错误

选择题

24.（3 分）输入为：

5 3
1 3
4 5
7 9
10 11
12 15

程序输出为（　）。

{{ select(24) }}

• -1
• 2
• 3
• 4

25.（3 分）令 $C=\max r_i-\min l_i$，该程序的时间复杂度为（　）。

{{ select(25) }}

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

26.（4 分）若将第 22 行的判断条件改为 a[i].l > last + d，其余代码不变。对第 24 题给出的输入，程序输出为（　）。

{{ select(26) }}

• -1
• 1
• 2
• 3

（三）程序 3（原题 2.3，共 15 分）

输入数据满足：$1\le n\le1000$，$1\le q\le1000$，所有输入整数均在 int 范围内。

判断题（每题 1.5 分）

27. 若插入的 $n$ 个数互不相同且严格递增，则程序第二行输出为 n 1。

{{ select(27) }}

• 正确
• 错误

28. 交换 dfs 函数中两次递归调用的先后顺序，程序最终输出可能发生改变。

{{ select(28) }}

• 正确
• 错误

选择题

29.（2 分）输入为 7 3\n5 3 8 2 4 7 9\n3 8 6 时，程序输出为（　）。

{{ select(29) }}

• 3 3 0 与 3 4
• 3 3 0 与 4 3
• 2 2 0 与 3 4
• 3 3 1 与 3 4

30.（3 分）输入为 6 2\n4 2 6 2 3 5\n2 4 时，程序输出为（　）。

{{ select(30) }}

• 2 6 与 4 2
• 3 6 与 4 2
• 3 5 与 3 3
• 3 6 与 3 2

31.（3 分）假设输入序列中整数 $x$ 至少出现一次。程序执行完建树操作后，令 int u = find_node(root, x);，则关于结点 $u$，下列说法中一定正确的是（　）。

{{ select(31) }}

• $u$ 一定是所有值为 $x$ 的结点中最后插入的结点。
• $u$ 的左子树中不存在值为 $x$ 的结点。
• $u$ 的右子树中一定存在值为 $x$ 的结点。
• $u$ 一定没有左儿子。

32.（4 分）若希望在 dfs 函数执行过程中，将二叉搜索树中所有结点的 val 按非递减顺序输出，则应将语句 cout << val[u] << " "; 加入哪个位置？

位置说明：Position A 在递归左子树之前；Position B 在递归左子树之后、递归右子树之前；Position C 在递归右子树之后、计算 sz[u] 之前；Position D 在计算 sz[u] 之后、判断叶结点之前。

{{ select(32) }}

• Position A
• Position B
• Position C
• Position D

三、完善程序（共 30 分）

（一）数轴上的饼干（原题 3.1，共 15 分）

数轴上有 $n$ 块饼干，第 $i$ 块饼干所在位置的坐标为 $a_i$，所有 $a_i$ 两两不同。

小 C 初始位于坐标 0。只要还有饼干没有被取走，他就重复下面的操作：

• 在所有尚未取走的饼干中，选择与当前位置距离最近的一块；
• 如果有两块饼干与当前位置的距离相同，则选择坐标较小的那一块；
• 移动到该饼干所在位置并将其取走。

请计算小 C 取走全部 $n$ 块饼干时移动的总距离。

输入满足 $1\le n\le10^5$，$-10^9\le a_i\le10^9$。试补全程序。

33. /* Blank 1 */ 应填（　）。

{{ select(33) }}

• r < n && a[r] < 0
• r < n && a[r] > 0
• r > 0 && a[r] < 0
• r <= n && a[r] < 0

34. /* Blank 2 */ 应填（　）。

{{ select(34) }}

• l >= 0 && r < n
• l >= 0 || r < n
• l < 0 || r >= n
• l >= 0 && r >= n

35. /* Blank 3 */ 应填（　）。

{{ select(35) }}

• l >= 0 && (r >= n || pos - a[l] <= a[r] - pos)
• l >= 0 && (r >= n || pos - a[l] < a[r] - pos)
• r < n && (l < 0 || pos - a[l] <= a[r] - pos)
• l >= 0 && (r >= n || -a[l] <= a[r])

36. /* Blank 4 */ 应填（　）。

{{ select(36) }}

• pos = a[--l]
• pos = a[l--]
• pos = a[l++]
• pos = a[r--]

37. /* Blank 5 */ 应填（　）。

{{ select(37) }}

• pos = a[++r]
• pos = a[r--]
• pos = a[r++]
• pos = a[--r]

（二）拆墙迷宫（原题 3.2，共 15 分）

有一个 $n\times m$ 的迷宫，其中 . 表示可以通过的空地，# 表示墙，S 表示起点，T 表示终点。每一步可以向上、下、左、右移动到相邻格子。

你至多可以选择一堵墙，在第一次走到这堵墙时将它拆掉，并进入这个格子；拆掉后该格子可正常通过。求从 S 到 T 的最少步数。若无法到达，输出 -1。

输入满足 $1\le n,m\le100$，且迷宫中恰有一个 S 和一个 T。试补全程序。

38. /* Blank 1 */ 应填（　）。

{{ select(38) }}

• fill(dista[0][0], dista[0][0] + 2, -1)
• memset(g, -1, sizeof(g))
• memset(dista, 0, sizeof(dista))
• memset(dista, -1, sizeof(dista))

39. /* Blank 2 */ 应填（　）。

{{ select(39) }}

• !q.empty()
• dista[tx][ty][0] == -1
• q.empty()
• q.size() == 1

40. /* Blank 3 */ 应填（　）。

{{ select(40) }}

• g[nx][ny] == '#' && u.used == 0
• g[nx][ny] != '#' && u.used == 1
• g[nx][ny] == '#' && u.used == 1
• g[nx][ny] == '#'

41. /* Blank 4 */ 应填（　）。

{{ select(41) }}

• u.used + (g[nx][ny] == '#')
• u.used
• u.used - (g[nx][ny] == '#')
• g[nx][ny] == '#'

42. /* Blank 5 */ 应填（　）。

{{ select(42) }}

• ans = min(ans, dista[tx][ty][1])
• ans = (ans == -1 ? dista[tx][ty][1] : min(ans, dista[tx][ty][1]))
• ans = (ans == -1 ? dista[tx][ty][1] : max(ans, dista[tx][ty][1]))
• ans = (ans == -1 ? -1 : min(ans, dista[tx][ty][1]))