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

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

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

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

姓名: ____________________   日期: ____________

1.简单

在 n 个数的无序数组中找出最大值的时间复杂度是多少？

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

如果一个操作的运行时间是 O(1)，这意味着什么？

  1. A它总是恰好花费一秒
  2. B它只能运行一次
  3. C它的运行时间不随输入规模增长
  4. D它每秒运行时间恰好处理一个元素
3.简单

哪种排序算法会反复交换顺序错误的相邻元素？

  1. A快速排序（Quicksort）
  2. B归并排序（Merge sort）
  3. C冒泡排序（Bubble sort）
  4. D堆排序（Heap sort）
4.中等

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

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

说一个 O(n²) 算法也是 O(n³)，这正确吗？

  1. A正确，但仅当 n 小于 100 时
  2. B不正确，因为当 n 很大时 n³ 小于 n²
  3. C正确，因为 Big O 是上界，而 n² 的增长不比 n³ 快
  4. D不正确，因为 Big O 必须始终给出函数的确切增长率
6.中等

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

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

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

  1. A能由确定性算法在多项式时间内求解的判定问题
  2. B在每台计算机上都需要指数时间的问题
  3. C其解可以被验证、但绝不能在多项式时间内找到的问题
  4. D能够并行求解的问题
8.困难

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

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

答案

  1. 1. C · O(n)
  2. 2. C · 它的运行时间不随输入规模增长
  3. 3. C · 冒泡排序（Bubble sort）
  4. 4. B · O(n)
  5. 5. C · 正确，因为 Big O 是上界，而 n² 的增长不比 n³ 快
  6. 6. D · O(n³)
  7. 7. A · 能由确定性算法在多项式时间内求解的判定问题
  8. 8. D · 分数背包问题，物品可以分割

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