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

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

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

什么是记忆化（memoisation）？

1. A存储函数调用的结果，使重复调用能直接从内存中得到答案
2. B函数返回后释放内存
3. C自动把递归转换为等价的循环，从而不需要调用栈
4. D在每行代码旁边写注释

算法的最坏情况运行时间描述的是什么？

1. A在最小输入上所需的时间
2. B在所有规模为 n 的输入上所需的最长时间
3. C在慢速计算机上所需的时间
4. D在规模为 n 的随机输入上所需的期望时间

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

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

在一个有序数组中，你从两端各放一个指针向内移动，寻找和为目标值的两个元素。时间复杂度是多少？

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

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

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

取一个极大匹配中每条边的两个端点，可以得到一个顶点覆盖。这个覆盖有多好？

1. A与最优解相比质量未知
2. B至多是最小顶点覆盖大小的两倍
3. C至多是最小值的 log n 倍
4. D总是一个最小顶点覆盖

为什么哈希表的平均查找时间是 O(1)，而最坏情况是 O(n)？

1. A许多键可能冲突（collision）到同一个桶中
2. B数组的访问时间是 O(n)
3. C键必须先排序
4. D哈希函数运行很慢