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

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

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

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

姓名: ____________________   日期: ____________

1.简单

一个包含两层嵌套循环、每层都执行 n 次的算法，通常具有哪种复杂度？

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

什么是算法？

  1. A一种为书写数学公式而设计的编程语言
  2. B任何带有图形界面的计算机程序
  3. C一种存储数字的数据结构
  4. D解决问题的、由有限个明确定义的步骤组成的序列
3.简单

空间复杂度衡量的是：

  1. A计算机的物理尺寸
  2. B代码的行数
  3. C程序编译后程序文件占用的磁盘空间
  4. D随着输入增大，算法所需的内存量
4.中等

当问题具有以下特征时，动态规划（dynamic programming）很有用：

  1. A只有随机输入
  2. B只有一个循环
  3. C重叠子问题和最优子结构
  4. D完全没有子问题，因此一步就能解决
5.中等

对长度为 m 和 n 的两个字符串求最长公共子序列，标准动态规划算法的时间复杂度是多少？

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

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

  1. AO(n)
  2. BO(log n)
  3. CO(n log n)
  4. DO(n²)
7.困难

下列哪个可满足性问题已知可以在多项式时间内求解？

  1. A2-SAT，每个子句至多有两个文字
  2. B电路可满足性问题
  3. C合取范式公式上的一般 SAT
  4. D3-SAT，每个子句恰好有三个文字
8.困难

对于哪种背包问题变体，贪心规则"按单位重量价值的顺序取物品"总能给出最优解？

  1. A两种变体都可以
  2. B分数背包问题，物品可以分割
  3. C两种变体都不可以
  4. D0/1 背包问题，物品必须整个拿取

答案

  1. 1. B · O(n²)
  2. 2. D · 解决问题的、由有限个明确定义的步骤组成的序列
  3. 3. D · 随着输入增大，算法所需的内存量
  4. 4. C · 重叠子问题和最优子结构
  5. 5. A · O(mn)
  6. 6. A · O(n)
  7. 7. A · 2-SAT，每个子句至多有两个文字
  8. 8. B · 分数背包问题，物品可以分割

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