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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

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

什么是递归？

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

通过下标访问数组中的元素需要：

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

用标准的三重循环计算两个 n × n 矩阵的乘积，时间复杂度是多少？

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

对于在满时将容量翻倍的动态数组，追加元素的均摊（amortised）时间复杂度是多少？

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

哪种排序算法是稳定的？

  1. A选择排序（常见版本）
  2. B堆排序
  3. C归并排序
  4. D快速排序（常见的原地版本）
7.困难

一个问题是 NP 完全（NP-complete）的，当且仅当它：

  1. A可以在多项式时间内解决
  2. B不可能被解决
  3. C属于 NP，且所有 NP 问题都能在多项式时间内归约到它
  4. D不属于 NP，但比所有 NP 问题都难，例如停机问题
8.困难

用动态规划求解 0/1 背包问题需要 O(nW) 时间。为什么称之为伪多项式（pseudo-polynomial）？

  1. AW 是一个数值，因此运行时间相对于表示 W 所需的位数是指数级的
  2. B因为它只适用于 W = 0
  3. C因为 n 总是很小
  4. D因为该算法是随机化的，其运行时间随每个输入而变化

答案

  1. 1. B · 分治法（divide and conquer）
  2. 2. A · 在更小的输入上调用自身的函数
  3. 3. A · O(1)
  4. 4. D · O(n³)
  5. 5. D · O(1)
  6. 6. C · 归并排序
  7. 7. C · 属于 NP，且所有 NP 问题都能在多项式时间内归约到它
  8. 8. A · W 是一个数值，因此运行时间相对于表示 W 所需的位数是指数级的

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