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

第 1 题 下面关于 C++ 中形参、实参和定义域的说法中，正确的一项是 ( )

{{ select(1) }}

• 形参是函数定义时所指定的变量，它只在函数内部有效。
• 在函数内部，可以修改传入的形参的值，即使该形参是一个常量引用。
• 实参和形参的类型必须完全一致，否则会导致编译错误。
• 使用指针作为形参时，形参是指向实参的地址，因此对该指针赋值会影响实参。

第 2 题 已知三个序列: s1 = {3, 1, 8, 2, 5, 6, 7, 4}, s2 = {1, 5, 1, 8, 6, 4, 7, 5, 6},s3 = {1，8, 3, 5, 7, 6, 2, 4}。以下哪个序列是它们的最长公共子序列 ( )。

{{ select(2) }}

• {1,8,5,6}
• {1,5,6,7}
• {1, 8, 6}
• {1,5,7,4}

第 3 题 现有一个地址区间为 $0 \sim 10$ 的哈希表，当出现冲突情况，会往后找第一个空的地址存储(到 $10$ 冲突了就从 $0$ 开始往后)，现在要依次存储(1, 3, 5, 7, 9)，哈希函数为 $h(x)=(x^2+x)$ $mod$ $11$。其中 $9$ 存储在哈希表哪个地址中 ( )

{{ select(3) }}

• $1$
• $2$
• $3$
• $4$

第 4 题 在 0/1 背包问题中，给定一组物品，每个物品有一个重量和价值，背包的容量有限。假设背包的最大容量为$W$，物品的数量为 $n$，其中第个物品的重量为 $w[i]$ 问，价值为 $v[i]$。以下关于 0/1 背包问题的描述，正确的是 ( )。

{{ select(4) }}

• 在解决 0/1 背包问题时，使用贪心算法可以保证找到最优解，因为物品只能放入一次。
• 0/1 背包是 $P$ 问题(多项式时间可解问题)，它可以在 $O(nW)$ 的时间复杂度内解决。
• 01 背包问题中，动态规划解法的空间复杂度为 $O(nW)$，但可以通过滚动数组技巧将空间复杂度优化到 $O(W)$。
• 0/1 背包问题中，每个物品只能选择一次，并且子问题之间是独立的，无法重用计算结果。

第 5 题 一棵深度为 $6$(根节点深度为 $1$)的完全二叉树，节点总数最少有 ( )。

{{ select(5) }}

• $31$
• $32$
• $63$
• $64$

第 6 题 对于如下二叉树，下面关于访问的顺序说法错误的是 ( )。

{{ select(6) }}

• D E B F H J I G C A 是它的后序遍历序列。
• A B C D E F G H I J 是它的广度优先遍历序列。
• A B D E C F G H I J 是它的先序遍历序列。
• D B E A F C H G J I 是它的中序遍历序列。

第 7 题 下面程序的运行结果为 ( )。

01 #include <iostream>
02 
03 int query(int n, int *a, int x) {
04     int l = 0, r = n;
05     while (l < r) {
06         int mid = l + (r - l) / 2;
07         if (a[mid] >= x) r = mid;
08         else l = mid + 1;
09     }
10  
11     if (l == n) return -1;
12     return l;
13 }
14 
15 int main() {
16     int n = 10;
17     int x = 3;
18     int num[] = {1, 2, 2, 3, 3, 4, 5, 5, 6, 7};
19
20     std::cout << query(n, num, x) << "\n";
21     return 0;
22 }

{{ select(7) }}

• $2$
• $3$
• $4$
• $5$

第 8 题 下面程序中，函数 query 的时间复杂度是 ( )

01 #include <iostream>
02 
03 int query(int n, int *a, int x) {
04     int l = 0, r = n;
05     while (l < r) {
06         int mid = l + (r - l) / 2;
07         if (a[mid] >= x) r = mid;
08         else l = mid + 1;
09     }
10  
11     if (l == n) return -1;
12     return l;
13 }
14 
15 int main() {
16     int n = 10;
17     int x = 3;
18     int num[] = {1, 2, 2, 3, 3, 4, 5, 5, 6, 7};
19
20     std::cout << query(n, num, x) << "\n";
21     return 0;
22 }

{{ select(8) }}

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

