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.当1000≥d≥b 时，输出的序列是有序的。（ ） {{ select(16) }}

• 正确
• 错误

17.当输入 5 5 1 时，输出为 1 1 5 5 5。（ ） {{ select(17) }}

• 正确
• 错误

18.假设数组 c 长度无限制，该程序所实现的算法的时间复杂度是 O(b) 的。（ ） {{ select(18) }}

• 正确
• 错误

19.函数 int logic(int x, int y) 的功能是（ ） {{ select(19) }}

• 按位与
• 按位或
• 按位异或
• 以上都不是

20. 当输入为 10 100 100 时，输出的第100 个数是？（ ） {{ select(20) }}

• 91
• 94
• 95
• 98

第 2 题

假设输入的s 是包含 n 个字符的01 串，完成下面的判断题和单选题。

21.假设数组 dp 长度无限制，函数 solve( ) 所实现的算法的时间复杂度是O(n×$2^m$)。 {{ select(21) }}

• 正确
• 错误

22.输入 11 2 10000000001 时，程序输出两个数 32 和 23。 {{ select(22) }}

• 正确
• 错误

23.（2 分）在n≤10 时，solve( ) 的返回值始终小于$4^{10}$ 。 {{ select(23) }}

• 正确
• 错误

24.当n=10 且m=10 时，有多少种输入使得两行的结果完全一致？（ ） {{ select(24) }}

• 1024
• 11
• 10
• 0

25.当n≤6 时，solve() 的最大可能返回值为（ ）？ {{ select(25) }}

• 65
• 211
• 665
• 2059

26.若n=8,m=8，solve 和 solve2 的返回值的最大可能的差值为（ ）？ {{ select(26) }}

• 1477
• 1995
• 2059
• 2187

第 3 题

27.假设程序运行前能自动将 maxn 改为 n+1，所实现的算法的时间复杂度是O(nlogn)。（ ） {{ select(27) }}

• 正确
• 错误

28.时间开销的瓶颈是 init() 函数。 {{ select(28) }}

• 正确
• 错误

29.若修改常数 B1 或 K1 的值，该程序可能会输出不同的结果。 {{ select(29) }}

• 正确
• 错误

30.在 solve() 函数中，h[] 的合并顺序可以看作是（ ）？ {{ select(30) }}

• 二叉树的 BFS 序
• 二叉树的先序遍历
• 二叉树的中序遍历
• 二叉树的后序遍历

31.输入10，输出的第一行是？（ ） {{ select(31) }}

• 83
• 424
• 54
• 110101000

32.输入16，输出的第二行是？（ ） {{ select(32) }}

• 7
• 9
• 10
• 12

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

(1)（序列合并） 有两个长度为 N 的单调不降序列 A 和 B，序列的每个元素都是小于$10^9$的非负整数。在 A 和B 中各取一个数相加可以得到$N^2$个和，求其中第 K 小的和。上述参数满足$N≤10^5$和$1≤K≤N^2$。

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

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

• an-a
• an-a-1
• ai
• ai+1

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

• a[mid] > ai
• a[mid] >= ai
• a[mid] < ai
• a[mid] <= ai

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

• a+l
• a+l+1
• a+l-1
• an-l

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

• a[n-1]+b[n-1]
• a[n]+b[n]
• 2 * maxn
• maxn

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

• get_rank(mid) < k
• get_rank(mid) <= k
• get_rank(mid) > k
• get_rank(mid) >= k

(2)（次短路） 已知一个有n 个点 m 条边的有向图 G，并且给定图中的两个点s 和 t，求次短路（长度严格大于最短路的最短路径）。如果不存在，输出一行−1。如果存在，输出两行，第一行表示次短路的长度，第二行表示次短路的一个方案。

试补全程序。

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

• upd(pre[b], n+b, dis[b], q)
• upd(a, n+b, d, q)
• upd(pre[b], b, dis[b], q)
• upd(a, b, d, q)

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

• make_pair(-d, b)
• make_pair(d, b)
• make_pair(b, d)
• make_pair(-b, d)

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

• 0xff
• 0x1f
• 0x3f
• 0x7f

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

• upd(a, n+b, dis[a]+c, q)
• upd(n+a, n+b, dis2[a]+c, q)
• upd(n+a, b, dis2[a]+c, q)
• upd(a, b, dis[a]+c, q)

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

• pre2[a%n]
• pre[a%n]
• pre2[a]
• pre[a%n]+1