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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

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

一个 O(n) 算法在 n = 100 万时需要 3 秒。n = 200 万时大约需要多长时间？

  1. A9 秒
  2. B6 秒
  3. C12 秒
  4. D3 秒
3.简单

哪种记号表示增长的下界？

  1. AΩ（Big Omega）
  2. BO（Big O）
  3. CΘ（Big Theta）
  4. Do（little o）
4.中等

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

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

对长度为 m 和 n 的两个字符串求最长公共子序列，标准动态规划算法的时间复杂度是多少？

  1. AO(m + n)
  2. BO(mn)
  3. CO(2m+n)
  4. DO(mn log n)
6.中等

递推式 T(n) = 2T(n/2) + O(n) 的解是：

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

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

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

哪种算法通过反复加入不会形成环的最便宜的边来求最小生成树？

  1. AFloyd–Warshall
  2. BDijkstra 算法
  3. CKruskal 算法
  4. D从一个节点出发的 Prim 算法

答案

  1. 1. D · 分解、解决、合并
  2. 2. B · 6 秒
  3. 3. A · Ω（Big Omega）
  4. 4. B · O(n²)
  5. 5. B · O(mn)
  6. 6. D · O(n log n)
  7. 7. C · O((V + E) log V)
  8. 8. C · Kruskal 算法

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