1. 在 Linux 系统终端中，以下哪个命令用于创建一个新的目录？ {{ select(1) }}

• newdir
• mkdir
• create
• mkfold

2. 0,1,2,3,4 中选取4 个数字，能组成（）个不同四位数（注：最小的四位数是1000 最大的四位数是9999）。 {{ select(2) }}

• 96
• 18
• 120
• 84

3.假设 n 是图的顶点的个数，m 是图的边的个数，为求解某一问题有下面四种不同时间复杂度的算法。对于m=Θ(n) 的稀疏图而言，下面的四个选项，哪一项的渐近时间复杂度最小（）。 {{ select(3) }}

• 
• 
• 
• 

4.假设有n 根柱子，需要按照以下规则依次放置编号为1,2,3,⋯ 的圆环：每根柱子的底 部固定，顶部可以放入圆环；每次从柱子顶部放入圆环时，需要保证任何两个相邻圆环的编号之和是一个完全平方数。请计算当有4 根柱子时，最多可以放置（）个圆环。 {{ select(4) }}

• 7
• 9
• 11
• 5

5.以下对数据结构的表述不恰当的一项是： {{ select(5) }}

• 队列是一种先进先出（FIFO）的线性结构
• 哈夫曼树的构造过程主要是为了实现图的深度优先搜索
• 散列表是一种通过散列函数将关键字映射到存储位置的数据结构
• 二叉树是一种每个结点最多有两个子结点的树结构

6. 以下连通无向图中，（）一定可以用不超过两种颜色进行染色 {{ select(6) }}

• 完全三叉树
• 平面图
• 边双连通图
• 欧拉图

{{ select(7) }}

• 4
• 5
• 6
• 7

{{ select(8) }}

• 7 元
• 35/6元
• 16/3元
• 19/3元

{{ select(9) }}

• true
• false
• 1
• 0

10.假设快速排序算法的输入是一个长度为n 的已排序数组，且该快速排序算法在分治过程总是选择第一个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为? {{ select(10) }}

• 快速排序对于此类输入的表现最好，因为数组已经排序。
• 快速排序对于此类输入的时间复杂度是Θ(nlogn)。
• 快速排序对于此类输入的时间复杂度是$Θ(n^2)$。
• 快速排序无法对此类数组进行排序，因为数组已经排序。

11. 以下哪个命令，能将一个名为 main.cpp 的 C++ 源文件，编译并生成一个名为 main 的可执行文件？（） {{ select(11) }}

• g++ -o main main.cpp
• g++ -o main.cpp main
• g++ main -o main.cpp
• g++ main.cpp -o main.cpp

12.在图论中，树的重心是树上的一个结点，以该结点为根时，使得其所有的子树中结点数最多的子树的结点数最少。一棵树可能有多个重心。请问下面哪种树一定只有一个重心？ {{ select(12) }}

• 4 个结点的树
• 6 个结点的树
• 7 个结点的树
• 8 个结点的树

13.如图是一张包含6 个顶点的有向图，但顶点间不存在拓扑序。如果要删除其中一条边，使这6 个顶点能进行拓扑排序，请问总共有多少条边可以作为候选的被删除边？（）

{{ select(13) }}

• 1
• 2
• 3
• 4

{{ select(14) }}

• 10
• 11
• 12
• 13

{{ select(15) }}

• O(n)
• O(1)
• O(logn)
• O(nlogn)

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ⨉ ；除特殊说明外，判断题 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]