GESP 202509 C++ 八级

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

1. [2 分] 小杨想点一杯奶茶外卖，但还差 5 元起送。于是，小杨决定点一些小料。可选的小料包括：珍珠 1 元、椰果 2 元、奶冻 3 元、奶盖 4 元。每种小料最多点 1 份。请问共有多少种满足起送条件的小料方案？（ ） （ {{ select(1) }} ）

• 16
• 10
• 9
• 7

2. [2 分] 小杨和小郑是好朋友，她们在逛商场时发现新设置的大头贴自拍机，于是决定一起拍一组照片。一组照片包括 4 张，这 4 张照片没有顺序区分。拍每张照片时，可以选择有相框或无相框。两人可以分别选择有头饰或无头饰。还可以从 2 种位置（小杨在左，或小郑在左）中选出一种。她们不希望一组照片中出现完全相同的相框、头饰、位置的组合。请问一组照片共有多少种不同的方案？（ ） （ {{ select(2) }} ）

• 1820
• 70
• 24
• 16

3. [2 分] 下列关于 C++ 类的说法，错误的是（ ）。 （ {{ select(3) }} ）

• A. 派生类对象占用的内存总是不小于基类对象。
• B. 派生类可以实现基类的虚函数。
• C. 如果一个类包含纯虚函数，则它不能包含成员变量。
• D. 如果一个类包含纯虚函数，则不能用它定义对象。

4. [2 分] 下列关于树和图的说法，错误的是（ ）。 （ {{ select(4) }} ）

• A. 每个连通图都存在生成树。
• B. 每个存在生成树的有向图，都一定是强连通的。
• C. 保留树的所有节点，并把树的每个节点指向其父节点，则可以将树转换为一个有向强连通图。
• D. 保留树的所有节点，并把树的每个节点指向其子节点，则可以将树转换为一个有向无环图。

5. [2 分] 一对夫妻生男生女的概率相同，这对夫妻希望儿女双全。请问这对夫妻生下三个孩子时，实现儿女双全的概率是多少？（ ） （ {{ select(5) }} ）

• $\frac{1}{4}$
• $\frac{1}{2}$
• $\frac{3}{4}$
• $\frac{7}{8}$

6. [2 分] 二项式 $(x+y)^6$ 的展开式中 $x^2y^4$ 项的系数是（ ）。 （ {{ select(6) }} ）

• 720
• 120
• 20
• 15

7. [2 分] 对一个包含 $V$ 个顶点、$E$ 条边的图，执行广度优先搜索，其最优时间复杂度是（ ）。 （ {{ select(7) }} ）

• $O(V)$
• $O(V+E)$
• $O(V^2)$
• $O(E)$

8. [2 分] 以下关于贪心法和动态规划的说法中，错误的是（ ）。 （ {{ select(8) }} ）

• A. 动态规划能解决大部分贪心算法解决的问题。
• B. 对特定的问题，贪心法不一定适用。
• C. 当特定的问题适用贪心法时，通常比动态规划的时间复杂度更低。
• D. 对很多问题，递推实现和递归实现动态规划方法的时间复杂度相当。

9. [2 分] 下面程序的输出为（ ）。

int N = 15, cnt = 0;
for (int x = 1; x + x + x <= N; x++)
    for (int y = x; x + y + y <= N; y++)
        for (int z = y; x + y + z <= N; z++)
            cnt++;
cout << cnt << endl;

（ {{ select(9) }} ）

• 45
• 102
• 174
• 3375

10. [2 分] 下面程序的时间复杂度为（ ）。

// Sieve of Eratosthenes
bool isPrime[MAXV] = {false};
void sieve() {
    for (int n = 2; n <= MAXV; n++) {
        if (!isPrime[n]) {
            primes[num++] = n;
            for (int i = 0; i < num && n * primes[i] <= MAXV; i++)
                isPrime[n * primes[i]] = true;
        }
    }
}

（ {{ select(10) }} ）

• $O(N \log N)$
• $O(N \log \log N)$
• $O(N)$
• $O(\log N)$

11. [2 分] 下列 Dijkstra 算法，假设图 graph 中顶点数 $V$、边数 $E$，则程序的时间复杂度为（ ）。 （ {{ select(11) }} ）

• $O(V^2)$
• $O(V \log V + E)$
• $O((V+E) \log V)$
• $O(V+E)$

12. [2 分] 下面 count_triple 函数的时间复杂度为（ ）。 （ {{ select(12) }} ）

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

13. [2 分] 下面 merge_sort 函数实现归并排序算法，横线处应该填入的是（ ）。 （ {{ select(13) }} ）

• A. arr, left, mid / arr, mid, right
• B. arr, left, mid + 1 / arr, mid + 1, right
• C. arr, left, mid / arr, mid + 1, right
• D. arr, left, mid + 1 / arr, mid + 1, right + 1

14. [2 分] 下面 Prim 算法程序中，横线处应该填入的是（ ）。 （ {{ select(14) }} ）

• A. graph[u][v] >= 0 && key[v] > graph[u][v]
• B. graph[u][v] <= 0 && key[v] > graph[u][v]
• C. graph[u][v] >= 0 && key[v] < graph[u][v]
• D. graph[u][v] != 0 && key[v] > graph[u][v]

15. [2 分] 下面的程序使用出边邻接表表达的带权无向图，则从顶点 0 到顶点 3 的最短距离为（ ）。 （ {{ select(15) }} ）

• 12
• 11
• 10
• 9

---

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

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

• 正确
• 错误

17. [2 分] 下列 C++ 语言代码，能够安全地输出 arr[5] 的值。

int n = 5;
int arr[n] = {1, 2, 3};
cout << arr[5];

（ {{ select(17) }} ）

• 正确
• 错误

18. [2 分] 对 $n$ 个元素的数组进行排序，最差情况的时间复杂度为 $O(n^2)$。 （ {{ select(18) }} ）

• 正确
• 错误

19. [2 分] 有 4 个红球、3 个蓝球和 2 个绿球排成一排（相同颜色球为完全相同），则不同的排列方案数为 1260 种。 （ {{ select(19) }} ）

• 正确
• 错误

20. [2 分] 使用 math.h 或 cmath 头文件中的函数，对于 int 类型的变量 x，表达式 fabs(x) 和 sqrt(x * x) 的结果总是近似相等的。 （ {{ select(20) }} ）

• 正确
• 错误

21. [2 分] 运算符重载是 C++ 语言静态多态的一种典型体现，而使用 C 语言则无法实现运算符重载。 （ {{ select(21) }} ）

• 正确
• 错误

22. [2 分] 存在一个简单无向图满足：顶点数为 6，边数为 8，6 个顶点的度数分别为 3、3、3、3、2、2。 （ {{ select(22) }} ）

• 正确
• 错误

23. [2 分] 已知两个 double 类型的变量 r 和 theta 分别表示一个扇形的圆半径及圆心角（弧度），则扇形的周长可以通过表达式 (2 + theta) * r 求得。 （ {{ select(23) }} ）

• 正确
• 错误

24. [2 分] Dijkstra 算法的时间复杂度为 $O(V^2)$，其中 $V$ 为图中顶点的数量。 （ {{ select(24) }} ）

• 正确
• 错误

25. [2 分] 从 32 名学生中选出 2 人分别担任男生班长和女生班长（男生班长必须是男生，女生班长必须是女生），则共有 $C(32, 2)/2$ 种不同的选法。 （ {{ select(25) }} ）

• 正确
• 错误