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

如果一个操作的运行时间是 O(1)，这意味着什么？

1. A它每秒运行时间恰好处理一个元素
2. B它总是恰好花费一秒
3. C它只能运行一次
4. D它的运行时间不随输入规模增长

归并排序的最坏情况时间复杂度是多少？

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

在 n 个数的无序数组中找出最大值的时间复杂度是多少？

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

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

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

快速排序的最坏情况时间复杂度是多少？

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

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

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

关于 log(n!)，哪个界是正确的？

1. AΘ(log n)
2. BΘ(n²)
3. CΘ(n)
4. DΘ(n log n)

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

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