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

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

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

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

姓名: ____________________   日期: ____________

1.简单

当 n 很大时，哪个复杂度类增长最快？

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

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

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

下列哪个运行时间是多项式的？

  1. AO(2ⁿ)
  2. BO(n³)
  3. CO(nⁿ)
  4. DO(n!)
4.中等

贪心算法（greedy algorithm）：

  1. A在每一步都做出局部最优的选择
  2. B只使用递归
  3. C总能给出最优解
  4. D尝试所有可能的解
5.中等

在包含 1,000,000 个元素的有序数组上，二分查找在最坏情况下大约需要多少次比较？

  1. A约 100 次
  2. B约 1,000 次
  3. C约 20 次
  4. D约 500,000 次
6.中等

下面代码的时间复杂度是多少：for i = 1 to n: (j = 1; while j < n: j = j × 2)？

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

为什么哈希表的平均查找时间是 O(1)，而最坏情况是 O(n)？

  1. A数组的访问时间是 O(n)
  2. B键必须先排序
  3. C哈希函数运行很慢
  4. D许多键可能冲突（collision）到同一个桶中
8.困难

关于类 NP 的哪个定义是正确的？

  1. A任何算法都无法求解的问题
  2. B不能在多项式时间内求解的问题
  3. C非多项式的问题
  4. D给定证书时，其"是"答案能在多项式时间内验证的判定问题

答案

  1. 1. B · O(2ⁿ)
  2. 2. D · 反复找出未排序部分的最小值，并把它交换到前面
  3. 3. B · O(n³)
  4. 4. A · 在每一步都做出局部最优的选择
  5. 5. C · 约 20 次
  6. 6. B · O(n log n)
  7. 7. D · 许多键可能冲突（collision）到同一个桶中
  8. 8. D · 给定证书时，其"是"答案能在多项式时间内验证的判定问题

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