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

在包含 n 个元素的无序数组中进行线性查找（linear search）的时间复杂度（最坏情况）是多少？

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

3n² + 5n + 2 的 Big O 是什么？

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

平均情况运行时间描述的是什么？

1. A最好情况与最坏情况运行时间之间的中间值
2. B平均长度的输入所需的时间
3. C在最常见的计算机上所需的时间
4. D在给定的规模为 n 的输入分布上的期望时间

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

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

Prim 算法如何构建最小生成树？

1. A运行广度优先搜索并保留 BFS 树
2. B把所有边按权重排序，逐条加入，除非会在森林中形成环
3. C从一个起始顶点开始扩展一棵树，每次加入离开该树的最便宜的边
4. D不断删除最贵的边，直到没有环为止

对 n 个元素的数组进行归并排序，递归共有多少层？

1. A约 n 层
2. B约 √n 层
3. C约 log₂ n 层
4. D约 n / 2 层

要证明一个判定问题 X 是 NP 完全的，必须证明哪两点？

1. AX 属于 P，并且 X 能归约到 SAT
2. BX 没有多项式算法，并且 X 是可判定的
3. CX 属于 NP，并且某个已知的 NP 完全问题能在多项式时间内归约到 X
4. DX 能归约到 P 中的某个问题，并且 X 属于 NP

关于 log(n!)，哪个界是正确的？

1. AΘ(log n)
2. BΘ(n log n)
3. CΘ(n)
4. DΘ(n²)