考研之路

查找与排序 章节测

范围：查找（顺序/折半/分块、BST、AVL、红黑树、B 树与 B+ 树、散列表）与排序（插入族、交换族、选择族、归并、基数、外部排序）。说明：本卷共 30 题，第 1-24 题为单选，第 25-30 题为手推大题；全部为模拟题（非真题），风格对齐 408 统考。限时 60 分钟。答案与解析见文末，做完前不要下翻。

第 1 题

对 100 个元素的表做顺序查找，等概率下查找成功的平均查找长度为（ ）

A. 50 B. 50.5 C. 51 D. 100

第 2 题

顺序查找算法中设置哨兵（将待查关键字存入 R[0]）的作用是（ ）

A. 省去查找方向的判断 B. 省去对数组下标越界的判断，减少比较分支 C. 使查找失败时返回值统一为 0 D. 防止待查元素恰好在表头时漏查

第 3 题

长度为 100 的有序表做折半查找，其判定树中失败结点（外部结点）的个数为（ ）

A. 100 B. 101 C. 99 D. 200

第 4 题

有序表为 {7, 14, 18, 21, 23, 29, 31, 35, 38, 42, 46, 49, 52}（下标 1..13），mid = ⌊(low+high)/2⌋，查找关键字 14 的比较次数为（ ）

A. 2 B. 3 C. 4 D. 5

第 5 题

关于折半查找，下列说法错误的是（ ）

A. 折半查找要求关键字有序且采用顺序存储 B. 折半查找的判定树形态由 mid 的取法唯一确定 C. 折半查找也可以在有序单链表上高效进行 D. 含 13 个元素的有序表折半查找，成功查找最多比较 4 次

第 6 题

对含 630 个元素的表分块查找，每块 21 个元素（共 30 块），块间与块内均用顺序查找，等概率下成功查找的平均查找长度为（ ）

A. 26.5 B. 26 C. 15.5 D. 11

第 7 题

在二叉排序树中删除一个有两个孩子的结点 p 时，标准做法是用（ ）替换 p，再删除该替换结点

A. p 的左子树中最右下的结点（中序前驱） B. p 的双亲结点 C. p 的左孩子或右孩子直接上移 D. p 的右子树中最左下的结点（中序后继）或左子树中最右下的结点（中序前驱）

第 8 题

高度为 5 的平衡二叉树（AVL）的最少结点数为（ ）

A. 10 B. 11 C. 12 D. 15

第 9 题

关于 AVL 树的插入与删除，下列说法正确的是（ ）

A. 插入一个结点后可能需要连续多次旋转才能恢复平衡 B. 删除一个结点后至多旋转一次即可恢复全树平衡 C. 插入一个结点后至多一次旋转（含双旋的两步）即可恢复全树平衡 D. 插入与删除都至多旋转一次

第 10 题

关于红黑树，下列说法错误的是（ ）

A. 从根到任一叶结点的最长路径不超过最短路径的 2 倍 B. 红结点的孩子一定是黑结点 C. 黑结点的孩子一定是红结点 D. 任一结点到其所有后代叶结点的路径上黑结点数相同

第 11 题

向红黑树插入新结点 z 时，下列说法正确的是（ ）

A. z 初始着黑色，因为黑色安全 B. z 初始着红色；若父结点为红且叔结点为黑，通过变色即可解决且不上溯 C. z 初始着红色；若父、叔结点均为红，则父叔变黑、祖父变红，问题可能继续向上传递 D. 一次插入过程中旋转次数可能超过 2 次

第 12 题

一棵 5 阶 B 树中，除根外的所有终端（非叶结点最底层分支结点层面的终端结点）结点中关键字的个数至少为（ ）

A. 1 B. 2 C. 3 D. 4

第 13 题

关于 m 阶 B+ 树，下列说法正确的是（ ）

A. 叶结点仅包含部分关键字，其余存于分支结点 B. 任何关键字的查找都必须下行到叶结点才结束 C. n 棵子树的结点含 n − 1 个关键字 D. B+ 树不支持顺序查找

