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

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

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

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

姓名: ____________________   日期: ____________

1.简单

在包含 n 个元素的无序数组中进行线性查找（linear search）的时间复杂度（最坏情况）是多少？

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

哪种排序算法选择一个基准，并把数组划分为较小元素和较大元素两部分？

  1. A归并排序
  2. B插入排序
  3. C快速排序
  4. D冒泡排序
3.简单

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

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

下面代码的时间复杂度是多少：for i = 1 to n: for j = 1 to i: 执行 O(1) 的工作？

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

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

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

一个函数先运行一个 n 次迭代的循环，然后再单独运行另一个 n 次迭代的循环。它的时间复杂度是多少？

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

插入排序在有序输入上运行时间为 O(n)。这与比较排序的 Ω(n log n) 下界矛盾吗？

  1. A不矛盾，下界针对的是所有输入中的最坏情况，而不是每一个输入
  2. B不矛盾，因为插入排序不是比较排序
  3. C矛盾，因此这个下界是错的
  4. D矛盾，但仅对长度小于 100 的数组
8.困难

22n 属于 O(2ⁿ) 吗？

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

答案

  1. 1. A · O(n)
  2. 2. C · 快速排序
  3. 3. A · 在给定的规模为 n 的输入分布上的期望时间
  4. 4. D · O(n²)
  5. 5. B · O(V × E)
  6. 6. C · O(n)
  7. 7. A · 不矛盾，下界针对的是所有输入中的最坏情况，而不是每一个输入
  8. 8. A · 不属于，因为 22n = 4ⁿ，而 4ⁿ / 2ⁿ = 2ⁿ 无界地增长

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