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

一个算法的运行时间是 O(n)。这种增长称为什么？

1. A常数
2. B对数
3. C平方
4. D线性

一个循环从 i = 1 开始，每次迭代将 i 翻倍，直到 i > n。它运行多少次迭代？

1. A约 n / 2 次
2. B约 n 次
3. C约 log₂ n 次
4. D约 n² 次

在 n 个数的无序数组中找出最大值的时间复杂度是多少？

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

贪心算法（greedy algorithm）：

1. A只使用递归
2. B总能给出最优解
3. C在每一步都做出局部最优的选择
4. D尝试所有可能的解

Prim 算法如何构建最小生成树？

1. A运行广度优先搜索并保留 BFS 树
2. B把所有边按权重排序，逐条加入，除非会在森林中形成环
3. C从一个起始顶点开始扩展一棵树，每次加入离开该树的最便宜的边
4. D不断删除最贵的边，直到没有环为止

哪种排序算法是稳定的？

1. A快速排序（常见的原地版本）
2. B归并排序
3. C堆排序
4. D选择排序（常见版本）

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

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

Strassen 算法在矩阵乘法中对半尺寸的分块只做 7 次而不是 8 次递归乘法。它的运行时间是多少？

1. AΘ(n² log n)
2. BΘ(n³)
3. CΘ(n^{log₂ 7})，约为 n^2.81
4. DΘ(n²)