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

第 1 题 下列C++代码的输出结果是（）。

1 #include <iostream>
2 using namespace std;
3 int main() {
4	 int a = 5 , b = 3;
5	 cout << (a & b) + (a | b) << endl;
6	 return 0;
7 }

{{ select(1) }}

• 6
• 7
• 8
• 9

第 2 题 使用 cmath 或 math.h 中的数学库函数，下列说法中正确的是（）。

{{ select(2) }}

• pow(2, 3) 的返回值类型为int
• sin(30) 的参数 30 表示 30 度
• sqrt(4) 的返回值类型为int
• log(1) 的返回值为 0.0，且类型为 double

第 3 题 有 4 个字符，出现次数分别为1、2、3、4。构造哈夫曼树后，出现次数为 1 的字符的哈夫曼编码长度为（）。

{{ select(3) }}

• 1
• 2
• 3
• 4

第 4 题 从 $4 \times 5$ 个点连接成的网格的左上角走到右下角，每次只能向右或向下移动，不同的路径共有（）条。

{{ select(4) }}

• 20
• 35
• 70
• 126

第 5 题 在含有 $n$ 个结点的二叉排序树中查找一个元素，平均时间复杂度和最坏时间复杂度分别为（）。

{{ select(5) }}

• $O(logn)、O(n)$
• $O(n)、O(logn)$
• $O(logn)、O(logn)$
• $O(1)、O(n)$

第 6 题 有 4 堆石子，数量分别为1、2、3、4。每次可以合并相邻两堆，合并代价为两堆石子数之和。将所有石子合并成一堆的最小总代价为（）

{{ select(6) }}

• 17
• 19
• 20
• 23

第 7 题 在无权图中，使用 BFS 从起点开始遍历，并在访问由结点 u 扩展的相邻结点 v 时记录 dist[v] = dist[u] + 1，且起点的 dist 为 0，则最终 dist[v] 表示的是（）。

{{ select(7) }}

• 起点到结点 v 的最少边数
• 结点 v 的度数
• 从起点到结点 v 的路径上经过的最大边权
• 包含结点 v 的连通块大小

第 8 题 在二维网格上实现泛洪填充时，为了防止递归层数过深，最适合的非递归实现方式是（）。

{{ select(8) }}

• 使用哈希表记录每个格子被访问的次数
• 使用快速排序预处理网格
• 使用二分查找定位边界
• 使用队列实现 BFS 或使用显式栈模拟 DFS

第 9 题 关于哈希表，下列说法正确的是（）。

{{ select(9) }}

• 只要哈希函数选择合适，就可以完全避免冲突
• 在链地址法中，查找一个元素的时间复杂度一定为 $O(1)$
• 开放定址法发生冲突后，会在表内寻找下一个可用位置
• 哈希表的查找速度与表中元素个数无关

第 10 题 下列C++代码的输出结果是（）。

1 #include <iostream>
2 using namespace std;
3
4 void inc(int &x) {
5	 x++;
6 }
7 int main() {
8 	int a = 3;
9	 inc(a);
10	 cout << a;
11	 return 0;
12 }

{{ select(10) }}

• 3
• 4
• 5
• 编译错误

第 11 题 用动态规划求两个序列 $s_1$ 和 $s_2$ 的最长公共子序列长度，若 dp[i][j] 表示前 i 个元素与前 j 个元素的 LCS 长度。当 $s_1[i-1] = s_2[j-1]$ 时，正确的状态转移是（）。

{{ select(11) }}

• dp[i][j] = dp[i - 1][j - 1] + 1
• dp[i][j] = max (dp[i - 1][j], dp[i][j - 1])
• dp[i][j] = dp[i - 1][j] + 1
• dp[i][j] = dp[i][j - 1]

第 12 题 下列代码是一维数组优化 0/1 背包的核心片段，执行后 dp[8] 的输出结果是（）。

1 #include <iostream>
2 #include <algorithm>
3 using namespace std;
4 int main() {
5	 int w = 3, v = 5, W = 8;
6	 int dp [9] = {0};
7	 for (int c = W; c >= w; c--)
8		 dp[c] = max (dp[c], dp[c - w] + v);
9	 cout << dp[8] << endl;
10	 return 0 ;
11 }

{{ select(12) }}

• 0
• 1
• 3
• 5

第 13 题 若要求排序后相等元素的相对顺序保持不变，下列排序算法中最不适宜使用的是（）。

{{ select(13) }}

• 冒泡排序
• 插入排序
• 归并排序
• 快速排序

第 14 题 下列代码片段的时间复杂度为（）。

1 long long s = 0;
2 for (int i = 1; i <= n; i++)
3	 for (int j = 1; j <= n; j += i)
4		 s += i + j;

{{ select(14) }}

• $O(n)$
• $O(nlogn)$
• $O(n^2)$
• $O(n \sqrt(n))$

第 15 题 已知 int a[6] = {1, 3, 5, 7, 9, 11}; int* p = a + 1; 则表达式 *(p + 3) 的值是（）。

{{ select(15) }}

• 5
• 7
• 9
• 11

二、判断题（每题 2 分，共 20 分）

第 16 题 使用 cmath 或 math.h 中的函数，表达式 exp(0) 的结果值为 1.0，且类型为double。

{{ select(16) }}

• 正确
• 错误

第 17 题 采用开放定址法处理冲突的哈希表中，删除一个元素后可以直接将该位置置空，不会影响后续查找。

{{ select(17) }}

• 正确
• 错误

第 18 题 在哈夫曼树中，出现次数更多的叶子结点，其深度总是更小。

{{ select(18) }}

• 正确
• 错误

第 19 题 在一个有向图中，所有顶点的入度之和总是等于所有顶点的出度之和。

{{ select(19) }}

• 正确
• 错误

第 20 题 广度优先搜索通常借助队列实现，深度优先搜索通常借助栈或递归实现。

{{ select(20) }}

• 正确
• 错误

第 21 题 快速排序的平均时间复杂度为 $O(nlogn)$，最坏时间复杂度也为 $O(nlogn)$。

{{ select(21) }}

• 正确
• 错误

第 22 题 为解决 0/1 背包问题，使用一维数组优化时，内层容量循环应从大到小枚举。

{{ select(22) }}

• 正确
• 错误

第 23 题 使用邻接表存储图时，遍历某个顶点的所有邻边所需时间与图中顶点数成正比。

{{ select(23) }}

• 正确
• 错误

第 24 题 在按层序从 $1$ 开始对结点编号的完全二叉树中，编号为 $i \ (i>1)$ 的结点的父结点编号为 $\lfloor {i/2} \rfloor$ 。

{{ select(24) }}

• 正确
• 错误

第 25 题 在定义了数组 int arr[10]; 后，表达式 arr 和表达式 &arr[0] 总是等价的。

{{ select(25) }}

• 正确
• 错误