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

一个 O(n²) 算法在 n = 1000 时需要 1 秒。n = 2000 时大约需要多长时间？

1. A2 秒
2. B1 秒
3. C8 秒
4. D4 秒

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

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

f(n) = Θ(g(n)) 是什么意思？

1. Af 的增长严格快于 g
2. B对每个 n，f 总是小于 g，因此 g 是它的上界，但绝不是下界
3. Cf 的增长严格慢于 g
4. Df 与 g 以相同的速率增长，上下都被 g 的常数倍所界定

哪种排序算法是稳定的？

1. A堆排序
2. B归并排序
3. C快速排序（常见的原地版本）
4. D选择排序（常见版本）

用标准的三重循环计算两个 n × n 矩阵的乘积，时间复杂度是多少？

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

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

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

下列哪个可满足性问题已知可以在多项式时间内求解？

1. A3-SAT，每个子句恰好有三个文字
2. B电路可满足性问题
3. C2-SAT，每个子句至多有两个文字
4. D合取范式公式上的一般 SAT

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

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