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

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

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

选择排序（selection sort）是如何工作的？

1. A反复交换顺序错误的相邻元素
2. B通过移动元素，把每个元素插入到不断增长的有序部分中
3. C把数组对半分开再合并
4. D反复找出未排序部分的最小值，并把它交换到前面

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

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

贪心算法（greedy algorithm）：

1. A只使用递归
2. B尝试所有可能的解
3. C总能给出最优解
4. D在每一步都做出局部最优的选择

递推式 T(n) = 2T(n/2) + O(1) 的解是什么？

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

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

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

下面代码的时间复杂度是多少：for i = 1 to n: for (j = i; j ≤ n; j = j + i) 执行 O(1) 的工作？

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

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

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