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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

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

通过下标访问数组中的元素需要：

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

平均情况运行时间描述的是什么？

  1. A在最常见的计算机上所需的时间
  2. B平均长度的输入所需的时间
  3. C在给定的规模为 n 的输入分布上的期望时间
  4. D最好情况与最坏情况运行时间之间的中间值
4.中等

用自底向上的表格计算第 n 个斐波那契数，时间复杂度是多少？

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

哪种排序算法是稳定的？

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

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

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

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

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

插入排序在有序输入上运行时间为 O(n)。这与比较排序的 Ω(n log n) 下界矛盾吗？

  1. A矛盾，因此这个下界是错的
  2. B矛盾，但仅对长度小于 100 的数组
  3. C不矛盾，下界针对的是所有输入中的最坏情况，而不是每一个输入
  4. D不矛盾，因为插入排序不是比较排序

答案

  1. 1. D · O(log n)
  2. 2. A · O(1)
  3. 3. C · 在给定的规模为 n 的输入分布上的期望时间
  4. 4. A · O(n)
  5. 5. D · 归并排序
  6. 6. A · O(1)
  7. 7. A · 给定证书时，其"是"答案能在多项式时间内验证的判定问题
  8. 8. C · 不矛盾，下界针对的是所有输入中的最坏情况，而不是每一个输入

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