第 9 题 有 $5$ 个字符，它们出现的次数分别为 $2$ 次、$2$ 次、$3$ 次、$3$ 次、$5$ 次。现在要用哈夫曼编码的方式来为这些字符进行编码，最小加权路径长度 $WPL$(每个字符的出现次数 $\times$ 它的编码长度，再把每个字符结果加起来)的值为 ( )。

{{ select(9) }}

• $30$
• $34$
• $43$
• $47$

第 10 题 下面程序的运行结果为 ( )

01 #include <iostream>
02 using namespace std;
03 int f(int n) {
04     if (n <= 2) return n * 2;
05     return f(n - 1) + f(n - 2);
06 }
07 int main() {
08     cout << f(5) << endl;
09     return 0;
10 }

{{ select(10) }}

• $10$
• $16$
• $26$
• $30$

第 11 题 一个简单无向图 $G$ 有 $36$ 条边，且每个顶点的度数都为 $4$，则图 $G$ 的顶点个数为 ( )。

{{ select(11) }}

• $9$
• $12$
• $18$
• $36$

第 12 题 下面关于二叉树的说法正确的是 ( )

{{ select(12) }}

• 任意二叉树的中序遍历与后序遍历必定不相同。
• 对任意二叉树，若已知先序遍历与后序遍历，则该二叉树唯一确定。
• 若二叉树有 $n$ 个结点，根节点高度为$1$，则其高度满足:$\lceil log_2(n+1) \rceil \leq h \leq n$。
• 在二叉树的先序遍历中，根后紧跟的结点一定是根的左孩子。

第 13 题 假设一个算法时间复杂度的递推式是 $T(n)=8T(\frac{n}{4})+n\sqrt n$ ($n$为正整数)，和$T(0) = 1$，那么这个算法的时间复杂度是 ( )。

{{ select(13) }}

• $O(n \sqrt n)$
• $O(n \sqrt n log n)$
• $O(n^2)$
• $O(n^2logn)$

第 14 题 下面哪一个可能是下图的深度优先遍历序列 ( )。

{{ select(14) }}

• 1,5,6,3,2,8,9,4,7
• 1,5,8,9,7,4,6,3,2
• 3,2,1,4,7,6,9,5,8
• 2,5,6,3,8,7,9,4,1

第 15 题 下面这个有向图的强连通分量的个数是 ( )。

{{ select(15) }}

• $3$
• $4$
• $5$
• $6$

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

第 1 题 C++ 语言中，表达式 3 ^ 2 的结果类型为 int，值为 9。

{{ select(16) }}

• 正确
• 错误

第 2 题 使用 cmath 头文件中的正弦函数，表达式 sin(90) 的结果类型为 double，值约为 1.0。

{{ select(17) }}

• 正确
• 错误

第 3 题 使用 strcmp("10"，"9") 比较两个字符串，返回值大于 $0$，说明 "10" 比 "9" 大。

{{ select(18) }}

• 正确
• 错误

第 4 题 选择排序是一种不稳定的排序算法，而冒泡排序是一种稳定的排序算法。

{{ select(19) }}

• 正确
• 错误

第 5 题 求两个长度为 $n$ 序列的最长公共子序列 $(LCS)$ 长度时，可以使用滚动数组将空间复杂度从 $O(n^2)$ 优化到 $O(n)$。

{{ select(20) }}

• 正确
• 错误

第 6 题 在无向图中，所有顶点的度数之和等于边数的两倍。

{{ select(21) }}

• 正确
• 错误

第 7 题 使用邻接矩阵存储一个有 $V$ 个顶点、$E$ 条边的图，对该图进行一次完整的 $BFS$ 遍历，时间复杂度为$O(V+E)$。

{{ select(22) }}

• 正确
• 错误

第 8 题 在图像处理或游戏开发中，泛洪 ($flood$ $filI$) 算法既可以用$BFS$ 实现，也可以用 $DFS$ 实现。

{{ select(23) }}

• 正确
• 错误

第 9 题 使用链地址法处理冲突的哈希表，当所有元素都映射到同一个槽位时，查找操作的最坏时间复杂度为 $O(n)$， 其中 $n$ 为元素个数。

{{ select(24) }}

• 正确
• 错误

第 10 题 一个包含 $V$ 个顶点的连通无向图，其任何一棵生成树都恰好包含 $V-1$ 条边。

{{ select(25) }}

• 正确
• 错误