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

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

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

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

姓名: ____________________   日期: ____________

1.简单

哪种记号表示增长的上界？

  1. ABig O
  2. BLittle omega
  3. CBig Theta
  4. DBig Omega
2.简单

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

  1. A8 秒
  2. B4 秒
  3. C1 秒
  4. D2 秒
3.简单

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

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

为什么许多库排序函数在子数组很小时会改用插入排序？

  1. A在大规模输入上，插入排序比任何其他排序算法使用的内存都少
  2. B递归算法无法处理少于 10 个元素的数组
  3. C插入排序在最坏情况下是 O(n log n)
  4. D插入排序开销小，在小规模或几乎有序的输入上很快
5.中等

当问题具有以下特征时，动态规划（dynamic programming）很有用：

  1. A只有一个循环
  2. B重叠子问题和最优子结构
  3. C完全没有子问题，因此一步就能解决
  4. D只有随机输入
6.中等

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

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

取一个极大匹配中每条边的两个端点，可以得到一个顶点覆盖。这个覆盖有多好？

  1. A与最优解相比质量未知
  2. B至多是最小顶点覆盖大小的两倍
  3. C至多是最小值的 log n 倍
  4. D总是一个最小顶点覆盖
8.困难

关于在无序数组中选择第 k 小的元素，下列哪个说法是正确的？

  1. A快速选择的最坏情况为 O(log n)，因为它只对枢轴的一侧递归
  2. B选择只能在 O(n²) 内完成
  3. C选择总是需要 Ω(n log n)，因为必须先排序
  4. D快速选择的期望时间为 O(n)，而中位数的中位数法保证最坏情况为 O(n)

答案

  1. 1. A · Big O
  2. 2. B · 4 秒
  3. 3. A · O(n³)
  4. 4. D · 插入排序开销小，在小规模或几乎有序的输入上很快
  5. 5. B · 重叠子问题和最优子结构
  6. 6. C · 选择最早结束的活动，然后在与之相容的活动中重复这一步
  7. 7. B · 至多是最小顶点覆盖大小的两倍
  8. 8. D · 快速选择的期望时间为 O(n)，而中位数的中位数法保证最坏情况为 O(n)

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