2026-05-11 排序、查找和散列

单项选择题

1. 给定一个 N 个相异元素构成的有序数列，设计一个递归算法实现数列的二分查找，考察递归过程中栈的使用情况，请问这样一个递归调用栈的最小容量应为（ ）。

2. 假设需要对存储开销 1GB (GigaBytes) 的数据进行排序，但主存储器（RAM）当前可用的存储空间只有 100MB (MegaBytes)。针对这种情况，（ ）排序算法是最适合的。

3. 若按照排序的稳定性和不稳定性对排序算法进行分类，则（ ）是不稳定排序。

4. 以下（ ）分组中的两个排序算法的最坏情况下时间复杂度的大 O 表示相同。

5. 假设线性表中每个元素有两个数据项 key1 和 key2，现对线性表按以下规则进行排序：先根据数据项 key1 的值进行非递减排序；在 key1 值相同的情况下，再根据数据项 key2 的值进行非递减排序。满足这种要求的排序方法是（ ）。

6. 有 n² 个整数，找到其中最小整数需要比较次数至少为（ ）次。

7. 有一个散列表如下图所示，其散列函数为 h(key)=key mod 13，该散列表使用再散列函数 H2(Key)=Key MOD 3 解决碰撞，问从表中检索出关键码 38 需进行几次比较（ ）。

判断题

8. 希尔排序算法的每一趟都要调用一次或多次直接插入排序算法，所以其效率比直接插入排序算法差。

9. 直接插入排序、冒泡排序、希尔排序都是在数据正序的情况下比数据在逆序的情况下要快。

10. 由于碰撞的发生，基于散列表的检索仍然需要进行关键码对比，并且关键码的比较次数仅取决于选择的散列函数与处理碰撞的方法两个因素。

11. 构建一个含 N 个结点的（二叉）最小值堆，建堆的时间复杂度大 O 表示为 O(Nlog₂N)。

填空题

12. 线性表的顺序存储与链式存储是两种常见存储形式；当表元素有序排序进行二分检索时，应采用_________存储形式。

13. 如果只想得到 1000 个元素的序列中最小的前 5 个元素，在冒泡排序、快速排序、堆排序和归并排序中，哪种算法最快？

14. 有 n 个数据对象的二路归并排序中，每趟归并的时间复杂度为_________。

15. 对一组记录进行降序排序，其关键码为（46, 70, 56, 38, 40, 80, 60, 22），采用初始步长为 4 的希尔（shell）排序，第一趟扫描的结果是（）；而采用归并排序第一轮归并结果是（）。

16. 对一组记录进行非递减排序，其关键码为 [46, 70, 56, 38, 40, 80]，则利用快速排序的方法，以第一个记录为基准得到的第一次划分结果为_________。

17. 设有一组记录的关键字为 19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79，用链地址法（拉链法）构造散列表，散列函数为 H(key)=key MOD 13，散列地址为 1 的链中有_________个记录。

18. 已知以数组表示的小根堆为 [8, 15, 10, 21, 34, 16, 12]，删除关键字 8 之后需要重新建堆，在此过程中，关键字的比较次数是_________。

综合题

19. 奇偶交换排序如下所述：对于原始记录序列 {a₁, a₂, a₃, ……, a_n}，第一趟对所有奇数 i，将 a_i 和 a_i+1 进行比较，若 a_i > a_i+1，则将二者交换；第二趟对所有偶数 i；第三趟对所有奇数 i；第四趟对所有偶数 i，…，依次类推直到整个记录序列有序为止。伪代码如下：

def ExSort(a[1..n]):  # a[1..n] 为待排序数组
    change1 = True
    change2 = True
    if n <= 0:
        return Error
    while change1 or change2:
        change1 = False  # 奇数趟扫描标志
        for i in range(1, n, 2):
            if a[i] > a[i+1]:
                a[i], a[i+1] = a[i+1], a[i]
                change1 = True
        if not change1 and not change2:
            break
        change2 = False  # 偶数趟扫描标志
        for i in range(2, n, 2):
            if a[i] > a[i+1]:
                a[i], a[i+1] = a[i+1], a[i]
                change2 = True

a) 请写出序列 18, 73, 5, 10, 68, 99, 27, 10 在前 4 趟排序中每趟排序后的结果（2 分）。

b) 奇偶交换排序是否是稳定的排序（1 分）。

c) 在序列为初始状态为"正序"和"逆序"两种情况下，试给出序列长度为 n 的情况下，排序过程所需进行的关键码比较次数和记录的交换次数（4 分）。