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

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

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

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

姓名: ____________________   日期: ____________

1.简单

在有序数组上进行二分查找（binary search）的时间复杂度是多少？

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

通过下标访问数组中的元素需要：

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

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

  1. AO（Big O）
  2. BΩ（Big Omega）
  3. Co（little o）
  4. DΘ（Big Theta）
4.中等

对长度为 m 和 n 的两个字符串求最长公共子序列，标准动态规划算法的时间复杂度是多少？

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

用标准的三重循环计算两个 n × n 矩阵的乘积，时间复杂度是多少？

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

一个函数先运行一个 n 次迭代的循环，然后再单独运行另一个 n 次迭代的循环。它的时间复杂度是多少？

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

用一个只保留最后两个值的循环计算第 n 个斐波那契数，时间和空间代价各是多少？

  1. AO(n) 时间和 O(1) 空间
  2. BO(log n) 时间和 O(n) 空间
  3. CO(2ⁿ) 时间和 O(1) 空间
  4. DO(n) 时间和 O(n) 空间
8.困难

22n 属于 O(2ⁿ) 吗？

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

答案

  1. 1. D · O(log n)
  2. 2. D · O(1)
  3. 3. B · Ω（Big Omega）
  4. 4. C · O(mn)
  5. 5. B · O(n³)
  6. 6. A · O(n)
  7. 7. A · O(n) 时间和 O(1) 空间
  8. 8. C · 不属于，因为 22n = 4ⁿ，而 4ⁿ / 2ⁿ = 2ⁿ 无界地增长

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