第 14 题

除留余数法中，散列函数取 H(key) = key mod p，p 通常选不大于表长的最大素数（或不含小于 20 的质因子的数），主要原因是（ ）

A. 素数运算比合数快 B. 使关键字经取模后尽可能均匀地落在各地址，减少冲突与堆积 C. 保证散列函数值不超过表长 D. 保证装填因子小于 1

第 15 题

采用开放定址法（线性探测）处理冲突的散列表中，删除一个元素的正确做法是（ ）

A. 直接置为空，与未存放过元素一致 B. 做删除标记（懒惰删除），不能物理置空 C. 用表中最后一个元素填补被删位置 D. 重新散列全部剩余元素

第 16 题

平方探测法中，散列表表长 m 取 4j + 3 形式的素数，其好处是（ ）

A. 散列函数计算更快 B. 装填因子可以取到 1 C. 能保证探测序列覆盖表中所有位置 D. 保证任何情况下不发生冲突

第 17 题

散列表的装填因子 α 与平均查找长度 ASL 的关系是（ ）

A. α 越大 ASL 越小，与冲突处理方法无关 B. ASL 是 α 的函数，α 越小 ASL 越小；同一 α 下不同冲突处理方法 ASL 不同 C. ASL 只与表中记录个数 n 有关 D. ASL 只与表长 m 有关

第 18 题

关于快速排序，下列说法正确的是（ ）

A. 初始序列基本有序时，取首元素为枢轴的快排性能最好 B. 快排的空间复杂度在任何情况下都是 O(1) C. 快排每趟结束至少有一个元素落在最终位置 D. 快排是稳定的排序算法

第 19 题

序列 {25, 84, 21, 47, 15, 27, 68, 35, 20}（下标 1..9）经某一趟排序后变为 {20, 15, 21, 25, 47, 27, 68, 35, 84}，该排序算法是（ ）

A. 冒泡排序 B. 快速排序 C. 简单选择排序 D. 直接插入排序

第 20 题

下列排序算法中，稳定的是（ ）

A. 希尔排序 B. 快速排序 C. 堆排序 D. 直接插入排序

第 21 题

对 8 个元素做二路归并排序（自底向上），共需归并的趟数为（ ）

A. 2 B. 3 C. 4 D. 8

第 22 题

关于堆排序，下列说法错误的是（ ）

A. 对 n 个元素自底向上建初始堆的时间复杂度为 O(n) B. 建初始堆从编号 ⌊n/2⌋ 的结点开始，倒序逐结点向下调整 C. 升序排序应采用大顶堆 D. 堆排序是稳定的排序算法

第 23 题

关于基数排序，下列说法正确的是（ ）

A. 时间复杂度为 O(d(n + r))，其中 d 为关键字位数、r 为基数 B. 它基于关键字比较进行 C. 它是不稳定的排序算法 D. 它对任意浮点数序列同样高效

第 24 题

10 个不等长初始归并段做 3 路平衡归并（构造最佳归并树时），需补充的虚段个数为（ ）

A. 0 B. 1 C. 2 D. 3

第 25 题（手推）

对序列 {49, 38, 65, 97, 76, 13, 27, 50}（下标 1..8）做快速排序，以首元素 49 为枢轴，采用"双向交替"划分（high 端找小者填左坑、low 端找大者填右坑）。要求：(1) 写出第一趟划分的完整结果并指出枢轴落位；(2) 继续对枢轴左侧子序列做一趟划分，写出第二趟结束后全序列的状态。

第 26 题（手推）

对序列 {50, 36, 66, 90, 14, 22, 5, 18}（下标 1..8）：(1) 自底向上建大顶堆，写出建堆结果与每个结点的调整过程；(2) 写出堆排序第一趟（堆顶与末位交换并调整）之后的序列状态。

第 27 题（手推）

