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

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

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

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

姓名: ____________________   日期: ____________

1.简单

什么是递归？

  1. A永远不会结束的循环
  2. B一种数据结构
  3. C一种排序方法
  4. D在更小的输入上调用自身的函数
2.简单

对范围在 0 到 k 之间的 n 个整数进行计数排序（counting sort），运行时间是多少？

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

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

  1. A4 秒
  2. B2 秒
  3. C8 秒
  4. D1 秒
4.中等

为什么动态规划不能真正加速归并排序？

  1. A它的子问题不重叠，因此没有可以复用的结果
  2. B动态规划只适用于图问题，不适用于数组
  3. C归并排序已经是 O(n)
  4. D归并排序没有递归结构
5.中等

说一个 O(n²) 算法也是 O(n³)，这正确吗？

  1. A不正确，因为当 n 很大时 n³ 小于 n²
  2. B不正确，因为 Big O 必须始终给出函数的确切增长率
  3. C正确，但仅当 n 小于 100 时
  4. D正确，因为 Big O 是上界，而 n² 的增长不比 n³ 快
6.中等

均摊分析衡量的是什么？

  1. A在最坏情况的操作序列上，每个操作的平均代价
  2. B算法在最好输入上的代价
  3. C序列中任何位置上单个最昂贵操作的代价
  4. D在随机输入上的期望代价
7.困难

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

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

在有 V 个顶点、E 条边的图上，使用二叉堆的 Dijkstra 算法运行时间是多少？

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

答案

  1. 1. D · 在更小的输入上调用自身的函数
  2. 2. C · O(n + k)
  3. 3. A · 4 秒
  4. 4. A · 它的子问题不重叠，因此没有可以复用的结果
  5. 5. D · 正确，因为 Big O 是上界，而 n² 的增长不比 n³ 快
  6. 6. A · 在最坏情况的操作序列上，每个操作的平均代价
  7. 7. B · 分数背包问题，物品可以分割
  8. 8. A · O((V + E) log V)

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