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

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

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

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

姓名: ____________________   日期: ____________

1.简单

插入排序（insertion sort）的最坏情况时间复杂度是多少？

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

通过下标访问数组中的元素需要：

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

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

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

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

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

快速排序的最坏情况时间复杂度是多少？

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

基于比较的排序在最坏情况下的下界是：

  1. AΩ(n log n)
  2. BΩ(n)
  3. CΩ(n²)
  4. DΩ(log n)
7.困难

旅行商问题如何分类？

  1. A判定版本属于 P，但优化版本是 NP 完全的
  2. B判定版本是 NP 完全的，优化版本是 NP 难的
  3. C它是不可判定的
  4. D它属于 P，因为 Dijkstra 算法通过把每个城市访问一次来求解它
8.困难

为什么在单链表上二分查找不能达到 O(log n) 的时间？

  1. A链表节点上的比较更慢
  2. B二分查找至少需要两倍的内存
  3. C链表无法排序
  4. D由于不能按下标直接访问，到达中间元素需要 O(n) 步

答案

  1. 1. D · O(n²)
  2. 2. C · O(1)
  3. 3. A · O(n)
  4. 4. C · O(n)
  5. 5. B · O(n²)
  6. 6. A · Ω(n log n)
  7. 7. B · 判定版本是 NP 完全的，优化版本是 NP 难的
  8. 8. D · 由于不能按下标直接访问，到达中间元素需要 O(n) 步

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