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

一个 O(n²) 算法在 n = 1000 时需要 1 秒。n = 2000 时大约需要多长时间？

1. A1 秒
2. B8 秒
3. C4 秒
4. D2 秒

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

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

算法的最坏情况运行时间描述的是什么？

1. A在最小输入上所需的时间
2. B在规模为 n 的随机输入上所需的期望时间
3. C在慢速计算机上所需的时间
4. D在所有规模为 n 的输入上所需的最长时间

在一个有序数组中，你从两端各放一个指针向内移动，寻找和为目标值的两个元素。时间复杂度是多少？

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

Floyd–Warshall 算法计算什么？速度如何？

1. A以 O(V + E) 计算从一个源顶点到所有其他顶点的最短路径
2. B以 O(V²) 计算拓扑序
3. C以 O(V³) 计算所有顶点对之间的最短路径
4. D以 O(E log V) 计算最小生成树

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

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

拓扑排序只适用于：

1. A带负权重的图
2. B有向无环图（DAG）
3. C完全图
4. D无向图

用一个只保留最后两个值的循环计算第 n 个斐波那契数，时间和空间代价各是多少？

1. AO(log n) 时间和 O(n) 空间
2. BO(n) 时间和 O(n) 空间
3. CO(2ⁿ) 时间和 O(1) 空间
4. DO(n) 时间和 O(1) 空间