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

f(n) = Θ(g(n)) 是什么意思？

1. Af 的增长严格快于 g
2. Bf 的增长严格慢于 g
3. C对每个 n，f 总是小于 g，因此 g 是它的上界，但绝不是下界
4. Df 与 g 以相同的速率增长，上下都被 g 的常数倍所界定

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

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

当 n 变大时，下列哪一项增长最慢？

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

用标准的三重循环计算两个 n × n 矩阵的乘积，时间复杂度是多少？

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

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

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

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

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

插入排序在有序输入上运行时间为 O(n)。这与比较排序的 Ω(n log n) 下界矛盾吗？

1. A矛盾，但仅对长度小于 100 的数组
2. B矛盾，因此这个下界是错的
3. C不矛盾，下界针对的是所有输入中的最坏情况，而不是每一个输入
4. D不矛盾，因为插入排序不是比较排序

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

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