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

当 n 很大时，哪个复杂度类增长最快？

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

如果一个操作的运行时间是 O(1)，这意味着什么？

1. A它只能运行一次
2. B它总是恰好花费一秒
3. C它的运行时间不随输入规模增长
4. D它每秒运行时间恰好处理一个元素

分治算法的三个步骤是什么？

1. A猜测、检查、重复
2. B排序、查找、返回
3. C读取、计算、写入
4. D分解、解决、合并

对长度为 m 和 n 的两个字符串求最长公共子序列，标准动态规划算法的时间复杂度是多少？

1. AO(mn)
2. BO(m + n)
3. CO(2^m+n)
4. DO(mn log n)

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

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

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

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

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

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

旅行商问题如何分类？

1. A判定版本属于 P，但优化版本是 NP 完全的
2. B它属于 P，因为 Dijkstra 算法通过把每个城市访问一次来求解它
3. C它是不可判定的
4. D判定版本是 NP 完全的，优化版本是 NP 难的