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

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

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

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

姓名: ____________________   日期: ____________

1.简单

一个 O(n) 算法在 n = 100 万时需要 3 秒。n = 200 万时大约需要多长时间？

  1. A12 秒
  2. B3 秒
  3. C6 秒
  4. D9 秒
2.简单

如果一个操作的运行时间是 O(1)，这意味着什么？

  1. A它每秒运行时间恰好处理一个元素
  2. B它只能运行一次
  3. C它的运行时间不随输入规模增长
  4. D它总是恰好花费一秒
3.简单

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

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

为什么许多库排序函数在子数组很小时会改用插入排序？

  1. A插入排序在最坏情况下是 O(n log n)
  2. B在大规模输入上，插入排序比任何其他排序算法使用的内存都少
  3. C递归算法无法处理少于 10 个元素的数组
  4. D插入排序开销小，在小规模或几乎有序的输入上很快
5.中等

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

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

在一个有序数组中，你从两端各放一个指针向内移动，寻找和为目标值的两个元素。时间复杂度是多少？

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

关于 P 和 NP，下列哪个说法是正确的？

  1. ANP 表示“not polynomial”（非多项式）
  2. B已经证明 P ≠ NP
  3. CP 中的每个问题也都属于 NP
  4. DNP 问题无法被快速验证
8.困难

一个问题是 NP 完全（NP-complete）的，当且仅当它：

  1. A不可能被解决
  2. B不属于 NP，但比所有 NP 问题都难，例如停机问题
  3. C可以在多项式时间内解决
  4. D属于 NP，且所有 NP 问题都能在多项式时间内归约到它

答案

  1. 1. C · 6 秒
  2. 2. C · 它的运行时间不随输入规模增长
  3. 3. A · 快速排序
  4. 4. D · 插入排序开销小，在小规模或几乎有序的输入上很快
  5. 5. A · O(n log n)
  6. 6. C · O(n)
  7. 7. C · P 中的每个问题也都属于 NP
  8. 8. D · 属于 NP，且所有 NP 问题都能在多项式时间内归约到它

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