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

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

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

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

姓名: ____________________   日期: ____________

1.简单

归并排序的最坏情况时间复杂度是多少？

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

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

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

选择排序（selection sort）是如何工作的？

  1. A反复交换顺序错误的相邻元素
  2. B通过移动元素，把每个元素插入到不断增长的有序部分中
  3. C反复找出未排序部分的最小值，并把它交换到前面
  4. D把数组对半分开再合并
4.中等

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

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

下面代码的时间复杂度是多少：for i = 1 to n: (j = 1; while j < n: j = j × 2)？

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

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

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

旅行商问题如何分类？

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

一个问题是 NP 完全（NP-complete）的，当且仅当它：

  1. A可以在多项式时间内解决
  2. B不属于 NP，但比所有 NP 问题都难，例如停机问题
  3. C不可能被解决
  4. D属于 NP，且所有 NP 问题都能在多项式时间内归约到它

答案

  1. 1. B · O(n log n)
  2. 2. A · f 与 g 以相同的速率增长，上下都被 g 的常数倍所界定
  3. 3. C · 反复找出未排序部分的最小值，并把它交换到前面
  4. 4. D · 以 O(V³) 计算所有顶点对之间的最短路径
  5. 5. C · O(n log n)
  6. 6. C · O(n)
  7. 7. B · 判定版本是 NP 完全的，优化版本是 NP 难的
  8. 8. D · 属于 NP，且所有 NP 问题都能在多项式时间内归约到它

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