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

当 n 很大时，哪个复杂度类增长最快？

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

分治算法的三个步骤是什么？

1. A读取、计算、写入
2. B排序、查找、返回
3. C猜测、检查、重复
4. D分解、解决、合并

空间复杂度衡量的是：

1. A代码的行数
2. B程序编译后程序文件占用的磁盘空间
3. C随着输入增大，算法所需的内存量
4. D计算机的物理尺寸

对 n 个 k 进制、d 位的整数进行 LSD 基数排序（radix sort），运行时间是多少？

1. AO(n²)
2. BO(n log n)
3. CO(dn log k)
4. DO(d(n + k))

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

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

递推式 T(n) = 2T(n/2) + O(n) 的解是：

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

对于哪种背包问题变体，贪心规则"按单位重量价值的顺序取物品"总能给出最优解？

1. A两种变体都不可以
2. B分数背包问题，物品可以分割
3. C0/1 背包问题，物品必须整个拿取
4. D两种变体都可以

停机问题（halting problem）表明：

1. A不存在一种算法能对所有程序和输入判定其是否会停机
2. B每个程序最终都会停机
3. C应当避免使用循环
4. D有些程序在更快的计算机上运行得更快，所以是否停机取决于硬件