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

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

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

选择排序（selection sort）是如何工作的？

1. A反复交换顺序错误的相邻元素
2. B通过移动元素，把每个元素插入到不断增长的有序部分中
3. C反复找出未排序部分的最小值，并把它交换到前面
4. D把数组对半分开再合并

O(2ⁿ) 的增长称为什么？

1. A线性
2. B多项式级
3. C指数级
4. D对数级

简单的递归阶乘函数 fact(n) = n × fact(n − 1) 使用多少栈空间？

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

你对一个 n 个元素的数组排序一次，然后用二分查找回答 k 次成员查询。总代价是多少？

1. AO(k n log n)
2. BO(n + k)
3. CO(nk)
4. DO(n log n + k log n)

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

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

Held–Karp 动态规划算法能精确求解旅行商问题。对 n 个城市，它的运行时间是多少？

1. AO(n³)
2. BO(n² 2ⁿ)
3. CO(2^n²)
4. DO(n!)

关于类 NP 的哪个定义是正确的？

1. A不能在多项式时间内求解的问题
2. B给定证书时，其"是"答案能在多项式时间内验证的判定问题
3. C任何算法都无法求解的问题
4. D非多项式的问题