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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

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

一个包含两层嵌套循环、每层都执行 n 次的算法，通常具有哪种复杂度？

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

在 n 个数的无序数组中找出最大值的时间复杂度是多少？

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

简单的递归阶乘函数 fact(n) = n × fact(n − 1) 使用多少栈空间？

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

硬币面值为 1、3 和 4，金额为 6，贪心的"先取最大硬币"方法使用多少枚硬币？与最优解相比如何？

  1. A贪心用 3 枚；最优解是 2 枚
  2. B贪心用 4 枚；最优解是 3 枚
  3. C贪心用 2 枚；最优解是 2 枚
  4. D贪心用 3 枚；最优解是 3 枚
6.中等

下面代码的时间复杂度是多少：for i = 1 to n: for j = 1 to i: 执行 O(1) 的工作？

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

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

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

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

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

答案

  1. 1. A · O(n²)
  2. 2. A · O(n²)
  3. 3. B · O(n)
  4. 4. D · O(n)
  5. 5. A · 贪心用 3 枚；最优解是 2 枚
  6. 6. C · O(n²)
  7. 7. D · Θ(nlog₂ 3)，约为 n1.585
  8. 8. D · O(n) 时间和 O(1) 空间

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