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

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

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

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

姓名: ____________________   日期: ____________

1.简单

当 n 变大时，下列哪一项增长最慢？

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

哪种排序算法会反复交换顺序错误的相邻元素？

  1. A堆排序（Heap sort）
  2. B冒泡排序（Bubble sort）
  3. C归并排序（Merge sort）
  4. D快速排序（Quicksort）
3.简单

归并排序采用哪种设计策略？

  1. A分治法（divide and conquer）
  2. B动态规划
  3. C蛮力法
  4. D贪心选择
4.中等

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

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

说一个 O(n²) 算法也是 O(n³)，这正确吗？

  1. A正确，因为 Big O 是上界，而 n² 的增长不比 n³ 快
  2. B不正确，因为 Big O 必须始终给出函数的确切增长率
  3. C正确，但仅当 n 小于 100 时
  4. D不正确，因为当 n 很大时 n³ 小于 n²
6.中等

贪心算法（greedy algorithm）：

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

要证明一个新问题 X 是 NP 难（NP-hard）的，必须做什么？

  1. A证明 X 能在多项式时间内被验证
  2. B证明 X 对于小规模输入没有多项式算法
  3. C把一个已知的 NP 难问题在多项式时间内归约到 X
  4. D把 X 在多项式时间内归约到一个已知的 NP 难问题
8.困难

Held–Karp 动态规划算法能精确求解旅行商问题。对 n 个城市，它的运行时间是多少？

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

答案

  1. 1. D · O(log n)
  2. 2. B · 冒泡排序（Bubble sort）
  3. 3. A · 分治法（divide and conquer）
  4. 4. C · O(n)
  5. 5. A · 正确，因为 Big O 是上界，而 n² 的增长不比 n³ 快
  6. 6. A · 在每一步都做出局部最优的选择
  7. 7. C · 把一个已知的 NP 难问题在多项式时间内归约到 X
  8. 8. A · O(n² 2ⁿ)

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