一、单项选择题

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

【第 1 题】

有 $5$ 个红球和 $5$ 个蓝球，它们除了颜色之外完全相同。将这 $10$ 个球排成一排，要求任意两个蓝色球都不能相邻，有多少种不同的排列方法？

{{ select(1) }}

• $25$
• $30$
• $6$
• $120$

【第 2 题】

在 $KMP$ 算法中，对于模式串 $P=\text{"abacaba"}$，其 $next$ 数组（$next[i]$ 定义为模式串 $P[0..i]$ 最长公共前后缀的长度，且数组下标从 $0$ 开始）的值是什么？

{{ select(2) }}

• $\{0,0,1,0,1,2,3\}$
• $\{0,1,2,3,4,5,6\}$
• $\{0,0,1,1,2,2,3\}$
• $\{0,0,0,0,1,2,3\}$

【第 3 题】

对一个大小为 $16$（下标 $0$–$15$）的数组构建线段树，查询区间 $[3,\,11]$ 时，最少需要访问多少个树结点（包括路径上的父结点和完全包含在查询区间内的结点）？

{{ select(3) }}

• 7
• 8
• 9
• 10

【第 4 题】

将字符串 “cat”、“car”、“cart”、“case”、“dog”、“do” 插入一个空的 Trie 树（前缀树）中，构建完成 Trie 树（包括根节点）共有多少个结点？

{{ select(4) }}

• 8
• 9
• 10
• 11

【第 5 题】

对于一个包含 $n$ 个结点和 $m$ 条边的有向无环图（$DAG$），其拓扑排序的结果有多少种可能？

{{ select(5) }}

• 只有 $1$ 种
• 最多 $n$ 种
• 等于 $n-m$ 种
• 以上都不对

【第 6 题】

在一个大小为 $13$ 的哈希表中，使用闭散列法的线性探查来解决冲突。哈希函数为 $H(\text{key})=\text{key}\bmod 13$。依次插入关键字 $18,\,26,\,35,\,9,\,68,\,74$，插入 $74$ 后，它最终被放置在哪个索引位置？

{{ select(6) }}

• 5
• 7
• 8
• 11

【第 7 题】

一个包含 $8$ 个顶点的完全图（顶点的编号为 $1$ 到 $8$），在每两个点之间的边权重等于两顶点编号的绝对值。例如，顶点 $3$ 和 $7$ 之间的边权重为 $|7-3|=4$。该图的最小生成树的权重是多少？

{{ select(7) }}

• 7
• 8
• 9
• 10

【第 8 题】

如果一棵二叉搜索树的后序遍历序列是 $2,\,5,\,4,\,8,\,12,\,10,\,6$，那么该树的前序遍历是什么？

{{ select(8) }}

• $6,\,4,\,2,\,5,\,10,\,8,\,12$
• $6,\,4,\,5,\,2,\,10,\,12,\,8$
• $6,\,2,\,4,\,5,\,8,\,10,\,12$
• $6,\,2,\,5,\,4,\,10,\,8,\,12$

【第 9 题】

一个 $0$-$1$ 背包问题，背包容量为 $20$。现有 $5$ 个物品，重量和价值分别为 $7,\,5,\,4,\,3,\,6$ 和 $15,\,12,\,9,\,7,\,13$。装入背包的物品能获得的最大总价值是多少？

{{ select(9) }}

• 43
• 41
• 45
• 44

【第 10 题】

在一棵以结点 $1$ 为根的树中，结点 $12$ 和结点 $18$ 的最近公共祖先（$LCA$）是结点 $4$。那么下列哪个结点的 $LCA$ 组合是不可出现的？

{{ select(10) }}

• $LCA(12,\,4)=4$
• $LCA(18,\,4)=4$
• $LCA(12,\,18,\,4)=4$
• $LCA(12,\,1)=4$

【第 11 题】

递归关系式 $T(n)=2T(n/2)+O(n^{i})$ 描述了某个分治算法的时间复杂度。请问该算法的时间复杂度是多少？

{{ select(11) }}

• $O(n)$
• $O(n\log n)$
• $O(n^{i})$
• $O(n^{i}\log n)$

【第 12 题】

在一个初始为空的最小堆（min-heap）中，依次插入元素 $20,\,12,\,15,\,8,\,10,\,5$。然后连续执行两次“删除最小值（delete-min）”操作。请问此时堆顶元素是什么？

{{ select(12) }}

• 10
• 12
• 15
• 20

【第 13 题】

