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

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

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

当 n 变大时，下列哪一项增长最慢？

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

通过下标访问数组中的元素需要：

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

为什么动态规划不能真正加速归并排序？

1. A它的子问题不重叠，因此没有可以复用的结果
2. B归并排序没有递归结构
3. C归并排序已经是 O(n)
4. D动态规划只适用于图问题，不适用于数组

递推式 T(n) = 2T(n/2) + O(1) 的解是什么？

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

均摊分析衡量的是什么？

1. A算法在最好输入上的代价
2. B在最坏情况的操作序列上，每个操作的平均代价
3. C序列中任何位置上单个最昂贵操作的代价
4. D在随机输入上的期望代价

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

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

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

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