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

• 25
• 30
• 6
• 120

2.在 KMP 算法中，对于模式串P=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(key)=keymod13。依次插入关键字18,26,35,9,68,74。插入74 后，它最终被放置在哪个索引位置？ {{ select(6) }}

• 5
• 7
• 9
• 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
• 2,4,5,6,8,10,12
• 12,8,10,5,2,4,6

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^2$) 描述了某个分治算法的时间复杂度。请问该算法的时间复杂度是多少？ {{ select(11) }}

• O(n)
• O(nlogn)
• O($n^2$)
• O($n^2logn$)

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
• 334

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

第 1 题

16.(1 分) 当输入的n=3 的时候，程序输出的答案为 3。 {{ select(16) }}

• 正确
• 错误

17.在 dfs 函数运行过程中，k 的取值会满足1≤k≤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

第 2 题

注意：下述的“猜测数”为调用 check 函数的次数（即cnt_check 的值）；“猜测正确”的含义为 assert_ans 函数 return true（执行第 25 行所在分支）的情况；所有输入保证1≤k≤n）。

22.当输入为 "6 5 1" 时，猜测次数为 5；当输入为 "6 5 2" 时，猜测次数为 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
• B. 1
• c. 2
• D. n

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

• O(n)
• O($n^2$)
• O( $sqrt(n)$）
• O(logn)

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

• 100,14
• 100,13
• 99,14
• 99,13

第 3 题

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.当输入为 3 15 1 2 -1 2 1 2 时，输出结果为（ ） {{ select(31) }}

• 4
• 8
• 0
• 10

32.记程序结束前p 数组元素的最大值为P，则该代码的时间复杂度是（ ）。 {{ select(32) }}

• O(n)
• O($m^nlogm^n)$
• O($m ^{n/2}logm^{n/2})$
• O($m ^{n/2}(logm^{n/2}+logP))$

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

• 满足$a,b,c∈[1,m]$ 的整数方程$a^3+b^3=c^3$的解的数量

• 满足$a,b,c∈[1,m]$ 的整数方程$a^2+b^2=c^2$的解的数量

• 

• 

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

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

34.①处应填 ( ) {{ select(34) }}

• 0
• 1
• -1
• false

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

• d[u][!used]
• d[u][used]
• d[t][used]
• INF

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

• d[v][1]
• d[v][used]
• d[u][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]

(2)工厂打算通过客户反馈来间接测试生产线，从而找到存在缺陷的生产线。工厂有n 条生产线（编号0∼n−1），已知其中恰有一条生产线存在缺陷。每一轮测试为，从若干生产线的产品取样混合成一个批次发给客户。若该批次中包含缺陷生产线的产品，客户将要求退货（结果记为 1），否则正常收货（记为 0）。受售后压力限制，在所有发货批次中，最多只能有 k 次退货（即结果为 1 的次数 ≤k）。工厂的目标是，设计最少的间接测试轮数 w（发货总批次），保证根据客户收货或退货的反馈结果，唯一确定存在缺陷的生产线。

以下程序实现了工厂的目标，包含两部分：i) 确定 w 的最小值，并设计最优测试方案；ii) 根据测试结果推断存在缺陷的生产线。该程序确定w 最小值的方法为：由于不同的生产线故障时，测试应当返回不同的结果，因此w 轮测试的可能结果总数不应少于生产线数量。

test_subset() 函数为抽象测试接口，输入所有批次的方案并返回一个二进制编码；该编码表示为每批次的检测结果（即最低位是第 1 批次、最高位是第w 批次）；其实现在此处未给出。

试补全程序。

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

• (1 << w) < n
• count_patterns(w, k) < n
• count_patterns(k, w) < n
• 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 >> i) & 1
• (i >> 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[j] == sig_bits
• plan[j] == sig_bits
• code[j][i] == sig_bits[i]