$1$ 到 $1000$ 之间，不能被 $2$、$3$、$5$ 中任意一个整除的整数有多少个？

{{ select(13) }}

• 266
• 267
• 333
• 734​

【第 14 题】

斐波那契数列的定义为 $F(0)=0,\ F(1)=1,\ F(n)=F(n-1)+F(n-2)$。使用朴素递归方法计算 $F(n)$ 的时间复杂度是指数级的，而使用动态规划（或迭代）方法的时间复杂度是线性的。造成这两种巨大差异的根本原因是？

{{ select(14) }}

• 递归函数调用开销过大
• 操作系统对递归深度有限制
• 朴素递归中存在大量的重复子问题未被重复利用
• 动态规划使用了更多的栈或寄存器/存储空间

【第 15 题】

有 $5$ 个独立、不可抢占的任务 $A_1, A_2, A_3, A_4, A_5$ 需要在一台计算机上执行（从时间 $0$ 开始执行），每个任务都有对应的处理时长和截止时刻，按顺序分别为 $3,\,4,\,2,\,5,\,1$ 和 $5,\,10,\,3,\,15,\,11$。如果某一个任务超时，相应的惩罚等于其处理时长。为了最小化总惩罚，应该优先执行哪个任务？

{{ select(15) }}

• 处理时间最短的任务 $A_5$
• 截止时间最早的任务 $A_3$
• 处理时间最长的任务 $A_4$
• 任选一个任务都可以

二、阅读程序

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

阅读程序（一）

判断题

16. （1 分）当输入的 $n=3$ 的时候，程序输出的答案为 $3$。

    {{ select(16) }}

• 正确
• 错误

17. 在 dfs 函数运行过程中，$k$ 的取值会满足 $1\le k\le n+1$。

    {{ select(17) }}

• 正确
• 错误

18. 删除第 $19$ 行的 “flag[i]=false;”，对答案不会产生影响。

    {{ select(18) }}

• 正确
• 错误

单选题

19. 当输入的 $n=4$ 的时候，程序输出的答案为（ ）。 {{ select(19) }}

• 11
• 12
• 24
• 9

20. 如果因为某些问题，导致程序运行到第 $25$ 行的 $dfs$ 函数之前，数组 $p$ 的初值并不全为 $0$，则对程序的影响是（ ）。

    {{ select(20) }}

• 输出的答案比原答案更小
• 无法确定能输出的答案
• 程序可能陷入死循环
• 没有影响

21. 假如删去第 $14$ 行的 “if(flag[i]) continue;”，输入 $3$，得到的输出答案是（ ）。 {{ select(21) }}

• 27
• 3
• 16
• 12

阅读程序（二）

（注意：下述的“猜测次数”为调用 $check$ 函数的次数（即 $cnt\_check$ 的值）；“猜测正确”的含义为 $assert\_ans$ 函数 $return\ true$（执行第 $25$ 行 $if$ 语句）的时候。所有输入满足 $1\le k\le n$。）

判断题

22. 当输入为 “$651$” 时，猜测次数为 $5$；当输入 “$652$” 时，猜测次数为 $3$。 {{ select(22) }}

• 正确
• 错误

23. 不管输入的 $n$ 和 $k$ 具体为多少，$t=2$ 时的猜测次数总是小于等于 $t=1$ 时的猜测次数。 {{ select(23) }}

• 正确
• 错误

24. 不管 $t=1$ 或 $t=2$，程序都一定会得出正确答案。 {{ select(24) }}

• 正确
• 错误

单选题

25. 虽然 $guess1$ 在运行过程中，$cnt\_broken$ 的值最多为（ ）。 {{ select(25) }}

• 0
• 1
• 2
• n

26. 函数 $guess2$ 在运行过程中，最多使用的猜测次数的量级为（ ）。

    {{ select(26) }}

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

27. 当输入的 $n=100$ 的时候，代码中 $t=1$ 和 $t=2$ 分别需要的猜测次数最少分别为（ ）。

    {{ select(27) }}

• $100,\,14$
• $100,\,13$
• $99,\,14$
• $99,\,13$

阅读程序（三）

判断题

28. 删除第 $51$ 行的 “std::sort(ans2.begin(), ans2.end());” 后，代码输出的结果不会受到影响。

    {{ select(28) }}

• 正确
• 错误

29. 假设计算过程中不发生溢出，函数 $mpow(x,k)$ 的功能是求出 $x^k$ 的取值。 {{ select(29) }}

• 正确
• 错误

