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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

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

一个 O(n) 算法在 n = 100 万时需要 3 秒。n = 200 万时大约需要多长时间？

  1. A6 秒
  2. B9 秒
  3. C3 秒
  4. D12 秒
3.简单

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

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

在无权图上进行广度优先搜索（BFS）可以求出：

  1. A所有图的拓扑序
  2. B含负权重边的图中的最短路径
  3. C从起始节点出发、按边数计的最短路径
  4. D最小生成树
5.中等

贪心算法（greedy algorithm）：

  1. A尝试所有可能的解
  2. B总能给出最优解
  3. C在每一步都做出局部最优的选择
  4. D只使用递归
6.中等

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

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

对于哪种背包问题变体，贪心规则"按单位重量价值的顺序取物品"总能给出最优解？

  1. A两种变体都不可以
  2. B0/1 背包问题，物品必须整个拿取
  3. C两种变体都可以
  4. D分数背包问题，物品可以分割
8.困难

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

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

答案

  1. 1. B · O(n²)
  2. 2. A · 6 秒
  3. 3. D · O(log n)
  4. 4. C · 从起始节点出发、按边数计的最短路径
  5. 5. C · 在每一步都做出局部最优的选择
  6. 6. D · O(n)
  7. 7. D · 分数背包问题，物品可以分割
  8. 8. D · 至多是最小顶点覆盖大小的两倍

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