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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

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

什么是记忆化（memoisation）？

  1. A存储函数调用的结果，使重复调用能直接从内存中得到答案
  2. B函数返回后释放内存
  3. C自动把递归转换为等价的循环，从而不需要调用栈
  4. D在每行代码旁边写注释
3.简单

归并排序采用哪种设计策略？

  1. A贪心选择
  2. B动态规划
  3. C分治法（divide and conquer）
  4. D蛮力法
4.中等

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

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

为什么动态规划不能真正加速归并排序？

  1. A动态规划只适用于图问题，不适用于数组
  2. B归并排序已经是 O(n)
  3. C它的子问题不重叠，因此没有可以复用的结果
  4. D归并排序没有递归结构
6.中等

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

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

递推式 T(n) = 2T(n/2) + n log n 的解是什么？

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

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

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

答案

  1. 1. C · 快速排序
  2. 2. A · 存储函数调用的结果，使重复调用能直接从内存中得到答案
  3. 3. C · 分治法（divide and conquer）
  4. 4. C · 最优解可以由其子问题的最优解构造出来
  5. 5. C · 它的子问题不重叠，因此没有可以复用的结果
  6. 6. C · 约 log₂ n 层
  7. 7. A · Θ(n log² n)
  8. 8. A · 均匀随机地选择基准

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