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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

  1. A3 秒
  2. B6 秒
  3. C9 秒
  4. D12 秒
2.简单

哪种记号表示增长的下界？

  1. AO（Big O）
  2. BΘ（Big Theta）
  3. CΩ（Big Omega）
  4. Do（little o）
3.简单

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

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

为什么动态规划不能真正加速归并排序？

  1. A动态规划只适用于图问题，不适用于数组
  2. B归并排序没有递归结构
  3. C归并排序已经是 O(n)
  4. D它的子问题不重叠，因此没有可以复用的结果
5.中等

当问题具有以下特征时，动态规划（dynamic programming）很有用：

  1. A重叠子问题和最优子结构
  2. B完全没有子问题，因此一步就能解决
  3. C只有一个循环
  4. D只有随机输入
6.中等

快速排序总是使用第一个元素作为基准。它在哪种输入上表现出最坏情况？

  1. A长度为 2 的数组
  2. B随机顺序的数组
  3. C所有元素都不相同的数组
  4. D已经有序的数组
7.困难

停机问题（halting problem）表明：

  1. A不存在一种算法能对所有程序和输入判定其是否会停机
  2. B应当避免使用循环
  3. C每个程序最终都会停机
  4. D有些程序在更快的计算机上运行得更快，所以是否停机取决于硬件
8.困难

当 n 很大时，n! 与 2ⁿ 相比如何？

  1. A2ⁿ 比 n! 增长得快
  2. Bn! 是 O(n²)
  3. Cn! 比 2ⁿ 增长得快
  4. D两者以相同的速率增长

答案

  1. 1. B · 6 秒
  2. 2. C · Ω（Big Omega）
  3. 3. D · O(n)
  4. 4. D · 它的子问题不重叠，因此没有可以复用的结果
  5. 5. A · 重叠子问题和最优子结构
  6. 6. D · 已经有序的数组
  7. 7. A · 不存在一种算法能对所有程序和输入判定其是否会停机
  8. 8. C · n! 比 2ⁿ 增长得快

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