向初始为空的 AVL 树依次插入 {35, 20, 45, 10, 30, 25}。要求：(1) 指出哪次插入引发失衡、失衡类型（LL/RR/LR/RL）及最小不平衡子树的根；(2) 写出两步旋转的每一步动作；(3) 给出最终树形。

第 28 题（手推）

一棵 5 阶 B 树当前只有一个结点（根，同时为终端结点），含关键字 {15, 35, 55, 75}。要求：(1) 插入 25，说明结点变化、上移的关键字与分裂结果、树高变化；(2) 该 5 阶 B 树中非根终端结点关键字数的合法区间。

第 29 题（手推）

关键字序列 {22, 41, 53, 46, 30, 13, 1, 67}，散列函数 H(key) = key mod 11，用链地址法处理冲突，依次插入。要求：(1) 画出各链（用文字或示意描述各地址桶的链）；(2) 计算等概率下查找成功与查找失败的平均查找长度。

第 30 题（手推）

初始序列 {36, 24, 48, 12, 65, 43, 50, 26}（下标 1..8）。以下三组"第一趟之后"的结果分别来自哪个算法（冒泡 / 快排 / 简单选择 / 直接插入 四选三）？并说明判定依据。(1) {24, 36, 12, 48, 43, 50, 26, 65}；(2) {26, 24, 12, 36, 65, 43, 50, 48}；(3) {12, 24, 48, 36, 65, 43, 50, 26}。另问：(4) 若算法为直接插入排序，第一趟后的结果应是什么？

答案与解析

第 1 题：B

  • 考点标签：顺序查找成功 ASL
  • 难度：易
  • 解析：ASL成功=n+12=1012=50.5ASL_{成功} = \frac{n+1}{2} = \frac{101}{2} = 50.5。
  • 错因提醒：51 是失败情形的比较次数口径之一（含哨兵），别与成功 ASL 混淆。

第 2 题：B

  • 考点标签：顺序查找的哨兵
  • 难度：易
  • 解析：哨兵保证循环必然终止（扫到 R[0] 必命中），循环体内无需判断下标越界，省去一半比较分支。C 是附带效果而非作用。
  • 错因提醒：答题口径落在"免越界判断、简化程序"上。

第 3 题：B

  • 考点标签：折半查找判定树失败结点数
  • 难度：易
  • 解析：n 个内部结点的判定树恰有 n + 1 个空链域，各挂一个失败结点，故 101 个。
  • 错因提醒：这是恒等式"失败结点 = n + 1"，与 mid 取法无关。

第 4 题：C

  • 考点标签：折半查找比较次数手推
  • 难度：中
  • 解析：mid 序列：(1+13)/2=7 → 29（14 < 29，high=6）；(1+6)/2=3 → 18（14 < 18，high=2）；(1+2)/2=1 → 7（14 > 7，low=2）；low=high=2 → mid=2 → 14 命中。依次与 29、18、7、14 比较，共 4 次。
  • 错因提醒：手推时用"下标"算 mid，别拿关键字值算；漏掉最后命中那次比较是常见错误。

第 5 题：C

  • 考点标签：折半查找的适用条件
  • 难度：易
  • 解析：折半查找需随机存取定位 mid，链表不支持，C 错误。n = 13 时判定树高 ⌈log⁡214⌉=4\lceil\log_2 14\rceil = 4，D 正确。
  • 错因提醒："有序"和"顺序存储"两个前提缺一不可；单链表只能顺序查找。

第 6 题：A

  • 考点标签：分块查找 ASL
  • 难度：易
  • 解析：ASL=b+12+s+12=312+222=15.5+11=26.5ASL = \frac{b+1}{2} + \frac{s+1}{2} = \frac{31}{2} + \frac{22}{2} = 15.5 + 11 = 26.5。
  • 错因提醒：分母是块数 b 和块长 s 各自的 +1；若块间改用折半，前一项换成 ⌈log⁡231⌉=5\lceil\log_2 31\rceil = 5。

