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

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

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

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

姓名: ____________________   日期: ____________

1.简单

算法的最坏情况运行时间描述的是什么？

  1. A在慢速计算机上所需的时间
  2. B在最小输入上所需的时间
  3. C在所有规模为 n 的输入上所需的最长时间
  4. D在规模为 n 的随机输入上所需的期望时间
2.简单

log₂ 1024 等于多少？

  1. A32
  2. B12
  3. C512
  4. D10
3.简单

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

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

简单的递归阶乘函数 fact(n) = n × fact(n − 1) 使用多少栈空间？

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

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

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

一个函数先运行一个 n 次迭代的循环，然后再单独运行另一个 n 次迭代的循环。它的时间复杂度是多少？

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

旅行商问题如何分类？

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

哪种技术能使快速排序在任意输入上的期望运行时间为 O(n log n)？

  1. A在运行快速排序前先对输入排序
  2. B总是选择第一个元素
  3. C只对左侧进行递归
  4. D均匀随机地选择基准

答案

  1. 1. C · 在所有规模为 n 的输入上所需的最长时间
  2. 2. D · 10
  3. 3. D · O(log n)
  4. 4. B · O(n)
  5. 5. C · O(mn)
  6. 6. C · O(n)
  7. 7. B · 判定版本是 NP 完全的，优化版本是 NP 难的
  8. 8. D · 均匀随机地选择基准

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