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

什么是算法？

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

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

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

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

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

一个问题具有最优子结构是什么意思？

1. A该问题可以在常数时间内求解
2. B该问题恰好有一个最优解，所有子问题共享这个解
3. C每个子问题的规模都相同
4. D最优解可以由其子问题的最优解构造出来

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

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

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

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

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

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

哪种技术能使快速排序在任意输入上的期望运行时间为 O(n log n)？

1. A只对左侧进行递归
2. B总是选择第一个元素
3. C均匀随机地选择基准
4. D在运行快速排序前先对输入排序