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

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

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

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

姓名: ____________________   日期: ____________

1.简单

一个问题通常在什么情况下被称为易解的（tractable）？

  1. A只能通过尝试所有可能来求解
  2. B没有解
  3. C能在多项式时间内求解
  4. D能在常数时间内求解
2.简单

在有序数组上进行二分查找（binary search）的时间复杂度是多少？

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

哪种记号表示增长的上界？

  1. ALittle omega
  2. BBig Omega
  3. CBig Theta
  4. DBig O
4.中等

下面代码的时间复杂度是多少：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)
5.中等

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

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

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

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

取一个极大匹配中每条边的两个端点，可以得到一个顶点覆盖。这个覆盖有多好？

  1. A与最优解相比质量未知
  2. B至多是最小顶点覆盖大小的两倍
  3. C至多是最小值的 log n 倍
  4. D总是一个最小顶点覆盖
8.困难

22n 属于 O(2ⁿ) 吗？

  1. A属于，因为两者都是指数级的
  2. B属于，因为在 Big O 中指数里的常数因子总是被忽略
  3. C不属于，因为 22n = 4ⁿ，而 4ⁿ / 2ⁿ = 2ⁿ 无界地增长
  4. D不属于，因为 22n 增长得比 2ⁿ 慢

答案

  1. 1. C · 能在多项式时间内求解
  2. 2. C · O(log n)
  3. 3. D · Big O
  4. 4. C · O(n log n)
  5. 5. A · O(n)
  6. 6. C · O(n²)
  7. 7. B · 至多是最小顶点覆盖大小的两倍
  8. 8. C · 不属于，因为 22n = 4ⁿ，而 4ⁿ / 2ⁿ = 2ⁿ 无界地增长

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