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

一个 O(n) 算法在 n = 100 万时需要 3 秒。n = 200 万时大约需要多长时间？

1. A6 秒
2. B9 秒
3. C3 秒
4. D12 秒

一个问题通常在什么情况下被称为易解的（tractable）？

1. A能在常数时间内求解
2. B只能通过尝试所有可能来求解
3. C没有解
4. D能在多项式时间内求解

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

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

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

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

用自底向上的表格计算第 n 个斐波那契数，时间复杂度是多少？

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

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

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

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

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

关于在无序数组中选择第 k 小的元素，下列哪个说法是正确的？

1. A快速选择的最坏情况为 O(log n)，因为它只对枢轴的一侧递归
2. B快速选择的期望时间为 O(n)，而中位数的中位数法保证最坏情况为 O(n)
3. C选择总是需要 Ω(n log n)，因为必须先排序
4. D选择只能在 O(n²) 内完成