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

平均情况运行时间描述的是什么？

1. A最好情况与最坏情况运行时间之间的中间值
2. B在最常见的计算机上所需的时间
3. C平均长度的输入所需的时间
4. D在给定的规模为 n 的输入分布上的期望时间

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

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

什么是算法？

1. A一种为书写数学公式而设计的编程语言
2. B任何带有图形界面的计算机程序
3. C解决问题的、由有限个明确定义的步骤组成的序列
4. D一种存储数字的数据结构

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

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

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

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

Floyd–Warshall 算法计算什么？速度如何？

1. A以 O(V + E) 计算从一个源顶点到所有其他顶点的最短路径
2. B以 O(V³) 计算所有顶点对之间的最短路径
3. C以 O(E log V) 计算最小生成树
4. D以 O(V²) 计算拓扑序

停机问题（halting problem）表明：

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

拓扑排序只适用于：

1. A无向图
2. B有向无环图（DAG）
3. C完全图
4. D带负权重的图