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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

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

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

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

对范围在 0 到 k 之间的 n 个整数进行计数排序（counting sort），运行时间是多少？

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

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

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

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

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

你对一个 n 个元素的数组排序一次，然后用二分查找回答 k 次成员查询。总代价是多少？

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

关于 log(n!)，哪个界是正确的？

  1. AΘ(n²)
  2. BΘ(n log n)
  3. CΘ(log n)
  4. DΘ(n)
8.困难

22n 属于 O(2ⁿ) 吗？

  1. A属于，因为在 Big O 中指数里的常数因子总是被忽略
  2. B不属于，因为 22n = 4ⁿ，而 4ⁿ / 2ⁿ = 2ⁿ 无界地增长
  3. C不属于，因为 22n 增长得比 2ⁿ 慢
  4. D属于，因为两者都是指数级的

答案

  1. 1. B · 指数级
  2. 2. C · Ω（Big Omega）
  3. 3. C · O(n + k)
  4. 4. C · O(n log n)
  5. 5. B · 不同底的对数之间只相差一个常数因子
  6. 6. D · O(n log n + k log n)
  7. 7. B · Θ(n log n)
  8. 8. B · 不属于，因为 22n = 4ⁿ，而 4ⁿ / 2ⁿ = 2ⁿ 无界地增长

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