5325：[GESP202403] 七级客观题
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：文本裁判
金币值：
命题人：
提交：0
解决：0
题目描述
# 一、单选题（每题 2 分，共 30 分）
1. 下列关于排序的说法，正确的是( )。
- 冒泡排序是最快的排序算法之一。
- 快速排序通常是不稳定的。
- 最差情况， $N$个元素做归并排序的时间复杂度为$O(N)$
- 以上均不正确。
2. 下面的程序属于哪种算法( )。
- 贪心算法
- 动态规划
- 深度优先搜索
- 广度优先搜索
3. 下面有关C++类的说法，错误的是（ ）。
- C++类对象销毁时，会执行析构函数。
- C++类可以通过定义构造函数实现自动类型转换。
- C++类可以通过重载 [] 运算符实现通过给定下标访问数组成员的元素。
- C++类可以包含任意类型的成员变量。
4. 一个连通的简单无向图，共有28条边，则该图至少有( )个顶点。
- 6
- 7
- 8
- 9
5. 以下哪个方案不能合理解决或缓解哈希表冲突（ ）。
- 在每个哈希表项处，使用单链表管理该表项的冲突元素。
- 建立额外的单链表，用来管理所有发生冲突的元素。
- 使用不同的哈希函数再建立一个哈希表，用来管理所有发生冲突的元素。
- 用新元素覆盖发生冲突的哈希表项。
6. 已知一颗二叉树的中序遍历序列为：{C F B A E D G}，后序遍历序列为：{F C B E G D A}，则下列说法中正确的是( )。
- 该树是平衡二叉树。
- 该树的高为4。
- 该树有4个叶节点。
- 以上说法都不对。
7. 以下关于二叉排序树的说法，正确的是（ ）。
- 二叉排序树的中序遍历序列一定是有序的。
- 在含`n`个节点的二叉排序树中查找元素，最差情况的时间复杂度为$O(log(n))$。
- 二叉排序树一定是二叉平衡树。
- 以上说法都不对。
8. 已知 `x` 为 `double `类型的变量，且值大于0，则下列表达式的值一定大于0的是( )。
- `sin(x) / x`
- `exp(x) - x`
- `log(x) - x`
- `x \* x - x`
9. 一个简单有向图有10个结点、30条边。再增加多少条边可以成为完全图。（ ）
- 60
- 70
- 15
- 20
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 `函数的时间复杂度为( )。
- $O(n)$
- $O(log(n))$
- $O(n\ log(n))$
- $O(n^2)$
12. 下面`search`函数的平均时间复杂度为( )。
- $O(n)$
- $O(log(n))$
- $O(1)$
- 可能无法返回
13. 下面`count_triple`函数的时间复杂度为( )。
- $O(N)$
- $O(N^2)$
- $O(N^3)$
- $O(N^4)$
14. 下面程序的输出为（ ）。
- 6
- 13
- 20
- 无法正常结束。
15. 下面的程序使用邻接矩阵表达的带权无向图，则从顶点0到顶点3的最短距离为（ ）。
- 6
- 7
- 8
- 9
# 二、判断题（每题 2 分，共 20 分）
16. 祖冲之是南北朝时期杰出的数学家、天文学家，其主要贡献在数学、天文历法和机械制造三方面。他首次将“圆周率”精算到小数第七位，即在3.1415926和3.1415927之间。
- 正确
- 错误
17. C++语言中，表达式`2 ^ 3`的结果类型为 `int` 、值为`8`。( )
- 正确
- 错误
18. 一棵有 $N$个节点的完全二叉树，则树的深度为$[log_2(N)]+1$ 。( )
- 正确
- 错误
19. 能用动态规划解决的问题，一般也可以用贪心法解决，但动态规划的效率更高。( )
- 正确
- 错误
20. 使用`math.h`或 `cmath` 头文件中的正弦函数，表达式`sin(30)`的结果类型为`double`、值约为`0.5`。( )
- 正确
- 错误
21. 要求出简单有向图中从顶点`A`到顶点` B` 的最短路径，在深度优先搜索和广度优先搜索中选择，广度优先更适合。( )
- 正确
- 错误
22. 某`N`个表项的哈希表，在发生哈希函数冲突时采用向后寻找空位的方法解决冲突。其查找操作的平均时间复杂度为$O(1)$ ，即使当该哈希表的每个表项都有元素时，查找操作的平均时间复杂度仍为$O(1)$ 。( )
- 正确
- 错误
23. 动态规划有递推实现和递归实现，有时两种实现的时间复杂度不同。( )
- 正确
- 错误
24. 围棋游戏中，判断落下一枚棋子后是否会提掉对方的子，可以使用泛洪算法来实现。( )
- 正确
- 错误
25. 类`B`继承了抽象类`A `，但未实现类 `A `中的纯虚函数`f`，则类`B`不能直接实例化。( )
- 正确
- 错误