一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

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

• $16$
• $10$
• $9$
• $7$

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

   {{ select(2) }}

• $1820$
• $70$
• $24$
• $16$

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

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

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

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

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

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

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

   {{ select(6) }}

• $720$
• $120$
• $20$
• $15$

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

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

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

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

9. 下面程序的输出为（ ）。

{{ select(9) }}

• $45$
• $102$
• $174$
• $3375$

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

{{ select(10) }}

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

11. 下列 Dijkstra 算法（邻接表；顶点数 $V$、边数 $E$），程序的时间复杂度为（ ）。

{{ select(11) }}

• $O(v^2)$
• $O(v\log v + e)$
• $O((v+e)\log v)$
• $O(v+e)$

12. 下面 count_triple 函数的时间复杂度为（ ）。

{{ select(12) }}

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

13. 下面 merge_sort 函数试图实现​归并排序​，横线处应该填入的是（ ）。

{{ select(13) }}

• arr, left, mid；arr, mid, right
• arr, left, mid + 1；arr, mid + 1, right
• arr, left, mid；arr, mid + 1, right
• arr, left, mid+1；arr, mid+1, right+1

14. 下面 Prim 算法程序中，横线处应该填入的是（ ）。

{{ select(14) }}

• graph[u][v] >= 0 && key[v] > graph[u][v]
• graph[u][v] <= 0 && key[v] > graph[u][v]
• graph[u][v] == 0 && key[v] > graph[u][v]
• graph[u][v] != 0 && key[v] > graph[u][v]

15. 下面的程序使用出边邻接表表达的带权无向图，则从顶点 $0$ 到顶点 $3$ 的最短距离为（ ）。

{{ select(15) }}

• 12
• 11
• 10
• 9

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

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

• 正确
• 错误

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

{{ select(17) }}

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

20. 使用 <math.h> 或 <cmath> 中的函数，对于 int 类型变量 x，表达式 $\mathrm{fabs}(x)$ 和 sqrt(x * x) 的结果总是近似相等的。

{{ select(20) }}

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

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

    {{ select(23) }}

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误