一、单项选择题（共 15 题，每题 2 分，共计 30 分）

1. 在 Linux 系统终端中，用于切换工作目录的命令为（ ）。

{{ select(1) }}

• ls
• cd
• cp
• all

2. 你同时用 time 命令和秒表为某个程序在单核 CPU 的运行计时。假如 time 命令的输出如下：

   real    0m30.721s
   user    0m24.579s
   sys     0m6.123s
   

   以下最接近秒表计时的时长为（ ）。

{{ select(2) }}

• $30\text{s}$
• $24\text{s}$
• $18\text{s}$
• $6\text{s}$

3. 若元素 a、b、c、d、e、f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次退栈操作，则不可能得到的出栈序列是（ ）。

{{ select(3) }}

• dcebfa
• cbdaef
• bcaefd
• afedcb

4. 考虑对 $n$ 个数进行排序，以下最坏时间复杂度低于 $O(n^2)$ 的排序方法是（ ）。

{{ select(4) }}

• 插入排序
• 冒泡排序
• 归并排序
• 快速排序

5. 假设在基数排序过程中，受宇宙射线的影响，某项数据异变为一个完全不同的值。请问排序算法结束后，可能出现的最坏情况是（ ）。

{{ select(5) }}

• 移除受影响的数据后，最终序列是有序序列
• 移除受影响的数据后，最终序列是前后两个有序的子序列
• 移除受影响的数据后，最终序列是一个有序的子序列和一个基本无序的子序列
• 移除受影响的数据后，最终序列基本无序

6. 计算机系统用小端（Little Endian）和大端（Big Endian）来描述多字节数据的存储地址顺序模式，其中小端表示将低位字节数据存储在低地址的模式、大端表示将高位字节数据存储在低地址的模式。在小端模式的系统和大端模式的系统分别编译和运行以下 C++ 代码段表示的程序，将分别输出什么结果？（ ）

{{ select(6) }}

• EF、EF
• EF、DE
• DE、EF
• DE、DE

7. 一个深度为 $5$（根结点深度为 $1$）的完全 $3$ 叉树，按前序遍历的顺序给结点从 $1$ 开始编号，则第 $100$ 号结点的父结点是第（ ）号。

{{ select(7) }}

• $95$
• $96$
• $97$
• $98$

8. 强连通图的性质不包括（ ）。

{{ select(8) }}

• 每个顶点的度数至少为 $1$
• 任意两个顶点之间都有边相连
• 任意两个顶点之间都有路径相连
• 每个顶点至少都连有一条边

9. 每个顶点度数均为 $2$ 的无向图称为“$2$ 正规图”。由编号为从 $1$ 到 $n$ 的顶点构成的所有 $2$ 正规图，其中包含欧拉回路的不同 $2$ 正规图的数量为（ ）。

{{ select(9) }}

• $n!$
• $(n-1)!$
• $n!/2$
• $(n-1)!/2$

10. 共有 $8$ 人选修了程序设计课程，期末大作业要求由 $2$ 人组成的团队完成。假设不区分每个团队内 $2$ 人的角色和作用，请问共有多少种可能的组队方案。（ ）

{{ select(10) }}

• $28$
• $32$
• $56$
• $64$

11. 小明希望选到形如“省 A·$\mathcal{L}\mathcal{L}\mathcal{D}\mathcal{D}\mathcal{D}$”的车牌号。车牌号在“·”之前的内容固定不变；后面的 $5$ 位号码中，前 $2$ 位必须是大写英文字母，后 $3$ 位必须是阿拉伯数字（$\mathcal{L}$ 代表 A 至 Z，$\mathcal{D}$ 表示 $0$ 至 $9$，两个 $\mathcal{L}$ 和三个 $\mathcal{D}$ 之间可能相同也可能不同）。请问总共有多少个可供选择的车牌号。（ ）

{{ select(11) }}

• $20280$
• $52000$
• $676000$
• $1757600$