30. 代码中第 $39$ 行到第 $50$ 行的目的是为了将 $ans1$ 数组进行“去重”操作。 {{ select(30) }}

• 正确
• 错误

单选题

31. 如果输入x = 3 和 y = 3，则程序的最终输出为（ ）。 {{ select(31) }}

• 27
• 81
• 144
• 256

32. （当输入为 “$3\ 15\ 1\ 2\ -1\ 2\ 1\ 2$” 时，输出结果为（ ）

    {{ select(32) }}

• 4
• 8
• 0
• 10

33. 本题所求出的是（ ）。 {{ select(33) }}

• 满足 $a,b,c\in[1,m]$ 的整数方程 $a^3+b^3=c^3$ 的解的数量
• 满足 $a,b,c\in[1,m]$ 的整数方程 $a^2+b^2=c^2$ 的解的数量
• 满足 $x_i\in[0,m]$ 的整数方程 $\sum_{i=1}^n k_i\cdot x_i^{\,p}=0$ 的解的数量
• 满足 $x_i\in[1,m]$ 的整数方程 $\sum_{i=1}^n k_i\cdot x_i^{\,p}=0$ 的解的数量

三、程序填空

（单选题，每小题 3 分，共计 30 分）

程序填空(一)

（特殊最短路）给定一个含 $N$ 个点、$M$ 条边的带权无向图，边权非负。起点为 $S$，终点为 $T$；对于一条从 $S$ 到 $T$ 的路径，可以在整条路径中至多选择一条边作为“免费边”。当第一次经过这条被选中的边时，费用视为 $0$；如果之后再次经过该边，则仍按其原有权值计算。点和边均允许重复经过。求从 $S$ 到 $T$ 的最小总费用。

以下代码求解了上述问题，试补全程序。

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

• $0$
• $1$
• $-1$
• $false$

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

• $d[u][\lnot used]$
• $d[u][used]$
• $d[t][used]$
• $INF$

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

• $d[v][1]$
• $d[v][\text{used}]$
• $d[u][\text{used}]$
• $d[v][0]$

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

• $d[v][0]$
• $d[v][1]$
• $d[u][0]$
• $d[u][1]$

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

• $d[t][1]$
• $d[t][0]$
• $\min(d[t][0],\ d[t][1])$
• $d[t][0]+d[t][1]$

完善程序(二)

（特殊测试）给定一个工厂共有 $n$ 条生产线（编号 $0\sim n-1$）。工厂希望借助客户的“投诉/不投诉”反馈来定位存在缺陷的生产线。一次测试的方式为：从若干条生产线取样并混合成一批产品投放市场；若本批样品中包含来自缺陷生产线的产品，则该批会被判定为“有问题”（记作有投诉），否则记作“无投诉”。每条生产线产能相同。为了控制对客户的打扰与成本，允许的测试总次数记为 $w$（需要使其尽量小）。要求在不超过 $w$ 次测试的前提下，能唯一确定哪一条生产线存在缺陷。

下面给出一段需要补全的程序，目标包括两部分：

1. 确定最小的 $w$，并设计对应的最优测试方案；
2. 根据每次测试得到的投诉/不投诉的结果，最终确定唯一的有缺陷生产线。

test_subset() 为评测系统提供的黑箱接口，输入为一个二进制掩码，表示本次测试所选择的生产线集合；返回值表示该批测试的结果（有投诉 / 无投诉）。该函数最多会被调用 $w$ 次。请在保证能够唯一确定缺陷生产线的前提下，使 $w$ 尽可能小，并补全完整程序。

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

• $(1 \ll w) < n$
• $\text{count\_patterns}(w,\,k) < n$
• $\text{count\_patterns}(k,\,w) < n$
• $\text{comb}(w,\,k) < n$

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

• $next\_permutation(bits.begin(),\ bits.end())$
• $prev\_permutation(bits.begin(),\ bits.end())$
• $next\_permutation(bits.begin(),\ bits.begin()+ones)$
• $prev\_permutation(bits.begin(),\ bits.begin()+ones)$

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

• $(j \gg i)\ \&\ 1$
• $(i \gg j)\ \&\ 1$
• $code[i][j] == 1$
• $code[j][i] == 1$

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

• (signature >> i) & 1
• (signature >> i) ^ 1
• signature | (1 << i)
• (signature >> i) | 1

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

• is_permutation(code[j].begin(), code[j].end(), sig_bits.begin())
• code[i] == sig_bits
• plan[j] == sig_bits
• code[j][i] == sig_bits[i]