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

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

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

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

姓名: ____________________   日期: ____________

1.简单

选择排序（selection sort）是如何工作的？

  1. A反复找出未排序部分的最小值，并把它交换到前面
  2. B反复交换顺序错误的相邻元素
  3. C把数组对半分开再合并
  4. D通过移动元素，把每个元素插入到不断增长的有序部分中
2.简单

3n² + 5n + 2 的 Big O 是什么？

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

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

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

快速排序总是使用第一个元素作为基准。它在哪种输入上表现出最坏情况？

  1. A随机顺序的数组
  2. B长度为 2 的数组
  3. C已经有序的数组
  4. D所有元素都不相同的数组
5.中等

下面代码的时间复杂度是多少：for i = 1 to n: for j = 1 to i: 执行 O(1) 的工作？

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

朴素递归斐波那契（fib(n) = fib(n−1) + fib(n−2)）的时间复杂度是：

  1. A指数级
  2. B常数
  3. C对数级
  4. D线性
7.困难

旅行商问题如何分类？

  1. A判定版本是 NP 完全的，优化版本是 NP 难的
  2. B它属于 P，因为 Dijkstra 算法通过把每个城市访问一次来求解它
  3. C判定版本属于 P，但优化版本是 NP 完全的
  4. D它是不可判定的
8.困难

用动态规划求解 0/1 背包问题需要 O(nW) 时间。为什么称之为伪多项式（pseudo-polynomial）？

  1. A因为该算法是随机化的，其运行时间随每个输入而变化
  2. B因为它只适用于 W = 0
  3. CW 是一个数值，因此运行时间相对于表示 W 所需的位数是指数级的
  4. D因为 n 总是很小

答案

  1. 1. A · 反复找出未排序部分的最小值，并把它交换到前面
  2. 2. C · O(n²)
  3. 3. C · 它的运行时间不随输入规模增长
  4. 4. C · 已经有序的数组
  5. 5. C · O(n²)
  6. 6. A · 指数级
  7. 7. A · 判定版本是 NP 完全的，优化版本是 NP 难的
  8. 8. C · W 是一个数值，因此运行时间相对于表示 W 所需的位数是指数级的

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