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

免费可打印的算法与复杂度练习卷：8 道题，从简单到考试水平，附答案。可打印或另存为 PDF。

新练习卷在线练习，附提示

教师请注意： 可免费打印、复印并在课堂上使用。每份新练习题都有新的数值和独立的答案。欢迎在课程页面添加指向 ExamProblems 的链接。

姓名: ____________________   日期: ____________

1.简单

插入排序（insertion sort）的最坏情况时间复杂度是多少？

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

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

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

log₂ 1024 等于多少？

  1. A512
  2. B12
  3. C10
  4. D32
4.中等

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

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

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

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

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

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

当 n 很大时，n! 与 2ⁿ 相比如何？

  1. A2ⁿ 比 n! 增长得快
  2. B两者以相同的速率增长
  3. Cn! 是 O(n²)
  4. Dn! 比 2ⁿ 增长得快
8.困难

关于类 NP 的哪个定义是正确的？

  1. A不能在多项式时间内求解的问题
  2. B给定证书时，其"是"答案能在多项式时间内验证的判定问题
  3. C任何算法都无法求解的问题
  4. D非多项式的问题

答案

  1. 1. C · O(n²)
  2. 2. C · 它的运行时间不随输入规模增长
  3. 3. C · 10
  4. 4. A · 正确，因为 Big O 是上界，而 n² 的增长不比 n³ 快
  5. 5. C · O(log n)
  6. 6. D · 以 O(V³) 计算所有顶点对之间的最短路径
  7. 7. D · n! 比 2ⁿ 增长得快
  8. 8. B · 给定证书时，其"是"答案能在多项式时间内验证的判定问题

完整分步解答：请在 examproblems.com 上练习本主题。