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

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

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

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

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

在有序数组上进行二分查找（binary search）的时间复杂度是多少？

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

关于一个没有可达基本情况的递归函数，下列哪个说法是正确的？

1. A编译器总会把它变成能安全结束的循环
2. B它会不断调用自身，直到调用栈溢出
3. C它的运行时间为 O(1)
4. D它会自动返回 0

在包含 1,000,000 个元素的有序数组上，二分查找在最坏情况下大约需要多少次比较？

1. A约 20 次
2. B约 100 次
3. C约 1,000 次
4. D约 500,000 次

在无权图上进行广度优先搜索（BFS）可以求出：

1. A含负权重边的图中的最短路径
2. B从起始节点出发、按边数计的最短路径
3. C最小生成树
4. D所有图的拓扑序

要证明一个判定问题 X 是 NP 完全的，必须证明哪两点？

1. AX 没有多项式算法，并且 X 是可判定的
2. BX 属于 NP，并且某个已知的 NP 完全问题能在多项式时间内归约到 X
3. CX 属于 P，并且 X 能归约到 SAT
4. DX 能归约到 P 中的某个问题，并且 X 属于 NP

要证明一个新问题 X 是 NP 难（NP-hard）的，必须做什么？

1. A把 X 在多项式时间内归约到一个已知的 NP 难问题
2. B证明 X 对于小规模输入没有多项式算法
3. C证明 X 能在多项式时间内被验证
4. D把一个已知的 NP 难问题在多项式时间内归约到 X