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

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

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

下列哪个运行时间是多项式的？

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

什么是蛮力算法（brute-force algorithm）？

1. A在多个处理器上运行的算法
2. B总是使用递归的算法
3. C随机猜测答案的算法
4. D尝试所有可能的候选解的算法

在边权非负的图中，哪种算法用于求单源最短路径？

1. A任何情况下都必须使用 Bellman–Ford
2. B深度优先搜索（DFS）
3. CKruskal 算法
4. DDijkstra 算法

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

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

快速排序总是使用第一个元素作为基准。它在哪种输入上表现出最坏情况？

1. A已经有序的数组
2. B所有元素都不相同的数组
3. C长度为 2 的数组
4. D随机顺序的数组

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

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

最短简单路径可以在多项式时间内求出。在一般图中求两个顶点之间的最长简单路径，已知情况如何？

1. A它是不可判定的
2. B总能在 O(V + E) 内求解
3. C它是 NP 难的
4. D可以把权重取反后用 Dijkstra 算法求解