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

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

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

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

姓名: ____________________   日期: ____________

1.简单

当 n 变大时，下列哪一项增长最慢？

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

空间复杂度衡量的是：

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

分治算法的三个步骤是什么？

  1. A分解、解决、合并
  2. B读取、计算、写入
  3. C猜测、检查、重复
  4. D排序、查找、返回
4.中等

哪种排序算法是稳定的？

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

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

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

简单的递归阶乘函数 fact(n) = n × fact(n − 1) 使用多少栈空间？

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

拓扑排序只适用于：

  1. A完全图
  2. B带负权重的图
  3. C无向图
  4. D有向无环图（DAG）
8.困难

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

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

答案

  1. 1. D · O(log n)
  2. 2. C · 随着输入增大，算法所需的内存量
  3. 3. A · 分解、解决、合并
  4. 4. A · 归并排序
  5. 5. B · O(mn)
  6. 6. C · O(n)
  7. 7. D · 有向无环图（DAG）
  8. 8. C · 给定证书时，其"是"答案能在多项式时间内验证的判定问题

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