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

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

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

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

姓名: ____________________   日期: ____________

1.简单

二分查找对输入有什么要求？

  1. A数组必须有序
  2. B数组长度必须是 2 的幂
  3. C数组元素不能超过 1000 个
  4. D数组只能包含正数
2.简单

什么是蛮力算法（brute-force algorithm）？

  1. A尝试所有可能的候选解的算法
  2. B在多个处理器上运行的算法
  3. C随机猜测答案的算法
  4. D总是使用递归的算法
3.简单

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

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

均摊分析衡量的是什么？

  1. A序列中任何位置上单个最昂贵操作的代价
  2. B算法在最好输入上的代价
  3. C在最坏情况的操作序列上，每个操作的平均代价
  4. D在随机输入上的期望代价
5.中等

为什么许多库排序函数在子数组很小时会改用插入排序？

  1. A插入排序在最坏情况下是 O(n log n)
  2. B在大规模输入上，插入排序比任何其他排序算法使用的内存都少
  3. C递归算法无法处理少于 10 个元素的数组
  4. D插入排序开销小，在小规模或几乎有序的输入上很快
6.中等

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

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

不可判定问题与难解问题有什么区别？

  1. A两者都意味着该问题根本没有算法
  2. B不可判定问题没有任何能处理所有输入的算法，而难解问题有算法，但太慢
  3. C不可判定问题属于 NP，而难解问题属于 P
  4. D难解问题无法被任何算法求解，而不可判定问题只需要指数时间
8.困难

如果有人为某个 NP 完全问题找到了多项式时间算法，会有什么结果？

  1. A只有那一个问题会进入 P
  2. B停机问题将变得可判定
  3. C所有指数时间算法都会立即变成线性时间
  4. DNP 中的每个问题都能在多项式时间内求解，因此 P = NP

答案

  1. 1. A · 数组必须有序
  2. 2. A · 尝试所有可能的候选解的算法
  3. 3. C · O(n²)
  4. 4. C · 在最坏情况的操作序列上，每个操作的平均代价
  5. 5. D · 插入排序开销小，在小规模或几乎有序的输入上很快
  6. 6. B · O(1)
  7. 7. B · 不可判定问题没有任何能处理所有输入的算法，而难解问题有算法，但太慢
  8. 8. D · NP 中的每个问题都能在多项式时间内求解，因此 P = NP

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