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

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

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

归并排序采用哪种设计策略？

1. A分治法（divide and conquer）
2. B动态规划
3. C贪心选择
4. D蛮力法

什么是记忆化（memoisation）？

1. A函数返回后释放内存
2. B在每行代码旁边写注释
3. C自动把递归转换为等价的循环，从而不需要调用栈
4. D存储函数调用的结果，使重复调用能直接从内存中得到答案

对 n 个 k 进制、d 位的整数进行 LSD 基数排序（radix sort），运行时间是多少？

1. AO(dn log k)
2. BO(n²)
3. CO(d(n + k))
4. DO(n log n)

在活动选择问题中，哪条贪心规则总能得到数量最多的互不重叠的活动？

1. A选择最早结束的活动，然后在与之相容的活动中重复这一步
2. B先选择最短的活动
3. C先选择与其他活动重叠最少的活动，然后在与之相容的活动中重复这一步
4. D选择最早开始的活动

为什么在 Big O 中通常省略对数的底，例如写成 O(log n)？

1. A底只在 n 很小时才有影响
2. B计算机科学中所有对数的底都是 10，所以可以省略
3. C对数总是被四舍五入为整数
4. D不同底的对数之间只相差一个常数因子

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

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

不可判定问题与难解问题有什么区别？

1. A难解问题无法被任何算法求解，而不可判定问题只需要指数时间
2. B两者都意味着该问题根本没有算法
3. C不可判定问题没有任何能处理所有输入的算法，而难解问题有算法，但太慢
4. D不可判定问题属于 NP，而难解问题属于 P