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

什么是算法？

1. A解决问题的、由有限个明确定义的步骤组成的序列
2. B任何带有图形界面的计算机程序
3. C一种存储数字的数据结构
4. D一种为书写数学公式而设计的编程语言

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

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

空间复杂度衡量的是：

1. A代码的行数
2. B计算机的物理尺寸
3. C随着输入增大，算法所需的内存量
4. D程序编译后程序文件占用的磁盘空间

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

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

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

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

在有 V 个顶点、E 条边的图上，Bellman–Ford 算法的时间复杂度是多少？

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

关于 P 和 NP，下列哪个说法是正确的？

1. ANP 表示“not polynomial”（非多项式）
2. BNP 问题无法被快速验证
3. CP 中的每个问题也都属于 NP
4. D已经证明 P ≠ NP

Strassen 算法在矩阵乘法中对半尺寸的分块只做 7 次而不是 8 次递归乘法。它的运行时间是多少？

1. AΘ(n² log n)
2. BΘ(n²)
3. CΘ(n³)
4. DΘ(n^{log₂ 7})，约为 n^2.81