第 7 题：D

  • 考点标签：BST 删除双子结点
  • 难度：易
  • 解析：标准做法是用中序前驱（左子树最右下）或中序后继（右子树最左下）替换 p，替换者至多有一个孩子，删除归约为简单情形。A、D 都对但 D 完整（两种替换均可），选 D。
  • 错因提醒：只用"直接前驱/后继"（遍历序上的邻居概念）表述不严格，必须是子树最值结点。

第 8 题：C

  • 考点标签：AVL 最少结点数递推
  • 难度：易
  • 解析：Nh=Nh−1+Nh−2+1N_h = N_{h-1} + N_{h-2} + 1，N1=1,N2=2N_1 = 1, N_2 = 2 → 1, 2, 4, 7, 12, 20, 33。
  • 错因提醒：约定空树高度 0、单结点高度 1；若题目按其它高度约定，先对齐口径再递推。

第 9 题：C

  • 考点标签：AVL 插入/删除的旋转次数
  • 难度：中
  • 解析：插入引起失衡时，调整最小不平衡子树后其高度恢复到插入前，上方祖先自动复原，至多一次旋转（双旋算一次调整的两步）。删除可能使子树变矮引发连锁失衡，需要多次旋转。故 A、B、D 均错。
  • 错因提醒：这是"插入一次、删除多次"的经典对比，正反两个方向都可能被命题。

第 10 题：C

  • 考点标签：红黑树五大性质
  • 难度：中
  • 解析：性质只约束"红结点的孩子必黑"，黑结点的孩子可红可黑，C 错误。A 由"黑高相同 + 无相邻红结点"推出：最短路纯黑（长 = 黑高）、最长路红黑相间（长 ≤ 2 × 黑高）。
  • 错因提醒：把性质 4 单向约束说成双向是最高频错项；"叶结点（外部结点）全黑"里的"叶"不是数据结点。

第 11 题：C

  • 考点标签：红黑树插入调整
  • 难度：难
  • 解析：新结点着红（只可能违反性质 2/4；着黑必违反性质 5），A 错。父红叔红 → 变色后问题上移到祖父，可能连续变色（O(log n) 次），C 正确。父红叔黑 → 旋转解决（LR/RL 双旋至多 2 次旋转），B 说"只变色不旋转"错误。整次插入旋转次数至多 2，D 错。
  • 错因提醒："变色可多次、旋转至多两次"两句常被拆开设错项；父红叔红情形不旋转。

第 12 题：B

  • 考点标签：B 树关键字数下界
  • 难度：易
  • 解析：m 阶 B 树除根外每个结点至少 ⌈m/2⌉\lceil m/2\rceil 棵子树，即至少 ⌈5/2⌉−1=2\lceil 5/2\rceil - 1 = 2 个关键字。
  • 错因提醒：根结点不受该下界约束（根非叶时至少 2 棵子树 1 个关键字）；别把子树数下界当关键字数下界。

第 13 题：B

  • 考点标签：B+ 树性质
  • 难度：中
  • 解析：B+ 树非终端结点只起索引作用，任何查找都下行到叶结点才结束，B 正确。叶结点含全部关键字（A 错）；n 棵子树含 n 个关键字（C 错，这是 B 树的规则）；叶结点用链表相连，恰好支持顺序查找（D 错）。
  • 错因提醒：B 树"n 棵子树 n−1 关键字、命中可提前停"与 B+ 树"n 棵子树 n 关键字、必到叶"两组特征严格成对记忆，交叉出题。

第 14 题：B

  • 考点标签：除留余数法 p 的选取
  • 难度：易
  • 解析：p 取素数（或不含小质因子）可避免关键字按 p 的因子规律成簇，使散列地址分布均匀、减少冲突。
  • 错因提醒：C 的"不超过表长"由"不大于 m 的最大"保证但不是选素数的原因；素数不加速取模。

第 15 题：B

  • 考点标签：开放定址法下的删除
  • 难度：易
  • 解析：物理置空会截断同义词探测链，后来者探测到空位误判不存在；只能打删除标记。链地址法无此问题。
  • 错因提醒：删除标记过多会使表"看似变满"，失败查找链变长——副作用也是考点。

