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

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

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

在以邻接表存储的图上进行深度优先搜索，时间复杂度是多少？

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

什么是蛮力算法（brute-force algorithm）？

1. A总是使用递归的算法
2. B尝试所有可能的候选解的算法
3. C在多个处理器上运行的算法
4. D随机猜测答案的算法

你对一个 n 个元素的数组排序一次，然后用二分查找回答 k 次成员查询。总代价是多少？

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

Prim 算法如何构建最小生成树？

1. A运行广度优先搜索并保留 BFS 树
2. B把所有边按权重排序，逐条加入，除非会在森林中形成环
3. C从一个起始顶点开始扩展一棵树，每次加入离开该树的最便宜的边
4. D不断删除最贵的边，直到没有环为止

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

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

旅行商问题如何分类？

1. A它是不可判定的
2. B它属于 P，因为 Dijkstra 算法通过把每个城市访问一次来求解它
3. C判定版本是 NP 完全的，优化版本是 NP 难的
4. D判定版本属于 P，但优化版本是 NP 完全的

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

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