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

1. 下列关于排序的说法，正确的是（ ）。 {{ select(1) }}

• 冒泡排序是最快的排序算法之一。
• 快速排序通常是不稳定的。
• 最差情况，$n$ 个元素做归并排序的时间复杂度为 O(n)。
• 以上均不正确。

2. 下面的程序属于哪种算法（ ）。

   

   {{ select(2) }}

• 贪心算法
• 动态规划
• 深度优先搜索
• 广度优先搜索

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

• C++ 类对象销毁时，会执行析构函数。
• C++ 类可以通过定义构造函数实现自动类型转换。
• C++ 类可以通过重载 [] 运算符实现通过给定下标访问数组成员的元素。
• C++ 类可以包含任意类型的成员变量。

4. 一个连通的简单无向图，共有 28 条边，则该图至少有（ ）个顶点。 {{ select(4) }}

• 6
• 7
• 8
• 9

5. 以下哪个方案不能合理解决或缓解哈希表冲突（ ）。 {{ select(5) }}

• 在每个哈希表项处，使用单链表管理该表项的冲突元素。
• 建立额外的单链表，用来管理所有发生冲突的元素。
• 使用不同的哈希函数再建立一个哈希表，用来管理所有发生冲突的元素。
• 用新元素覆盖发生冲突的哈希表项。

6. 已知一颗二叉树的中序遍历序列为 {C F B A E D G}，后序遍历序列为 {F C B E G D A}，则下列说法中正确的是（ ）。 {{ select(6) }}

• 该树是平衡二叉树。
• 该树的高为 4。
• 该树有 4 个叶节点。
• 以上说法都不对。

7. 以下关于二叉排序树的说法，正确的是（ ）。 {{ select(7) }}

• 二叉排序树的中序遍历序列一定是有序的。
• 在含 $n$ 个节点的二叉排序树中查找元素，最差情况的时间复杂度为 $O(logn)$。
• 二叉排序树一定是二叉平衡树。
• 以上说法都不对。

8. 已知 $x$ 为 double 类型变量，且值大于 0，则下列表达式的值一定大于 0 的是（ ）。 {{ select(8) }}

• $\sin(x)\,/\,x$
• $\exp(x) - x$
• $\log(x) - x$
• $x \times x - x$

9. 一个简单有向图有 10 个结点、30 条边。再增加多少条边可以成为完全图（ ）。 {{ select(9) }}

• 60
• 70
• 15
• 20

10. 下列选项中，哪个可能是下图的深度优先遍历序列（ ）。

{{ select(10) }}

• 8, 6, 1, 5, 3, 4, 2, 10, 7, 12, 11, 9
• 7, 8, 6, 4, 2, 1, 5, 3, 12, 9, 11, 10
• 8, 10, 12, 9, 11, 4, 5, 3, 2, 1, 6, 7
• 7, 8, 10, 9, 11, 12, 4, 5, 1, 2, 3, 6

11. 下面 schedule 函数的时间复杂度为（ ）。

{{ select(11) }}

• $O(n)$
• $O(logn)$
• $O(nlogn)$
• $O(n^2)$

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

{{ select(12) }}

• $O(n)$
• $O(logn)$
• $O(1)$
• 可能无法返回

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

{{ select(13) }}

• $O(n)$
• $O(n^2)$
• $O(n^3)$
• $O(n^4)$

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

{{ select(14) }}

• 6
• 13
• 20
• 无法正常结束。

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

{{ select(15) }}

• 6
• 7
• 8
• 9

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

16. 祖冲之是南北朝时期杰出的数学家、天文学家，其主要贡献在数学、天文历法和机械制造三方面。他首次将“圆周率”精算到小数第七位，即在 3.1415926 和 3.1415927 之间。 {{ select(16) }}

• 正确
• 错误

17. C++ 语言中，表达式 2 ^ 3 的结果类型为 int，值为 8。 {{ select(17) }}

• 正确
• 错误

18. 一棵有 $n$ 个节点的完全二叉树，则树的深度为 $\lfloor log_{2}(N) \rfloor + 1$。 {{ select(18) }}

• 正确
• 错误

19. 能用动态规划解决的问题，一般也可以用贪心法解决，但动态规划的效率更高。 {{ select(19) }}

• 正确
• 错误

20. 使用 math.h 或 cmath 头文件中的正弦函数，表达式 $\sin(30)$ 的结果类型为 double，值约为 0.5。 {{ select(20) }}

• 正确
• 错误

21. 要求出简单有向图中从顶点 A 到顶点 B 的最短路径，在深度优先搜索和广度优先搜索中选择，广度优先更适合。 {{ select(21) }}

• 正确
• 错误

22. 某 $N$ 个表项的哈希表，在发生哈希函数冲突时采用向后寻找空位的方法解决冲突。其查找操作的平均时间复杂度为 $O(1)$，即使当该哈希表的每个表项都有元素时，查找操作的平均时间复杂度仍为 $O(1)$。 {{ select(22) }}

• 正确
• 错误

23. 动态规划有递推实现和递归实现，有时两种实现的时间复杂度不同。 {{ select(23) }}

• 正确
• 错误

24. 围棋游戏中，判断落下一枚棋子后是否会提掉对方的子，可以使用泛洪算法来实现。 {{ select(24) }}

• 正确
• 错误

25. 类 B 继承了抽象类 A，但未实现类 A 中的纯虚函数 f，则类 B 不能直接实例化。 {{ select(25) }}

• 正确
• 错误