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

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

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

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

姓名: ____________________   日期: ____________

1.简单

一个 O(n²) 算法在 n = 1000 时需要 1 秒。n = 2000 时大约需要多长时间？

  1. A2 秒
  2. B4 秒
  3. C8 秒
  4. D1 秒
2.简单

一个算法的运行时间是 O(n)。这种增长称为什么？

  1. A线性
  2. B对数
  3. C常数
  4. D平方
3.简单

平均情况运行时间描述的是什么？

  1. A在给定的规模为 n 的输入分布上的期望时间
  2. B在最常见的计算机上所需的时间
  3. C最好情况与最坏情况运行时间之间的中间值
  4. D平均长度的输入所需的时间
4.中等

硬币面值为 1、3 和 4，金额为 6，贪心的"先取最大硬币"方法使用多少枚硬币？与最优解相比如何？

  1. A贪心用 4 枚；最优解是 3 枚
  2. B贪心用 3 枚；最优解是 3 枚
  3. C贪心用 2 枚；最优解是 2 枚
  4. D贪心用 3 枚；最优解是 2 枚
5.中等

对 n 个 k 进制、d 位的整数进行 LSD 基数排序（radix sort），运行时间是多少？

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

在有 V 个顶点、E 条边的图上，Bellman–Ford 算法的时间复杂度是多少？

  1. AO(V × E)
  2. BO(V + E)
  3. CO(E log V)
  4. DO(V³ × E)
7.困难

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

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

关于 little-o 记号，下列哪个说法是正确的？

  1. An² = o(n)
  2. Bn = o(n)，因为每个函数都是自身的 little-o
  3. Cn = o(n²)，但 n 不是 o(n)
  4. D2n = o(n)，因为 2n 增长得慢

答案

  1. 1. B · 4 秒
  2. 2. A · 线性
  3. 3. A · 在给定的规模为 n 的输入分布上的期望时间
  4. 4. D · 贪心用 3 枚；最优解是 2 枚
  5. 5. C · O(d(n + k))
  6. 6. A · O(V × E)
  7. 7. A · 至多是最小顶点覆盖大小的两倍
  8. 8. C · n = o(n²)，但 n 不是 o(n)

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