发帖
雷达卡
本节课实验课的主要内容安排如下：
- 讲解上一节布置的3道课后习题
- 设计一道算法题：折半插入排序
- 布置一道力扣题目
- 安排下次课后的学习任务：完成学习通中的“期末习题复习一”
一、第七章课后习题解析
【P286 第4题】
在有序表 (4, 6, 10, 12, 20, 30, 50, 70, 88, 100) 中进行折半查找，目标元素为 58。在查找过程中，该元素将依次与表中的哪些元素比较？最终查找结果为失败。
选项：
A. 20, 70, 30, 50
B. 30, 88, 70, 50
C. 20, 50
D. 30, 88, 50
答案：A
解析： 表中共有 10 个元素，初始 low=1，high=10。
第一次取 mid = (1+10)/2 = 5，与第5个元素 20 比较，58 > 20，因此在右半区间继续查找（low=6）。
第二次取 mid = (6+10)/2 = 8，与第8个元素 70 比较，58 < 70，转向左半区间（high=7）。
第三次取 mid = (6+7)/2 = 6，与第6个元素 30 比较，58 > 30，继续在右半部分（low=7）。
第四次取 mid = (7+7)/2 = 7，与第7个元素 50 比较，58 > 50，但下一位置已超出范围，查找失败。
因此比较顺序为：20 → 70 → 30 → 50，对应选项 A。
【第7题】
给出以下四个序列，分别构造二叉排序树，其中哪一个与其他三个构造出的树结构不同？
选项：
A. (100, 80, 90, 60, 120, 110, 130)
B. (100, 120, 110, 130, 80, 60, 90)
C. (100, 60, 80, 90, 120, 110, 130)
D. (100, 80, 60, 90, 120, 130, 110)
答案：C
解析： 此题考察的是二叉排序树（BST）的构建规则及不同插入顺序对树形的影响。
根据 BST 性质：对于任意节点，其左子树所有节点值小于它，右子树所有节点值大于它。
分析各序列构建过程：
序列 A：
插入 100 作为根；
插入 80 → 100 的左孩子；
插入 90 → 大于 80 小于 100，成为 80 的右孩子；
插入 60 → 小于 80，成为 80 的左孩子；
插入 120 → 大于 100，成为 100 的右孩子；
插入 110 → 小于 120，成为 120 的左孩子；
插入 130 → 大于 120，成为 120 的右孩子。
A 构造的树结构为：
100
/ \
80 120
/ \ / \
60 90 110 130序列 B：
100 为根；
120 → 100 右孩子；
110 → 120 左孩子；
130 → 120 右孩子；
80 → 100 左孩子；
60 → 80 左孩子；
90 → 80 右孩子。
B 的树结构：
100
/ \
80 120
/ \ / \
60 90 110 130与 A 完全一致。
序列 C：
100 为根；
60 → 100 左孩子（关键差异点）；
80 → 60 右孩子；
90 → 80 右孩子；
120 → 100 右孩子；
110 和 130 分别为 120 的左右孩子。
C 的树结构：
100
/ \
60 120
\ / \
80 110 130
\
90明显与 A、B 不同，左子树形态发生变化。
序列 D：
构建顺序虽异，但最终结构与 B 相同：
100 为根；
80 为其左孩子；
60 和 90 分别为 80 的左右孩子；
120 为 100 右孩子；
130 为 120 右孩子；
110 为 120 左孩子。
D 的树结构：
100
/ \
80 120
/ \ / \
60 90 110 130综上所述，只有 C 序列生成的树与其他三项不等价，故正确答案为 C。
【第14题】
设哈希表长度为 14，哈希函数为 H(key) = key % 11。当前表中已有关键字：15、38、61、84。现需插入关键字 49，采用二次探测法解决冲突，问其应存入的位置是？
选项：
A. 8 B. 3 C. 5 D. 9
答案：D
解析：
计算各关键字的哈希地址：
H(15) = 15 % 11 = 4 → 存入位置 4
H(38) = 38 % 11 = 5 → 存入位置 5
H(61) = 61 % 11 = 6 → 存入位置 6
H(84) = 84 % 11 = 7 → 存入位置 7
现插入 49：H(49) = 49 % 11 = 5，发生冲突（位置 5 已被占用）
使用二次探测法处理冲突，探测序列为：
d = (H(key) + i) % m 或 (H(key) - i) % m（通常先正向尝试）
第一次冲突后，i = 1：
(5 + 1) % 14 = 6 → 仍冲突（61 占用）
i = 2：
(5 + 2) % 14 = 9 → 位置 9 为空，可插入。
因此关键字 49 被放入位置 9，答案为 D。
二、折半插入排序算法实践
给定一个长度为 10 的整数数组：
{12, 2, 16, 30, 28, 10, 16, 20, 6, 18}
要求使用折半插入排序（Binary Insertion Sort）对其进行升序排列。具体步骤如下：
- 从第二个元素开始，逐个处理每个元素；
- 对于当前元素，在前面已排序的部分中使用折半查找确定其应插入的位置；
- 将该位置后的元素整体后移一位，腾出空间； <4>插入当前元素。
通过不断扩展有序区，最终得到完整排序序列。
输入示例：
12 2 16 30 28 10 16 20 6 18
输出示例：
2 6 10 12 16 16 18 20 28 30
#include <stdio.h>
void BinaryInsertSortWithSentinel(int a[], int n) {
int i, j, low, high, mid, temp;
// 数组 a 的有效数据放在 a[1..n]，a[0] 用作哨兵
for (i = 2; i <= n; i++) {
temp = a[i];
// 折半查找在已排序区间 a[1..i-1] 中确定插入位置 low（1..i）
low = 1;
high = i - 1;
while (low <= high) {
mid = (low + high) / 2;
if (a[mid] > temp)
high = mid - 1;
else
low = mid + 1;
}
// 此时 low 为插入位置
// 将待插入元素放入哨兵 a[0]
a[0] = temp;
// 从 i-1 开始向左搬移大于哨兵的元素（哨兵保证不越界）
j = i - 1;
while (j >= low) { // 因为通过折半已算出 low，仍用 low 限制搬移范围
a[j + 1] = a[j];
j--;
}
// 把哨兵（即 temp）放到正确位置
a[low] = a[0];
}
}
int main() {
// 使用 1-based 存放输入，a[0] 保留给哨兵
int a[11] = {0, 12, 2, 16, 30, 28, 10, 16, 20, 6, 18};
int n = 10;
int i;
BinaryInsertSortWithSentinel(a, n);
// 输出排序后的序列（从 a[1] 到 a[n]）
for (i = 1; i <= n; i++) {
printf("%d ", a[i]);
}
printf("\n");
return 0;
}三、算法题讲解总结
本环节重点在于理解折半插入排序相较于直接插入排序的优势：通过二分查找减少比较次数，提升效率。虽然移动次数未变，但在大规模数据中能显著降低时间复杂度中的比较成本。
void BinaryInsertSortWithSentinel(int a[], int n) {
// 函数接收一个整型数组和元素个数
// 数组采用 1-based 下标存储有效数据（即实际数据从下标 1 到 n）
// a[0] 作为哨兵单元，用于暂存数据并简化边界处理
教学点：使用 1-based 索引可以让哨兵机制更直观。哨兵的主要作用是临时保存待插入值，避免每次移动时重复传参，并减少对数组边界的显式判断。
int i, j, low, high, mid;
// 局部变量说明：
// i：外层循环控制变量，表示当前要处理的元素位置，从第 2 个开始（i=2）
// j：在元素后移过程中使用的索引，方向为从右向左
// low 和 high：折半查找的左右边界指针
// mid：二分过程中的中点位置
// a[0]：用作哨兵，存放当前待插入的元素值
教学点：讲解各变量含义及其取值范围：
// i 的范围是 [2, n]
// j 初始为 i-1，逐步递减至 low
// low 起始为 1，high 起始为 i-1，在查找过程中动态调整
for (i = 2; i <= n; i++) {
// 外层循环从第二个元素开始遍历
// 第一个元素 a[1] 被视为已排序部分的起始
教学点：解释为何外层循环从 2 开始：
// 插入排序的基本思想是维护一个有序区间，初始时 a[1] 自身为有序
// 每次将未排序区的第一个元素插入到有序区的合适位置
// 因此需从第 2 个元素开始执行插入操作
a[0] = a[i];
// 将当前待插入元素 a[i] 存入哨兵位置 a[0]
// 这样可以在后续比较和搬移中直接引用 a[0]，无需额外变量暂存
教学点：强调该步骤的意义：
// 防止在右移过程中原值被覆盖而丢失
// 同时可利用 a[0] 参与比较，有时可省略边界检查（但在本实现中仍保留明确边界）
low = 1;
// 折半查找的左边界初始化为有序区间的起始位置（下标 1）
high = i - 1;
// 右边界为当前已排序部分的末尾（即 i-1）
a
while (low <= high) {
// 执行标准的二分查找结构，目标不是找相等元素
// 而是确定“第一个大于 a[0] 的位置”，即插入点
教学点：说明查找目标：
// 返回的位置应满足：插入后整个序列仍然有序
// 最终插入位置由 low 给出（循环结束时 low == high + 1）
mid = (low + high) / 2;
// 计算中间位置
n
教学点：提醒潜在问题：
// 在 C 语言中，(low + high) 可能发生整数溢出
// 更安全写法为 low + ((high - low) / 2)
// 但教学场景中若数组较小，可暂时忽略此风险
if (a[mid] > a[0]) {
// 若中间元素大于待插入值，说明插入点在左半段（含 mid）
high = mid - 1;
} else {
// 否则插入点在右半段（不包含 mid）
low = mid + 1;
}
a[1]
a[n]
a[0]
int i, j, low, high, mid, temp;
i
j
low, high, mid
temp
a[0]
low
[1, i]
high
[1, i-1]
temp = a[i];
temp
low = 1;
1
high = i - 1;
i - 1
a[low..high]
temp
mid = (low + high) / 2;
mid
(low+high)/2
low + (high-low)/2
if (a[mid] > temp)
high = mid - 1;
else
low = mid + 1;
mid - 1
mid+1..high
mid + 1
a[1..i]
low == i
// 此时 low 为插入位置
a[0] = temp;
j = i - 1;
j
i-1
a[j + 1] = a[j];
j--;
}
a[low..i-1]
a[low]
j < low
low
while (a[j] > a[0])
a[low] = a[0];
// 循环结束后，low 即为正确的插入位置
// 它指向第一个大于 a[0] 的元素所在位置
// 如果所有元素都不大于 a[0]，则 low = i（插入末尾）
}
// 此时 low 已确定为插入位置
// 接下来需要将 [low, i-1] 区间内的元素整体右移一位
j = i - 1;
// 设置搬移起始位置：从已排序区最后一个元素开始向右移动
i
while (j >= low) {
// 从右向左依次移动元素，直到腾出位置 low
a[j + 1] = a[j];
j--;
}
i == n
教学点：解释搬移方向的重要性：
// 必须从右往左移动，否则会覆盖尚未处理的数据
// 例如先移动左边会导致右边原始值丢失
// 虽然 a[0] 中已有待插入值，但此处没有依赖哨兵进行条件判断
// 而是以计算出的 low 作为搬移终点，保持逻辑清晰稳定
a[low] = a[0];
// 将哨兵中保存的原 a[i] 值插入到正确位置 low
【main
// 至此，a[1..i] 已恢复有序状态
// 继续下一轮循环处理下一个元素
}
// 整个数组 a[1..n] 已完成排序
// 排序结束
教学要点总结（快速回顾）：
// 1. 使用 1-based 数组便于理解哨兵机制
// 2. 哨兵 a[0] 用于暂存当前值，防止丢失
// 3. 折半查找确定插入位置，提高查找效率（O(log i)）
// 4. 元素右移腾位，必须从右向左进行
// 5. 最终通过 low 定位插入点并将 a[0] 写回
// 6. 总体时间复杂度仍为 O(n)，但比较次数优化至约 O(n log n)
int a[11] = {0, 12, 2, 16, 30, 28, 10, 16, 20, 6, 18};
}
使用一个长度为 11 的数组（索引范围 0 到 10），其中
a[0]a[1]..a[10]BinaryInsertSortWithSentinel(a, n);a[1]a[n]四、期末习题复习
相关内容将在下节课中继续讲解。五、力扣题
35、搜索插入位置
题目链接：https://leetcode.cn/problems/search-insert-position/description/
京公网安备 11010802022788号
