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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

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

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

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

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

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

为什么在 Big O 中通常省略对数的底，例如写成 O(log n)？

  1. A对数总是被四舍五入为整数
  2. B不同底的对数之间只相差一个常数因子
  3. C底只在 n 很小时才有影响
  4. D计算机科学中所有对数的底都是 10，所以可以省略
5.中等

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

  1. A常数
  2. B指数级
  3. C线性
  4. D对数级
6.中等

在活动选择问题中，哪条贪心规则总能得到数量最多的互不重叠的活动？

  1. A先选择最短的活动
  2. B先选择与其他活动重叠最少的活动，然后在与之相容的活动中重复这一步
  3. C选择最早结束的活动，然后在与之相容的活动中重复这一步
  4. D选择最早开始的活动
7.困难

在有 V 个顶点、E 条边的图上，使用二叉堆的 Dijkstra 算法运行时间是多少？

  1. AO(V³)
  2. BO(V × E)
  3. CO(V + E)
  4. DO((V + E) log V)
8.困难

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

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

答案

  1. 1. B · 冒泡排序（Bubble sort）
  2. 2. B · O(n²)
  3. 3. A · 数组必须有序
  4. 4. B · 不同底的对数之间只相差一个常数因子
  5. 5. B · 指数级
  6. 6. C · 选择最早结束的活动，然后在与之相容的活动中重复这一步
  7. 7. D · O((V + E) log V)
  8. 8. D · W 是一个数值，因此运行时间相对于表示 W 所需的位数是指数级的

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