算法与复杂度练习卷（附答案）

归并排序的最坏情况时间复杂度是多少？

1. AO(n)
2. BO(n log n)
3. CO(n²)
4. DO(log n)

哪种排序算法选择一个基准，并把数组划分为较小元素和较大元素两部分？

1. A归并排序
2. B插入排序
3. C冒泡排序
4. D快速排序

什么是递归？

1. A一种数据结构
2. B永远不会结束的循环
3. C一种排序方法
4. D在更小的输入上调用自身的函数

在无权图上进行广度优先搜索（BFS）可以求出：

1. A所有图的拓扑序
2. B最小生成树
3. C从起始节点出发、按边数计的最短路径
4. D含负权重边的图中的最短路径

为什么许多库排序函数在子数组很小时会改用插入排序？

1. A递归算法无法处理少于 10 个元素的数组
2. B在大规模输入上，插入排序比任何其他排序算法使用的内存都少
3. C插入排序在最坏情况下是 O(n log n)
4. D插入排序开销小，在小规模或几乎有序的输入上很快

说一个 O(n²) 算法也是 O(n³)，这正确吗？

1. A不正确，因为 Big O 必须始终给出函数的确切增长率
2. B不正确，因为当 n 很大时 n³ 小于 n²
3. C正确，因为 Big O 是上界，而 n² 的增长不比 n³ 快
4. D正确，但仅当 n 小于 100 时

如果有人为某个 NP 完全问题找到了多项式时间算法，会有什么结果？

1. A停机问题将变得可判定
2. B只有那一个问题会进入 P
3. C所有指数时间算法都会立即变成线性时间
4. DNP 中的每个问题都能在多项式时间内求解，因此 P = NP

插入排序在有序输入上运行时间为 O(n)。这与比较排序的 Ω(n log n) 下界矛盾吗？

1. A不矛盾，因为插入排序不是比较排序
2. B矛盾，因此这个下界是错的
3. C矛盾，但仅对长度小于 100 的数组
4. D不矛盾，下界针对的是所有输入中的最坏情况，而不是每一个输入