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

什么是算法？

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

一个算法的运行时间是 O(n)。这种增长称为什么？

1. A平方
2. B线性
3. C常数
4. D对数

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

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

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

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

一个问题具有最优子结构是什么意思？

1. A该问题恰好有一个最优解，所有子问题共享这个解
2. B该问题可以在常数时间内求解
3. C每个子问题的规模都相同
4. D最优解可以由其子问题的最优解构造出来

硬币面值为 1、3 和 4，金额为 6，贪心的"先取最大硬币"方法使用多少枚硬币？与最优解相比如何？

1. A贪心用 4 枚；最优解是 3 枚
2. B贪心用 2 枚；最优解是 2 枚
3. C贪心用 3 枚；最优解是 3 枚
4. D贪心用 3 枚；最优解是 2 枚

关于类 NP 的哪个定义是正确的？

1. A非多项式的问题
2. B给定证书时，其"是"答案能在多项式时间内验证的判定问题
3. C不能在多项式时间内求解的问题
4. D任何算法都无法求解的问题

当 n 很大时，n! 与 2ⁿ 相比如何？

1. A2ⁿ 比 n! 增长得快
2. Bn! 比 2ⁿ 增长得快
3. C两者以相同的速率增长
4. Dn! 是 O(n²)