12. 给定地址区间为 $0\sim 9$ 的哈希表，哈希函数为 $h(x)=x\bmod 10$，采用线性探查的冲突解决策略（对于出现冲突情况，会往后探查第一个空的地址存储；若地址 $9$ 冲突了则从地址 $0$ 重新开始探查）。哈希表初始为空，依次存储 $(71,23,73,99,44,79,89)$ 后，请问 $89$ 存储在哈希表哪个地址中。（ ）

{{ select(12) }}

• $9$
• $0$
• $1$
• $2$

13. 对于给定的 $n$，分析以下代码段对应的时间复杂度，其中最为准确的时间复杂度为（ ）。

{{ select(13) }}

• $O(n)$
• $O(n\log n)$
• $O(n\sqrt n)$
• $O(n^2)$

14. 以比较为基本运算，在 $n$ 个数的数组中找最大的数，在最坏情况下至少要做（ ）次运算。

{{ select(14) }}

• $n/2$
• $n-1$
• $n$
• $n+1$

15. ack 函数在输入参数“$(2,2)$”时的返回值为（ ）。

{{ select(15) }}

• $5$
• $7$
• $9$
• $13$

二、阅读程序（除特殊说明外，判断题每题 1.5 分，选择题每题 3 分，共计 40 分）

第 1 题

假设输入字符串由 ASCII 可见字符组成，完成下面的判断题和单选题：

16. （1 分）当输入为 abcde fg 时，输出为 $-1$。（ ）

{{ select(16) }}

• 正确
• 错误

17. 当输入为 abbababbbab abab 时，输出为 $4$。（ ）

{{ select(17) }}

• 正确
• 错误

18. 当输入为 GoodLuckCsp2022 22 时，第 20 行的 j++ 语句执行次数为 $2$。（ ）

{{ select(18) }}

• 正确
• 错误

19. 该算法最坏情况下的时间复杂度为（ ）。

{{ select(19) }}

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

20. f(a, b) 与下列（ ）语句的功能最类似。

{{ select(20) }}

• a.find(b)
• a.rfind(b)
• a.substr(b)
• a.compare(b)

21. 当输入为 baaabaaabaaabaaaa aaaa 时，第 20 行的 j++ 语句执行次数为（ ）。

{{ select(21) }}

• $9$
• $10$
• $11$
• $12$

第 2 题

假设输入的 $n$ 为不大于 $100$ 的正整数，$k$ 为不小于 $2$ 且不大于 $100$ 的正整数，val[i] 在 int 表示范围内，完成下面的判断题和单选题：

22. 这是一个不稳定的排序算法。（ ）

{{ select(22) }}

• 正确
• 错误

23. 该算法的空间复杂度仅与 $n$ 有关。（ ）

{{ select(23) }}

• 正确
• 错误

24. 该算法的时间复杂度为 $O(m(n+k))$。（ ）

{{ select(24) }}

• 正确
• 错误

25. 当输入为 5 3 98 26 91 37 46 时，程序第一次执行到第 36 行，val[] 数组的内容依次为（ ）。

{{ select(25) }}

• 91 26 46 37 98
• 91 46 37 26 98
• 98 26 46 91 37
• 91 37 46 98 26

26. 若 val[i] 的最大值为 $100$，$k$ 取（ ）时算法运算次数最少。

{{ select(26) }}

• $2$
• $3$
• $10$
• 不确定

27. 当输入的 $k$ 比 val[i] 的最大值还大时，该算法退化为（ ）算法。

{{ select(27) }}

• 选择排序
• 冒泡排序
• 计数排序
• 桶排序

第 3 题

假设输入的 $n$ 在 int 范围内，$k$ 为不小于 $2$ 且不大于 $36$ 的正整数，完成下面的判断题和单选题：

28. 该算法的时间复杂度为 $O(\log_k n)$。（ ）

{{ select(28) }}

• 正确
• 错误

29. 删除第 23 行的强制类型转换，程序的行为不变。（ ）

{{ select(29) }}

