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

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

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

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

姓名: ____________________   日期: ____________

1.简单

一个 O(n²) 算法在 n = 1000 时需要 1 秒。n = 2000 时大约需要多长时间？

  1. A4 秒
  2. B8 秒
  3. C1 秒
  4. D2 秒
2.简单

哪种排序算法会反复交换顺序错误的相邻元素？

  1. A快速排序（Quicksort）
  2. B归并排序（Merge sort）
  3. C堆排序（Heap sort）
  4. D冒泡排序（Bubble sort）
3.简单

当 n 很大时，哪个复杂度类增长最快？

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

在活动选择问题中，哪条贪心规则总能得到数量最多的互不重叠的活动？

  1. A先选择最短的活动
  2. B选择最早开始的活动
  3. C选择最早结束的活动，然后在与之相容的活动中重复这一步
  4. D先选择与其他活动重叠最少的活动，然后在与之相容的活动中重复这一步
5.中等

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

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

基于比较的排序在最坏情况下的下界是：

  1. AΩ(n²)
  2. BΩ(log n)
  3. CΩ(n log n)
  4. DΩ(n)
7.困难

插入排序在有序输入上运行时间为 O(n)。这与比较排序的 Ω(n log n) 下界矛盾吗？

  1. A不矛盾，下界针对的是所有输入中的最坏情况，而不是每一个输入
  2. B不矛盾，因为插入排序不是比较排序
  3. C矛盾，因此这个下界是错的
  4. D矛盾，但仅对长度小于 100 的数组
8.困难

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

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

答案

  1. 1. A · 4 秒
  2. 2. D · 冒泡排序（Bubble sort）
  3. 3. B · O(2ⁿ)
  4. 4. C · 选择最早结束的活动，然后在与之相容的活动中重复这一步
  5. 5. B · O(n)
  6. 6. C · Ω(n log n)
  7. 7. A · 不矛盾，下界针对的是所有输入中的最坏情况，而不是每一个输入
  8. 8. B · O(n)

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