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

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

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

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

姓名: ____________________   日期: ____________

1.简单

递归函数的基本情况是什么？

  1. A函数的第一行
  2. B无需再进行递归调用就能直接给出答案的情况
  3. C输入最大的情况，它在任何递归调用之前就被处理
  4. D使用内存最多的那次调用
2.简单

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

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

哪种排序算法选择一个基准，并把数组划分为较小元素和较大元素两部分？

  1. A冒泡排序
  2. B归并排序
  3. C快速排序
  4. D插入排序
4.中等

用自底向上的表格计算第 n 个斐波那契数，时间复杂度是多少？

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

下面代码的时间复杂度是多少：for i = 1 to n: (j = 1; while j < n: j = j × 2)？

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

在无权图上进行广度优先搜索（BFS）可以求出：

  1. A从起始节点出发、按边数计的最短路径
  2. B含负权重边的图中的最短路径
  3. C所有图的拓扑序
  4. D最小生成树
7.困难

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

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

关于 log(n!)，哪个界是正确的？

  1. AΘ(n)
  2. BΘ(log n)
  3. CΘ(n²)
  4. DΘ(n log n)

答案

  1. 1. B · 无需再进行递归调用就能直接给出答案的情况
  2. 2. C · O(1)
  3. 3. C · 快速排序
  4. 4. C · O(n)
  5. 5. B · O(n log n)
  6. 6. A · 从起始节点出发、按边数计的最短路径
  7. 7. D · O(n)
  8. 8. D · Θ(n log n)

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