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

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

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

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

姓名: ____________________   日期: ____________

1.简单

什么是递归？

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

在有序数组上进行二分查找（binary search）的时间复杂度是多少？

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

log₂ 1024 等于多少？

  1. A10
  2. B12
  3. C32
  4. D512
4.中等

一个问题具有最优子结构是什么意思？

  1. A最优解可以由其子问题的最优解构造出来
  2. B该问题可以在常数时间内求解
  3. C每个子问题的规模都相同
  4. D该问题恰好有一个最优解，所有子问题共享这个解
5.中等

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

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

贪心算法（greedy algorithm）：

  1. A尝试所有可能的解
  2. B只使用递归
  3. C总能给出最优解
  4. D在每一步都做出局部最优的选择
7.困难

旅行商问题如何分类？

  1. A判定版本属于 P，但优化版本是 NP 完全的
  2. B它属于 P，因为 Dijkstra 算法通过把每个城市访问一次来求解它
  3. C它是不可判定的
  4. D判定版本是 NP 完全的，优化版本是 NP 难的
8.困难

为什么哈希表的平均查找时间是 O(1)，而最坏情况是 O(n)？

  1. A键必须先排序
  2. B数组的访问时间是 O(n)
  3. C哈希函数运行很慢
  4. D许多键可能冲突（collision）到同一个桶中

答案

  1. 1. A · 在更小的输入上调用自身的函数
  2. 2. B · O(log n)
  3. 3. A · 10
  4. 4. A · 最优解可以由其子问题的最优解构造出来
  5. 5. D · 插入排序开销小，在小规模或几乎有序的输入上很快
  6. 6. D · 在每一步都做出局部最优的选择
  7. 7. D · 判定版本是 NP 完全的，优化版本是 NP 难的
  8. 8. D · 许多键可能冲突（collision）到同一个桶中

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