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

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

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

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

姓名: ____________________   日期: ____________

1.简单

什么是记忆化（memoisation）？

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

一个 O(n) 算法在 n = 100 万时需要 3 秒。n = 200 万时大约需要多长时间？

  1. A9 秒
  2. B12 秒
  3. C6 秒
  4. D3 秒
3.简单

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

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

在一个有序数组中，你从两端各放一个指针向内移动，寻找和为目标值的两个元素。时间复杂度是多少？

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

贪心算法（greedy algorithm）：

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

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

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

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

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

要证明一个新问题 X 是 NP 难（NP-hard）的，必须做什么？

  1. A证明 X 对于小规模输入没有多项式算法
  2. B把一个已知的 NP 难问题在多项式时间内归约到 X
  3. C证明 X 能在多项式时间内被验证
  4. D把 X 在多项式时间内归约到一个已知的 NP 难问题

答案

  1. 1. A · 存储函数调用的结果，使重复调用能直接从内存中得到答案
  2. 2. C · 6 秒
  3. 3. D · O(log n)
  4. 4. D · O(n)
  5. 5. A · 在每一步都做出局部最优的选择
  6. 6. B · 它的子问题不重叠，因此没有可以复用的结果
  7. 7. C · 快速选择的期望时间为 O(n)，而中位数的中位数法保证最坏情况为 O(n)
  8. 8. B · 把一个已知的 NP 难问题在多项式时间内归约到 X

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