第 16 题：C

  • 考点标签：平方探测的表长条件
  • 难度：中
  • 解析：表长为 4j + 3 型素数时，平方探测序列 ±12,±22,⋯\pm 1^2, \pm 2^2, \cdots 能探测到表中所有位置，不会出现"有空位却探不到"。
  • 错因提醒：任何散列方法都不可能"保证不冲突"（D 绝对化必错）；该结论只对平方探测成立，线性探测本身总能探全表。

第 17 题：B

  • 考点标签：装填因子与 ASL
  • 难度：易
  • 解析：ASL 是 α = n/m 的函数：α 越小冲突越少、ASL 越小；同一 α 下，链地址法与线性/平方探测的 ASL 不同。ASL 与表长本身、与记录具体取值无关。
  • 错因提醒：α 越小 ASL 越小但空间浪费越多——命题爱用"α 越大越好"设反。

第 18 题：C

  • 考点标签：快排性质
  • 难度：中
  • 解析：每趟划分使枢轴落到最终位置，C 正确。初始有序 + 首元素枢轴是快排最坏情形（O(n²)），A 反了；空间为递归栈深，最好/平均 O(log n)、最坏 O(n)，B 错；快排不稳定，D 错。
  • 错因提醒："基本有序对快排有利"是针对直接插入的直觉，别迁移错位。

第 19 题：B

  • 考点标签：每趟结果判断算法
  • 难度：中
  • 解析：检验元素 25（位置 4）：左侧 {20, 15, 21} 全部 < 25，右侧 {47, 27, 68, 35, 84} 全部 > 25——快排指纹。冒泡第一趟应使最大值 84 沉底且倒数第二位为次大区段形态（本结果末位恰是 84，但前部 47、27 等仍乱序且无 25 中部落位特征，不符）；简单选择第一趟应使最小值 20 在首位（20 确在首位，但简单选择不会让 25 落到中部最终位——以"左全小右全大"的枢轴指纹为准）；直接插入第一趟只动前两个。
  • 错因提醒：单一特征（如首、尾元素就位）可能撞车，必须用"某元素左全小右全大"的完整指纹复核。

第 20 题：D

  • 考点标签：排序稳定性
  • 难度：易
  • 解析：口诀"快选希堆"不稳定；直接插入相等时不越过等值元素，稳定。
  • 错因提醒：O(nlog⁡2n)O(n\log_2 n) 中只有归并稳定——若选项出现归并也稳定，不要被"快排最快所以稳定"的直觉骗。

第 21 题：B

  • 考点标签：二路归并趟数
  • 难度：易
  • 解析：自底向上段长 1→2→4→8，⌈log⁡28⌉=3\lceil\log_2 8\rceil = 3 趟。
  • 错因提醒：趟数只与 n 有关、与初态无关；问 4 路归并时公式换 ⌈log⁡4n⌉\lceil\log_4 n\rceil。

第 22 题：D

  • 考点标签：堆排序性质
  • 难度：中
  • 解析：堆排序远程交换打破稳定性（反例 {3, 3, 1}），D 错误。建堆 O(n)（叶结点不调整的红利，级数推导见知识点章节）、从 ⌊n/2⌋ 倒序调整、升序配大顶堆，A、B、C 均正确。
  • 错因提醒：若把 D 换成"建堆 O(n log n)"同样错；建堆 O(n) 与整体 O(n log n) 别混。

第 23 题：A

  • 考点标签：基数排序性质
  • 难度：中
  • 解析：d 趟分配收集，每趟 O(n + r)，共 O(d(n + r))，A 正确。基数排序不比较关键字（B 错）、稳定（队列 FIFO 保序，C 错）、要求关键字可按位分解且位数/基数小，任意浮点数不适用（D 错）。
  • 错因提醒：d、r 固定时接近线性，但"d、r 大时还高效"是错项常见表述。