• 正确
• 错误

30. 除非输入的 $n$ 为 $0$，否则程序输出的字符数为 $O(\lfloor\log_k |n|\rfloor+1)$。（ ）

{{ select(30) }}

• 正确
• 错误

31. 当输入为 100 7 时，输出为（ ）。

{{ select(31) }}

• 202
• 1515
• 244
• 1754

32. 当输入为 -255 8 时，输出为（ ）。

{{ select(32) }}

• 1400
• 1401
• 417
• 400

33. 当输入为 1000000 19 时，输出为（ ）。

{{ select(33) }}

• BG939
• 87G1B
• 1CD428
• 7CF1B

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

第一题：归并第 $k$ 小

已知两个长度均为 $n$ 的有序数组 a1 和 a2（均为递增序，但不保证严格单调递增），并且给定正整数 $k$（$1\le k\le 2n$），求数组 a1 和 a2 归并排序后的数组里第 $k$ 小的数值。

试补全程序。

34. ① 处应填（ ）。

{{ select(34) }}

• (m1 + m2) * 2
• (m1 - 1) + (m2 - 1)
• m1 + m2
• (m1 + 1) + (m2 + 1)

35. ② 处应填（ ）。

{{ select(35) }}

• a1[m1] == a2[m2]
• a1[m1] <= a2[m2]
• a1[m1] >= a2[m2]
• a1[m1] != a2[m2]

36. ③ 处应填（ ）。

{{ select(36) }}

• left1 == right1
• left1 < right1
• left1 > right1
• left1 != right1

37. ④ 处应填（ ）。

{{ select(37) }}

• y = a1[k - left2 - 1]
• y = a1[k - left2]
• y = a2[k - left1 - 1]
• y = a2[k - left1]

38. ⑤ 处应填（ ）。

{{ select(38) }}

• y = a1[k - left2 - 1]
• y = a1[k - left2]
• y = a2[k - left1 - 1]
• y = a2[k - left1]

第二题：容器分水

有两个容器，容器 1 的容量为 $a$ 升，容器 2 的容量为 $b$ 升；同时允许下列三种操作：

1. FILL(i)：用水龙头将容器 $i$（$i\in\{1,2\}$）灌满水；
2. DROP(i)：将容器 $i$ 的水倒进下水道；
3. POUR(i,j)：将容器 $i$ 的水倒进容器 $j$（完成此操作后，要么容器 $j$ 被灌满，要么容器 $i$ 被清空）。

求只使用上述两个容器和三种操作，获得恰好 $c$ 升水的最少操作数和操作序列。$a$、$b$、$c$ 均为不超过 $100$ 的正整数，且 $c\le\max\{a,b\}$。

程序读入三个正整数 $a,b,c$。若无法获得恰好 $c$ 升水，输出 impossible；否则先输出最少操作数，再逐行输出操作序列。

试补全程序。

39. ① 处应填（ ）。

{{ select(39) }}

• dfs(x + t, y - t) + 1
• dfs(x + t, y - t) - 1
• dfs(x - t, y + t) + 1
• dfs(x - t, y + t) - 1

40. ② 处应填（ ）。

{{ select(40) }}

• dfs(x + t, y - t) + 1
• dfs(x + t, y - t) - 1
• dfs(x - t, y + t) + 1
• dfs(x - t, y + t) - 1

41. ③ 处应填（ ）。

{{ select(41) }}

• x == c || y == c
• x == c && y == c
• x >= c || y >= c
• x >= c && y >= c

42. ④ 处应填（ ）。

{{ select(42) }}

• dfs(x + t, y - t) + 1
• dfs(x + t, y - t) - 1
• dfs(x - t, y + t) + 1
• dfs(x - t, y + t) - 1

43. ⑤ 处应填（ ）。

{{ select(43) }}

• dfs(x + t, y - t) + 1
• dfs(x + t, y - t) - 1
• dfs(x - t, y + t) + 1
• dfs(x - t, y + t) - 1