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

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

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

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

姓名: ____________________   日期: ____________

1.简单

插入排序（insertion sort）的最坏情况时间复杂度是多少？

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

什么是蛮力算法（brute-force algorithm）？

  1. A尝试所有可能的候选解的算法
  2. B在多个处理器上运行的算法
  3. C随机猜测答案的算法
  4. D总是使用递归的算法
3.简单

O(2ⁿ) 的增长称为什么？

  1. A多项式级
  2. B指数级
  3. C线性
  4. D对数级
4.中等

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

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

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

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

为什么在 Big O 中通常省略对数的底，例如写成 O(log n)？

  1. A对数总是被四舍五入为整数
  2. B底只在 n 很小时才有影响
  3. C计算机科学中所有对数的底都是 10，所以可以省略
  4. D不同底的对数之间只相差一个常数因子
7.困难

Karatsuba 乘法满足 T(n) = 3T(n/2) + O(n)。它的解是什么？

  1. AΘ(n log n)
  2. BΘ(nlog₂ 3)，约为 n1.585
  3. CΘ(n3)
  4. DΘ(n²)
8.困难

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

  1. An! 是 O(n²)
  2. B2ⁿ 比 n! 增长得快
  3. C两者以相同的速率增长
  4. Dn! 比 2ⁿ 增长得快

答案

  1. 1. B · O(n²)
  2. 2. A · 尝试所有可能的候选解的算法
  3. 3. B · 指数级
  4. 4. D · 约 20 次
  5. 5. A · 已经有序的数组
  6. 6. D · 不同底的对数之间只相差一个常数因子
  7. 7. B · Θ(nlog₂ 3)，约为 n1.585
  8. 8. D · n! 比 2ⁿ 增长得快

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