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

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

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

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

姓名: ____________________   日期: ____________

1.简单

标准的基于数组的归并排序使用多少额外内存？

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

选择排序（selection sort）是如何工作的？

  1. A反复找出未排序部分的最小值，并把它交换到前面
  2. B把数组对半分开再合并
  3. C通过移动元素，把每个元素插入到不断增长的有序部分中
  4. D反复交换顺序错误的相邻元素
3.简单

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

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

用自底向上的表格计算第 n 个斐波那契数，时间复杂度是多少？

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

递推式 T(n) = 2T(n/2) + O(n) 的解是：

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

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

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

旅行商问题如何分类？

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

如果有人为某个 NP 完全问题找到了多项式时间算法，会有什么结果？

  1. A停机问题将变得可判定
  2. B只有那一个问题会进入 P
  3. C所有指数时间算法都会立即变成线性时间
  4. DNP 中的每个问题都能在多项式时间内求解，因此 P = NP

答案

  1. 1. D · O(n)
  2. 2. A · 反复找出未排序部分的最小值，并把它交换到前面
  3. 3. D · 在给定的规模为 n 的输入分布上的期望时间
  4. 4. D · O(n)
  5. 5. B · O(n log n)
  6. 6. A · O(n)
  7. 7. B · 判定版本是 NP 完全的，优化版本是 NP 难的
  8. 8. D · NP 中的每个问题都能在多项式时间内求解，因此 P = NP

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