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

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

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

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

姓名: ____________________   日期: ____________

1.简单

O(2ⁿ) 的增长称为什么？

  1. A多项式级
  2. B线性
  3. C对数级
  4. D指数级
2.简单

对范围在 0 到 k 之间的 n 个整数进行计数排序（counting sort），运行时间是多少？

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

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

  1. AΘ（Big Theta）
  2. BΩ（Big Omega）
  3. CO（Big O）
  4. Do（little o）
4.中等

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

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

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

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

朴素递归斐波那契（fib(n) = fib(n−1) + fib(n−2)）的时间复杂度是：

  1. A指数级
  2. B常数
  3. C对数级
  4. D线性
7.困难

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

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

关于类 NP 的哪个定义是正确的？

  1. A给定证书时，其"是"答案能在多项式时间内验证的判定问题
  2. B任何算法都无法求解的问题
  3. C非多项式的问题
  4. D不能在多项式时间内求解的问题

答案

  1. 1. D · 指数级
  2. 2. C · O(n + k)
  3. 3. B · Ω（Big Omega）
  4. 4. D · 最优解可以由其子问题的最优解构造出来
  5. 5. C · O(1)
  6. 6. A · 指数级
  7. 7. B · 至多是最小顶点覆盖大小的两倍
  8. 8. A · 给定证书时，其"是"答案能在多项式时间内验证的判定问题

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