2026-05-11 练习题答案与解析
排序、查找和散列 答案与解析
单项选择题
1. 给定一个 N 个相异元素构成的有序数列，设计一个递归算法实现数列的二分查找，请问递归调用栈的最小容量应为（ ）。
答案：D. ⌊log₂(N+1)⌋
解析： 二分查找每次将搜索区间减半，递归深度等于查找路径长度。对于 N 个元素的有序数列，最坏情况下递归深度为 ⌊log₂(N+1)⌋。例如 N=1 → 1 层，N=3 → 2 层，N=7 → 3 层，与公式吻合。每层递归占用一个栈帧，所以栈的最小容量即为该递归深度。
2. 1GB 数据排序、可用内存仅 100MB，最适合的排序算法是（ ）。
答案：B. 归并排序
解析： 数据规模远超可用内存，必须采用外部排序。归并排序天然支持分块处理：先将大数据切成若干个能装入内存的块、对每块独立排序后写回磁盘，再多路归并合并所有块。归并阶段只需要在内存中维护每路的少量缓冲区即可。
堆排序和快速排序都假设数据全部驻留内存，无法直接处理超内存的数据；插入排序更不适合大规模数据。
3. 下列哪种是不稳定排序？
答案：D. 希尔排序
解析： 稳定排序指相等关键字在排序后保持原有相对顺序。
- 冒泡排序：只在严格大于时交换，相等元素不动 → 稳定
- 归并排序：合并时遇到相等元素优先取左侧 → 稳定
- 直接插入排序：从右向左找插入位置，相等时不越过 → 稳定
- 希尔排序：按增量分组进行插入排序，相等元素可能被分到不同子序列中改变相对顺序 → 不稳定
4. 哪一组排序算法最坏情况下时间复杂度大 O 表示相同？
答案：C. 快速排序和选择排序
解析： 各算法的最坏情况时间复杂度：
| 算法 | 最坏情况 |
|---|---|
| 快速排序 | O(n²)（基准每次都极端不平衡） |
| 堆排序 | O(n log n) |
| 归并排序 | O(n log n) |
| 直接插入排序 | O(n²) |
| 选择排序 | O(n²) |
| 冒泡排序 | O(n²) |
只有 C 选项中两者都是 O(n²)。
5. 多关键字排序，先按 key1 非递减、key1 相同时再按 key2 非递减，应选哪种方法？
答案：D. 先按 key2 值进行直接选择排序，再按 key1 值进行冒泡排序
解析： 多关键字排序的标准做法是：先排次关键字，再排主关键字，且最后一次排序必须使用稳定算法——这样主关键字相同时才会保持次关键字的相对顺序。
- 冒泡排序：稳定
- 直接选择排序：不稳定
因此最后一次必须用冒泡，主关键字 key1 由冒泡排序——选 D。
A、C 顺序错误；B 最后用了不稳定的选择排序，会破坏 key2 的有序性。
6. 有 n² 个整数，找到其中最小整数需要比较次数至少为（ ）次。
答案：C. n²-1
解析： 在 m 个互异元素中找最小值，每次比较最多淘汰一个候选元素。要确定最小值需要淘汰其余 m−1 个元素，所以至少需要 m−1 次比较。这里 m = n²，故为 n²−1 次。
7. 散列检索 38 需要进行几次比较？
答案：B. 2
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 26 | 38 | 17 | 33 | 48 | 25 |
解析： 此处"再散列"为双重散列（double hashing），即用 H₂(key) 作为探查步长。
- h(38) = 38 mod 13 = 12，位置 12 是 25（h(25)=12，先占位）≠ 38 → 第 1 次比较失败
- 计算步长 H₂(38) = 38 mod 3 = 2
- 下一探查位置 = (12 + 2) mod 13 = 1，位置 1 = 38 → 第 2 次比较成功
共 2 次关键码比较。
判断题
8. 希尔排序每趟都要调用直接插入排序，所以效率比直接插入排序差。
答案：B. 错误
解析： 希尔排序虽然每趟都基于直接插入排序，但通过递减增量分组，让远距离元素跨步交换，使整体逐渐"基本有序"。这样后续插入排序遇到的子序列长度小、移动距离短，整体效率显著提高。
希尔排序平均时间复杂度约 O(n^1.3)（取决于增量序列），优于直接插入排序的 O(n²)。
9. 直接插入排序、冒泡排序、希尔排序都是在数据正序时比逆序快。
答案：A. 正确
解析：
- 直接插入排序：正序时每个元素只需比较 1 次 → O(n)；逆序时需移动所有前驱 → O(n²)
- 冒泡排序：正序时一趟扫描即可结束 → O(n)；逆序时需 n−1 趟 → O(n²)
- 希尔排序：正序时各子序列已经有序，每次插入排序的比较和移动都极少；逆序时需较多比较和移动
三者均满足"正序快于逆序"。
10. 散列表关键码比较次数仅取决于散列函数和冲突处理方法。
答案：B. 错误
解析： 关键码比较次数还与装填因子（ = n/m） 密切相关。装填因子越大，冲突概率越高，
所以"仅取决于两个因素"的说法是不全面的。
11. 含 N 个结点构建二叉最小堆，时间复杂度为 O(N log₂N)。
答案：B. 错误
解析： 建堆的正确时间复杂度是 O(N)。
虽然单次 siftDown 调整是 O(log N)，但建堆是从最后一个非叶节点开始向上做 siftDown，底层节点多但下沉路径短，顶层节点少但下沉路径长。数学上：
自底向上 siftDown 建堆是 O(N)。
填空题
12. 二分检索应采用什么存储形式？
答案：顺序存储
解析： 二分检索每一步都需要 O(1) 时间访问"中间位置"的元素，只有顺序存储（数组）支持下标随机访问。链式存储要从头遍历到中点，需要 O(n) 时间，会让二分检索退化为 O(n log n)，失去意义。
13. 在 1000 个元素中找最小的前 5 个，最快的算法是？
答案：堆排序
解析： 这是经典的 top-k 问题。
| 算法 | 找前 5 小所需操作 |
|---|---|
| 冒泡排序 | 5 趟扫描，每趟 ~n 比较，约 5×1000 = 5000 |
| 快速排序 | 必须排完整个序列 → O(n log n) ≈ 10000 |
| 归并排序 | 必须完整归并 → O(n log n) ≈ 10000 |
| 堆排序 | 建小根堆 O(n) ≈ 1000，再 5 次 delMin（每次 O(log n)≈10），共 ≈ 1050 |
堆排序最快，是 top-k 类问题的天然选择（实际生产中通常使用 size=k 的最大堆，复杂度为 O(n log k)）。
14. n 个数据对象的二路归并排序中，每趟归并的时间复杂度为？
答案：O(n)
解析： 每趟归并将相邻有序子序列两两合并，每个元素只被读取/比较常数次，所以单趟归并时间为 O(n)。由于归并排序共需 ⌈log₂n⌉ 趟，所以归并排序总复杂度 O(n log n)。
15. 希尔排序与归并排序第一轮结果（降序）
输入：[46, 70, 56, 38, 40, 80, 60, 22]
(1) 希尔排序 gap=4 第一趟答案： [46, 80, 60, 38, 40, 70, 56, 22]
解析： 按下标差 4 分组，得到 4 个子序列，各自降序排列：
| 下标 | 子序列 | 降序后 |
|---|---|---|
| 0, 4 | (46, 40) | (46, 40) |
| 1, 5 | (70, 80) | (80, 70) |
| 2, 6 | (56, 60) | (60, 56) |
| 3, 7 | (38, 22) | (38, 22) |
按下标回填即得结果。
(2) 归并排序第一轮答案： [70, 46, 56, 38, 80, 40, 60, 22]
解析： 把每个元素视为长度为 1 的子序列，相邻两两归并（降序，大者在前）：
- (46, 70) → 70, 46
- (56, 38) → 56, 38
- (40, 80) → 80, 40
- (60, 22) → 60, 22
16. 快速排序第一次划分（pivot = 46，非递减）
答案：[40, 38, 46, 56, 70, 80]
解析： 取首元素 46 为基准，使用双指针法（left/right 交替扫描）：
| 操作 | 数组 | left | right |
|---|---|---|---|
| 初始（保存 pivot=46） | [_, 70, 56, 38, 40, 80] | 0 | 5 |
| 右→左找 < 46：40，放入 0 | [40, 70, 56, 38, _, 80] | 0 | 4 |
| 左→右找 > 46：70，放入 4 | [40, _, 56, 38, 70, 80] | 1 | 4 |
| 右→左找 < 46：38，放入 1 | [40, 38, 56, _, 70, 80] | 1 | 3 |
| 左→右找 > 46：56，放入 3 | [40, 38, _, 56, 70, 80] | 2 | 3 |
| 相遇于 2，放回 pivot | [40, 38, 46, 56, 70, 80] | — | — |
划分完成，pivot 左侧元素 ≤ 46，右侧元素 ≥ 46。
17. 拉链法散列地址 1 的链中有几个记录？
答案：4
解析： 计算每个 key mod 13：
| key | 19 | 14 | 23 | 1 | 68 | 20 | 84 | 27 | 55 | 11 | 10 | 79 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 地址 | 6 | 1 | 10 | 1 | 3 | 7 | 6 | 1 | 3 | 11 | 10 | 1 |
落在地址 1 的关键字：14, 1, 27, 79，共 4 个。
18. 删除最小堆 [8, 15, 10, 21, 34, 16, 12] 的堆顶后比较次数
答案：3
解析：
- 用末尾元素 12 替换堆顶 →
[12, 15, 10, 21, 34, 16] - 第 1 层 siftDown（12 在 index 0）：
- 比较两个孩子 15 和 10，取较小者 10 → 第 1 次比较
- 比较 12 和 10，12 > 10 → 交换 → 第 2 次比较
- 结果：
[10, 15, 12, 21, 34, 16]
- 第 2 层 siftDown（12 在 index 2，只有一个孩子 16）：
- 比较 12 和 16，12 < 16 → 停止 → 第 3 次比较
共 3 次关键字比较。
综合题
19. 奇偶交换排序
(a) 序列 [18, 73, 5, 10, 68, 99, 27, 10] 前 4 趟排序结果
| 趟 | 类型 | 比较位置 | 结果 |
|---|---|---|---|
| 1 | 奇 (i=1,3,5,7) | (18,73)(5,10)(68,99)(27,10) | [18, 73, 5, 10, 68, 99, 10, 27] |
| 2 | 偶 (i=2,4,6) | (73,5)(10,68)(99,10) | [18, 5, 73, 10, 68, 10, 99, 27] |
| 3 | 奇 (i=1,3,5,7) | (18,5)(73,10)(68,10)(99,27) | [5, 18, 10, 73, 10, 68, 27, 99] |
| 4 | 偶 (i=2,4,6) | (18,10)(73,10)(68,27) | [5, 10, 18, 10, 73, 27, 68, 99] |
加粗的是发生交换的对。
(b) 是否稳定？
答案：稳定
解析： 算法只在 a[i] > a[i+1] 即严格大于时才交换相邻元素，相等元素的相对顺序不会改变，所以是稳定排序。这也是基于相邻交换类排序通常稳定的共同原因（同冒泡排序）。
(c) 正序 / 逆序时的比较次数与交换次数
正序情况（如 [1, 2, ..., n]）：
- 一趟奇扫描：i=1,3,…，比较 ⌊n/2⌋ 次，全部 aᵢ ≤ aᵢ₊₁，无交换 → change1 = False
- 一趟偶扫描：i=2,4,…，比较 ⌊(n−1)/2⌋ 次，无交换 → change2 = False
- 进入下一轮 while 时 change1 和 change2 都为 False，退出循环
| 数值 | |
|---|---|
| 比较次数 | ⌊n/2⌋ + ⌊(n−1)/2⌋ = n − 1 |
| 交换次数 | 0 |
逆序情况（如 [n, n−1, ..., 1]）：
每对相邻元素都需交换，每次交换消除一个逆序对。逆序数组的总逆序对数恰为 C(n,2)。需要约 ⌈n/2⌉ 轮（odd+even）才能完全有序，再加一轮检测无变化才能跳出 while。每轮做 (n−1) 次比较。
| 数值 | |
|---|---|
| 比较次数 | (⌈n/2⌉ + 1)(n − 1) ≈ n²/2，量级 O(n²) |
| 交换次数 | n(n − 1) / 2 |
小例（n=4 逆序 [4,3,2,1]）验证：
| 轮 | 奇扫描后 | 偶扫描后 | 该轮交换 |
|---|---|---|---|
| 1 | [3,4,1,2] | [3,1,4,2] | 3 |
| 2 | [1,3,2,4] | [1,2,3,4] | 3 |
| 3 | 无变化 | 无变化 | 0 |
- 总比较 = 3 × 3 = 9 次 ≈ n²/2
- 总交换 = 6 = n(n−1)/2 ✓
结论： 正序为最优情况（线性 O(n)），逆序为最坏情况（平方 O(n²)），与冒泡排序的特性一致。