第 24 题：B

  • 考点标签：最佳归并树补虚段
  • 难度：中
  • 解析：严格 k 叉哈夫曼树要求 (r−1) mod (k−1)=0(r-1) \bmod (k-1) = 0。r=10,k=3r = 10, k = 3：(10−1) mod 2=1≠0(10-1) \bmod 2 = 1 \ne 0，补 u=(k−1)−(r−1) mod (k−1)=2−1=1u = (k-1) - (r-1)\bmod(k-1) = 2 - 1 = 1 个虚段。
  • 错因提醒：虚段长度为 0、只占结构位置不计读写量；先算余数再补，方向别反。

第 25 题

  • 考点标签：快排一趟划分手推
  • 难度：中
  • 解析： (1) pivot = 49，low=1、high=8。high 端找 <49：50 否、27 是 → 填到 low：{27, 38, 65, 97, 76, 13, _, 50}；low 端找 >49：27、38 否、65 是 → 填到 high：{27, 38, _, 97, 76, 13, 65, 50}；high 端找 <49：65、97、76 否、13 是 → 填 low：{27, 38, 13, 97, 76, _, 65, 50}；low 端找 >49：13 否、97 是 → 填 high：{27, 38, 13, _, 76, 97, 65, 50}；high 端继续左滑无小者，low=high=4，49 归位。第一趟：{27, 38, 13, 49, 76, 97, 50, 65}，枢轴 49 落位下标 4（左 {27,38,13} 全小、右 {76,97,50,65} 全大）。 (2) 左子序列 {27, 38, 13} 以 27 为枢轴：high 端 13 < 27 填到 low → {13, 38, 27}；low 端 38 > 27 填回 high → {13, 27, 38}（27 落位下标 2）。第二趟后全序列：{13, 27, 38, 49, 76, 97, 50, 65}（右子序列暂未处理）。
  • 错因提醒：扫描方向要交替（先 high 后 low，与枢轴取自 low 端配套）；每步填的是"对面留下的空位"；结束后必须用"左全小右全大"复核。

第 26 题

  • 考点标签：自底向上建堆与堆排序一趟
  • 难度：中
  • 解析： (1) n = 8，从 ⌊8/2⌋ = 4 倒序调整：i=4（90）：孩子 18，不动；i=3（66）：孩子 22、5，不动；i=2（36）：孩子 90、14，最大者 90 > 36 → 交换，36 落位 4，其孩子 18 < 36 止；i=1（50）：孩子 90、66，最大者 90 > 50 → 交换，50 落位 2，其孩子 36、14 均 < 50 止。建堆结果：{90, 50, 66, 36, 14, 22, 5, 18}。 (2) 堆顶 90 与 a[8] 交换得 {18, 50, 66, 36, 14, 22, 5, | 90}，对前 7 个元素从根下调：18 与较大孩子 66 交换 → 66 落根、18 落位 3；18 再与较大孩子 22 交换 → 18 落位 6。第一趟后：{66, 50, 22, 36, 14, 18, 5, 90}（90 已就位）。
  • 错因提醒：建堆必须倒序（子树先成堆再调父）；交换后要一路下沉到底，不能只换一层；每趟排序输出的是当前堆顶（最大）到尾部。

第 27 题

  • 考点标签：AVL 插入与 LR 双旋
  • 难度：难
  • 解析： (1) 依次插入 35, 20, 45, 10, 30 均平衡（35(20(10, 30), 45)）。插 25（成为 30 的左孩子）后自下而上检查：20 的 BF = 1 − 2 = −1 正常；35 的 BF = 左高 3 − 右高 1 = +2 失衡，最小不平衡子树以 35 为根；插入点 25 位于 35 的左孩子（20）的右子树（30 一侧）→ LR 型。 (2) 第一步：对 20 左旋——20 的右孩子 30 上升，30 的原左子树（25）挂为 20 的右子树，得子树 30(20(10, 25), −)；第二步：对 35 右旋——30 上升为子树根，35 连同右子树 45 下挂，30 的原右子树（空）成为 35 的左子树。 (3) 最终树形：30(20(10, 25), 35(−, 45))，即根 30，左子树根 20（孩子 10、25），右子树根 35（无左孩子，右孩子 45）。
  • 错因提醒：失衡判定要自插入点向上找第一个 BF = ±2 的祖先（本题是 35 不是 20）；LR/RL 双旋后孙结点当根（30、35、20 排序居中者是 30），用"中者提根"速检。

