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

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

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

对范围在 0 到 k 之间的 n 个整数进行计数排序（counting sort），运行时间是多少？

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

什么是算法？

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

递推式 T(n) = 2T(n/2) + O(1) 的解是什么？

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

为什么许多库排序函数在子数组很小时会改用插入排序？

1. A插入排序开销小，在小规模或几乎有序的输入上很快
2. B在大规模输入上，插入排序比任何其他排序算法使用的内存都少
3. C插入排序在最坏情况下是 O(n log n)
4. D递归算法无法处理少于 10 个元素的数组

哪种排序算法是稳定的？

1. A快速排序（常见的原地版本）
2. B归并排序
3. C堆排序
4. D选择排序（常见版本）

为什么在单链表上二分查找不能达到 O(log n) 的时间？

1. A链表无法排序
2. B二分查找至少需要两倍的内存
3. C链表节点上的比较更慢
4. D由于不能按下标直接访问，到达中间元素需要 O(n) 步

在有 V 个顶点、E 条边的图上，使用二叉堆的 Dijkstra 算法运行时间是多少？

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