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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

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

f(n) = Θ(g(n)) 是什么意思？

  1. Af 的增长严格慢于 g
  2. Bf 与 g 以相同的速率增长，上下都被 g 的常数倍所界定
  3. C对每个 n，f 总是小于 g，因此 g 是它的上界，但绝不是下界
  4. Df 的增长严格快于 g
3.简单

下列哪个运行时间是多项式的？

  1. AO(nⁿ)
  2. BO(n³)
  3. CO(2ⁿ)
  4. DO(n!)
4.中等

在边权非负的图中，哪种算法用于求单源最短路径？

  1. AKruskal 算法
  2. B深度优先搜索（DFS）
  3. CDijkstra 算法
  4. D任何情况下都必须使用 Bellman–Ford
5.中等

递推式 T(n) = 2T(n − 1) + O(1) 的解是什么？

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

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

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

为什么在单链表上二分查找不能达到 O(log n) 的时间？

  1. A链表无法排序
  2. B链表节点上的比较更慢
  3. C二分查找至少需要两倍的内存
  4. D由于不能按下标直接访问，到达中间元素需要 O(n) 步
8.困难

用自底向上的方法从 n 个无序元素构建二叉堆的时间复杂度是多少？

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

答案

  1. 1. C · O(n²)
  2. 2. B · f 与 g 以相同的速率增长，上下都被 g 的常数倍所界定
  3. 3. B · O(n³)
  4. 4. C · Dijkstra 算法
  5. 5. A · O(2ⁿ)
  6. 6. B · O(n)
  7. 7. D · 由于不能按下标直接访问，到达中间元素需要 O(n) 步
  8. 8. D · O(n)

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