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

下列哪个运行时间是多项式的？

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

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

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

O(2ⁿ) 的增长称为什么？

1. A多项式级
2. B指数级
3. C线性
4. D对数级

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

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

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

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

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

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

为什么当某些边权为负时，Dijkstra 算法可能给出错误结果？

1. A优先队列中不能存储负数
2. B顶点被取出时距离就被确定，但之后的负权边仍可能给它一条更短的路径
3. C每遇到一条负权边它就会陷入无限循环
4. D它只适用于无向图

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

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