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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

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

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

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

3n² + 5n + 2 的 Big O 是什么？

  1. AO(n³)
  2. BO(3n²)
  3. CO(5n)
  4. DO(n²)
4.中等

对于在满时将容量翻倍的动态数组，追加元素的均摊（amortised）时间复杂度是多少？

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

基于比较的排序在最坏情况下的下界是：

  1. AΩ(n)
  2. BΩ(log n)
  3. CΩ(n log n)
  4. DΩ(n²)
6.中等

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

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

哪种算法通过反复加入不会形成环的最便宜的边来求最小生成树？

  1. AKruskal 算法
  2. BDijkstra 算法
  3. CFloyd–Warshall
  4. D从一个节点出发的 Prim 算法
8.困难

Cook–Levin 定理确立了什么？

  1. A每个 NP 问题都能在指数时间内求解
  2. BP 不等于 NP
  3. C停机问题是不可判定的
  4. D布尔可满足性问题（SAT）是 NP 完全的

答案

  1. 1. B · 反复找出未排序部分的最小值，并把它交换到前面
  2. 2. B · f 与 g 以相同的速率增长，上下都被 g 的常数倍所界定
  3. 3. D · O(n²)
  4. 4. D · O(1)
  5. 5. C · Ω(n log n)
  6. 6. D · O(mn)
  7. 7. A · Kruskal 算法
  8. 8. D · 布尔可满足性问题（SAT）是 NP 完全的

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