第 28 题

  • 考点标签：B 树插入分裂
  • 难度：中
  • 解析： (1) 5 阶 B 树结点关键字上限为 m − 1 = 4，{15, 35, 55, 75} 已满。插入 25 后结点内有序为 {15, 25, 35, 55, 75}（5 个，溢出）：取第 ⌈5/2⌉=3\lceil 5/2\rceil = 3 个关键字 35 上移，新建根结点容纳 35；原结点分裂为左 {15, 25}、右 {55, 75}，两者均为根 35 的子树。树高由 1 变 2（根向上裂开，不是叶向下生长）。 (2) 非根终端结点关键字数合法区间为 [⌈m/2⌉−1, m−1]=[2,4][\lceil m/2\rceil - 1,\ m - 1] = [2, 4]。
  • 错因提醒：上移的是排序后的第 ⌈m/2⌉ 个关键字（本题第 3 个，即 35），不是中间偏左/偏右的其它取法；根结点例外，最少 1 个关键字。

第 29 题

  • 考点标签：链地址法散列表构造与 ASL
  • 难度：中
  • 解析： (1) 各关键字 mod 11：22→0，41→8，53→9，46→2，30→8，13→2，1→1，67→1。各桶链（按插入顺序接在链尾）：0: [22]；1: [1, 67]；2: [46, 13]；8: [41, 30]；9: [53]；其余 3、4、5、6、7、10 为空链。 (2) 成功：链首元素比较 1 次、链次元素比较 2 次——22、1、46、41、53 各 1 次，67、13、30 各 2 次，ASL成功=5×1+3×28=118ASL_{成功} = \frac{5 \times 1 + 3 \times 2}{8} = \frac{11}{8}。失败：对每个初始地址（0..10 共 11 个）数该链上全部比较次数（走到链尾即失败，不含空格比较）：链长为 1、2、2、2、1、0×6，总和 = 8，ASL失败=811ASL_{失败} = \frac{8}{11}。
  • 错因提醒：链地址法失败 ASL 的分母是桶数 m（=p）不是 n；失败比较数不含空格（链尾即知不存在），与开放定址"数到空位"口径不同；若题目改头插法建链，成功 ASL 中各元素的比较次数对应颠倒，需按实际链序数。

第 30 题

  • 考点标签：每趟结果判断算法
  • 难度：难
  • 解析： (1) {24, 36, 12, 48, 43, 50, 26, 65}：最大值 65 沉到末位，且相邻逆序逐对消除的形态吻合（36 与 24 交换、48 与 12 交换、65 一路下沉到尾），无中部元素"左全小右全大"指纹 → 冒泡排序。 (2) {26, 24, 12, 36, 65, 43, 50, 48}：检验 36（位置 4）：左 {26, 24, 12} 全 < 36，右 {65, 43, 50, 48} 全 > 36 → 快速排序（枢轴 36 落最终位）。 (3) {12, 24, 48, 36, 65, 43, 50, 26}：最小值 12 升到首位（原位置 4 与位置 1 交换，24 顶替到位置 4），尾部依旧乱序 → 简单选择排序。 (4) 直接插入第一趟只处理 r[2] = 24 < 36：前移一位，得 {24, 36, 48, 12, 65, 43, 50, 26}（仅前两个有序，其余不动）。
  • 错因提醒：(1)(3) 都有"一个极值就位"，区分要看就位端（冒泡在尾部沉大者、简单选择在头部升小者）以及中间区是否被交换打乱；(2) 的枢轴指纹是唯一强判据。直接插入的指纹是"只有前缀变短有序、后面纹丝不动"。