一、单选题（共15题每题 2 分，共 30 分）

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

• pwd
• cd
• ls
• echo

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

{{ select(2) }}

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

在 C++ 中，以下哪个函数调用会造成栈溢出？（ ）

{{ select(3) }}

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

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

• 120
• 720
• 504
• 1000

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

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

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

{{ select(6) }}

• 4
• 5
• 6
• 7

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

{{ select(7) }}

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

对数组进行二分查找的过程中，以下哪个条件必须满足？

{{ select(8) }}

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

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

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

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

{{ select(10) }}

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

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

• $\ 2^{h}$-1
• $\ 2^{h+1}$-1
• $\ 2^{h}$
• $\ 2^{h+1}$

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

• 120
• 210
• 630
• 5040

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

{{ select(13) }}

• 29
• 199
• 299
• 399

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

{{ select(14) }}

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

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

{{ select(15) }}

• 1
• 2
• 3
• 4

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

第 1 题

判断题1

当 1000≥d≥b 时，输出的序列是有序的。 {{ select(16) }}

• 正确
• 错误

判断题2

当输入 5 5 1 时，输出为 1 1 5 5 5。

{{ select(17) }}

• 正确
• 错误

判断题3

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

• 正确
• 错误

选择题1

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

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

选择题2

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

• 91
• 94
• 95
• 98

本题共 11.5 分

第 2 题

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

{{ select(21) }}

• 正确
• 错误

22. 第 7 题 使用哈希函数 f(x) = x % p 建立键值为 int 类型的哈希表，只要 p 取小于等于哈希表大小的素数，可保证不发生碰撞。

{{ select(22) }}

• 正确
• 错误

{{ select(23) }}

• 正确
• 错误

第 9 题 判断图是否连通，可以通过广度优先搜索实现。

{{ select(24) }}

• 正确
• 错误

{{ select(25) }}

• 正确
• 错误