1. 在 Linux 系统中，如果你想显示当前工作目录的路径，应该使用哪个命令？（ ） {{ select(1) }}

• pwd
• cd
• ls
• echo

2.假设一个长度为n 的整数数组中每个元素值互不相同，且这个数组是无序的。要找到这个数组中最大元素的时间复杂度是多少？（ ） {{ select(2) }}

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

3.在 C++ 中，以下哪个函数调用会造成栈溢出？（ ） {{ select(3) }}

• int foo() { return 0; }
• int bar() { int x = 1; return x; }
• void baz() { int a[1000]; baz(); }
• void qux() { return; }

4.在一场比赛中，有10 名选手参加，前三名将获得金、银、铜牌。若不允许并列，且每名选手只能获得一枚奖牌，则不同的颁奖方式共有多少种？ {{ select(4) }}

• 120
• 720
• 504
• 1000

5.下面哪个数据结构最适合实现先进先出（FIFO）的功能？（ ） {{ select(5) }}

• 栈
• 队列
• 线性表
• 二叉搜索树

6. 已知f(1)=1，且对于n≥2 有f(n)=f(n−1)+f(⌊n/2⌋)，则 f(4) 的值为？ {{ select(6) }}

• 4
• 5
• 6
• 7

7.假设有一个包含 n 个顶点的无向图，且该图是欧拉图。以下关于该图的描述中哪一项不一定正确？ {{ select(7) }}

• 所有顶点的度数均为偶数
• 该图连通
• 该图存在一个欧拉回路
• 该图的边数是奇数

8.对数组进行二分查找的过程中，以下哪个条件必须满足？ {{ select(8) }}

• 数组必须是有序的
• 数组必须是无序的
• 数组长度必须是 2 的幂
• 数组中的元素必须是整数

9.考虑一个自然数n 以及一个模数m，你需要计算n 的逆元（即n 在模 m 意义下的乘法逆元）。下列哪种算法最为适合？（ ） {{ select(9) }}

• 使用暴力法依次尝试
• 使用扩展欧几里得算法
• 使用快速幂法
• 使用线性筛法

10.在设计一个哈希表时，为了减少冲突，需要使用适当的哈希函数和冲突解决策略。已知某哈希表中有 n 个键值对，表的装载因子为α(0<α≤1)。在使用开放地址法解决冲突的过程中，最坏情况下查找一个元素的时间复杂度为（ ）？ {{ select(10) }}

• O(1)
• O(logn)
• O(1/(1−α))
• O(n)

11. 假设有一棵 h 层的完全二叉树，该树最多包含多少个结点？ {{ select(11) }}

• $2^h−1$
• $2^{h+1}−1$
• $2^h$
• $2^{h+1}$

12.设有一个10 个顶点的完全图，每两个顶点之间都有一条边。有多少个长度为4 的环？ {{ select(12) }}

• 120
• 210
• 630
• 5040

13.对于一个整数 n，定义f(n) 为 n 的各位数字之和，问使 f(f(x))=10 的最小自然数 x 是多少？ {{ select(13) }}

• 29
• 199
• 299
• 399

14.设有一个长度为n 的01 字符串，其中有k 个 1。每次操作可以交换相邻两个字符。在最坏情况下将这 k 个 1 移到字符串最右边所需要的交换次数是多少？ {{ select(14) }}

• k
• k*(k−1)/2
• (n−k)*k
• (2n−k−1)*k/2

15.如图是一张包含7 个顶点的有向图，如果要删除其中一些边，使得从节点1 到节点7 没有可行路径，且删除的边数最少，请问总共有多少种可行的删除边的集合？（ ）

{{ select(15) }}

• 1
• 2
• 3
• 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]