GESP 202512 C++ 七级

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

1. [2 分] 下面关于 C++ 中形参、实参和定义域的说法中，正确的一项是（ ）。 （ {{ select(1) }} ）

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

2. [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) }} ）

• A. $\{1, 8, 5, 6\}$
• B. $\{1, 5, 6, 7\}$
• C. $\{1, 8, 6\}$
• D. $\{1, 5, 7, 4\}$

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

• 1
• 2
• 3
• 4

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

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

5. [2 分] 一棵深度为 6（根节点深度为 1）的完全二叉树，节点总数最少有（ ）。 （ {{ select(5) }} ）

• 31
• 32
• 63
• 64

6. [2 分] 对于如下二叉树，下面关于访问的顺序说法错误的是（ ）。 （ {{ select(6) }} ）

• A. DEBFHJIGCA 是它的后序遍历序列。
• B. ABCDEFGHIJ 是它的广度优先遍历序列。
• C. ABDECFGHIJ 是它的先序遍历序列。
• D. DBEAFCGHJI 是它的中序遍历序列。

7. [2 分] 下面程序的运行结果为（ ）。

// ... (binary search code finding lower bound)
// Array: {1, 2, 2, 3, 3, 4, 5, 5, 6, 7}, n=10, x=3

（ {{ select(7) }} ）

• 2
• 3
• 4
• 5

8. [2 分] 下面程序中，函数 query 的时间复杂度是（ ）。 （ {{ select(8) }} ）

• $O(1)$
• $O(\log n)$
• $O(n)$
• $O(n \log n)$

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

• 30
• 34
• 43
• 47

10. [2 分] 下面程序的运行结果为（ ）。

int f(int n) {
    if (n <= 2) return n * 2;
    return f(n - 1) + f(n - 2);
}
// ... f(5)

（ {{ select(10) }} ）

• 10
• 16
• 26
• 30

11. [2 分] 一个简单无向图 $G$ 有 36 条边，且每个顶点的度数都为 4，则图 $G$ 的顶点个数为（ ）。 （ {{ select(11) }} ）

• 9
• 12
• 18
• 36

12. [2 分] 下面关于二叉树的说法正确的是（ ）。 （ {{ select(12) }} ）

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

13. [2 分] 假设一个算法时间复杂度的递推式是 $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^2 \log n)$

14. [2 分] 下面哪一个可能是下图的深度优先遍历序列（ ）。 （ {{ select(14) }} ）

• A. 1, 5, 6, 3, 2, 8, 9, 4, 7
• B. 1, 5, 8, 9, 7, 4, 6, 3, 2
• C. 3, 2, 1, 4, 7, 6, 9, 5, 8
• D. 2, 5, 6, 3, 8, 7, 9, 4, 1

15. [2 分] 下面这个有向图的强连通分量的个数是（ ）。 （ {{ select(15) }} ）

• 3
• 4
• 5
• 6

---

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

16. [2 分] C++ 语言中，表达式 3 ^ 2 的结果类型为 int，值为 9。 （ {{ select(16) }} ）

• 正确
• 错误

17. [2 分] 使用 cmath 头文件中的正弦函数，表达式 sin(90) 的结果类型为 double，值约为 1.0。 （ {{ select(17) }} ）

• 正确
• 错误

18. [2 分] 使用 strcmp("10", "9") 比较两个字符串，返回值大于 0，说明 "10" 比 "9" 大。 （ {{ select(18) }} ）

• 正确
• 错误

19. [2 分] 选择排序是一种不稳定的排序算法，而冒泡排序是一种稳定的排序算法。 （ {{ select(19) }} ）

• 正确
• 错误

20. [2 分] 求两个长度为 $n$ 序列的最长公共子序列（LCS）长度时，可以使用滚动数组将空间复杂度从 $O(n^2)$ 优化到 $O(n)$。 （ {{ select(20) }} ）

• 正确
• 错误

21. [2 分] 在无向图中，所有顶点的度数之和等于边数的两倍。 （ {{ select(21) }} ）

• 正确
• 错误

22. [2 分] 使用邻接矩阵存储一个有 $V$ 个顶点、$E$ 条边的图，对该图进行一次完整的 BFS 遍历，时间复杂度为 $O(V+E)$。 （ {{ select(22) }} ）

• 正确
• 错误

23. [2 分] 在图像处理或游戏开发中，泛洪（flood fill）算法既可以用 BFS 实现，也可以用 DFS 实现。 （ {{ select(23) }} ）

• 正确
• 错误

24. [2 分] 使用链地址法处理冲突的哈希表，当所有元素都映射到同一个槽位时，查找操作的最坏时间复杂度为 $O(n)$，其中 $n$ 为元素个数。 （ {{ select(24) }} ）

• 正确
• 错误

25. [2 分] 一个包含 $V$ 个顶点的连通无向图，其任何一棵生成树都恰好包含 $V-1$ 条边。 （ {{ select(25) }} ）

• 正确
• 错误