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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

  1. AO(nⁿ)
  2. BO(n!)
  3. CO(2ⁿ)
  4. DO(n³)
2.简单

3n² + 5n + 2 的 Big O 是什么？

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

什么是递归？

  1. A一种数据结构
  2. B永远不会结束的循环
  3. C在更小的输入上调用自身的函数
  4. D一种排序方法
4.中等

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

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

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

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

对 n 个元素的数组进行归并排序，递归共有多少层？

  1. A约 log₂ n 层
  2. B约 n / 2 层
  3. C约 √n 层
  4. D约 n 层
7.困难

哪种技术能使快速排序在任意输入上的期望运行时间为 O(n log n)？

  1. A在运行快速排序前先对输入排序
  2. B只对左侧进行递归
  3. C均匀随机地选择基准
  4. D总是选择第一个元素
8.困难

哪种算法通过反复加入不会形成环的最便宜的边来求最小生成树？

  1. AFloyd–Warshall
  2. BDijkstra 算法
  3. CKruskal 算法
  4. D从一个节点出发的 Prim 算法

答案

  1. 1. D · O(n³)
  2. 2. C · O(n²)
  3. 3. C · 在更小的输入上调用自身的函数
  4. 4. B · O(n)
  5. 5. A · O(n log n + k log n)
  6. 6. A · 约 log₂ n 层
  7. 7. C · 均匀随机地选择基准
  8. 8. C · Kruskal 算法

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