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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

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

一个算法的运行时间是 O(n)。这种增长称为什么？

  1. A平方
  2. B对数
  3. C常数
  4. D线性
3.简单

归并排序的最坏情况时间复杂度是多少？

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

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

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

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

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

快速排序的最坏情况时间复杂度是多少？

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

在有 V 个顶点、E 条边的图上，使用二叉堆的 Dijkstra 算法运行时间是多少？

  1. AO(V × E)
  2. BO(V + E)
  3. CO((V + E) log V)
  4. DO(V³)
8.困难

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

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

答案

  1. 1. A · O(n²)
  2. 2. D · 线性
  3. 3. C · O(n log n)
  4. 4. C · 不同底的对数之间只相差一个常数因子
  5. 5. B · 贪心用 3 枚；最优解是 2 枚
  6. 6. C · O(n²)
  7. 7. C · O((V + E) log V)
  8. 8. A · O(n) 时间和 O(1) 空间

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