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

哪种记号表示增长的上界？

1. ABig O
2. BLittle omega
3. CBig Theta
4. DBig Omega

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

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

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

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

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

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

对 n 个元素的数组进行归并排序，递归共有多少层？

1. A约 log₂ n 层
2. B约 n 层
3. C约 n / 2 层
4. D约 √n 层

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

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

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

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

Bellman–Ford 算法如何检测从源点可达的负权环？

1. A检查是否有边的权重为负
2. B用深度优先搜索统计环的数量
3. C在 V − 1 轮之后，检查是否还有边可以被松弛
4. D它运行两次 Dijkstra 算法，并比较两次的距离结果