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

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

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

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

姓名: ____________________   日期: ____________

1.简单

哪种排序算法选择一个基准，并把数组划分为较小元素和较大元素两部分？

  1. A快速排序
  2. B归并排序
  3. C插入排序
  4. D冒泡排序
2.简单

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

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

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

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

快速排序的最坏情况时间复杂度是多少？

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

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

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

对 n 个元素的数组进行归并排序，递归共有多少层？

  1. A约 √n 层
  2. B约 n 层
  3. C约 n / 2 层
  4. D约 log₂ n 层
7.困难

22n 属于 O(2ⁿ) 吗？

  1. A不属于，因为 22n 增长得比 2ⁿ 慢
  2. B不属于，因为 22n = 4ⁿ，而 4ⁿ / 2ⁿ = 2ⁿ 无界地增长
  3. C属于，因为在 Big O 中指数里的常数因子总是被忽略
  4. D属于，因为两者都是指数级的
8.困难

关于在无序数组中选择第 k 小的元素，下列哪个说法是正确的？

  1. A选择只能在 O(n²) 内完成
  2. B快速选择的最坏情况为 O(log n)，因为它只对枢轴的一侧递归
  3. C选择总是需要 Ω(n log n)，因为必须先排序
  4. D快速选择的期望时间为 O(n)，而中位数的中位数法保证最坏情况为 O(n)

答案

  1. 1. A · 快速排序
  2. 2. C · 分解、解决、合并
  3. 3. C · 它的运行时间不随输入规模增长
  4. 4. C · O(n²)
  5. 5. A · O(n³)
  6. 6. D · 约 log₂ n 层
  7. 7. B · 不属于，因为 22n = 4ⁿ，而 4ⁿ / 2ⁿ = 2ⁿ 无界地增长
  8. 8. D · 快速选择的期望时间为 O(n)，而中位数的中位数法保证最坏情况为 O(n)

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