学校-2025-2026-1《数据结构》测验4

2025-2026-1《数据结构》测验4

选择

1.数据结构是一门研究非数值计算的程序设计问题中计算机的（）以及它们之间的关系和运算等的学科。

A.操作对象

B.计算方法

C.逻辑存储

D.数据映象

要解决这道题，核心是精准匹配数据结构的官方定义，明确其研究范畴的核心要素。以下是详细分析：

第一步：回顾数据结构的标准定义

数据结构的核心研究对象是：非数值计算的程序设计问题中，计算机的「操作对象」、操作对象之间的「关系」，以及基于这些关系的「运算（算法）」。其完整体系包含三部分：

1. 逻辑结构（操作对象之间的关系）；
2. 物理结构（操作对象的存储方式）；
3. 运算（对操作对象的处理方法）。

第二步：逐一分析选项

选项 A：操作对象

“操作对象” 即数据结构中的「数据元素」（如数组的元素、链表的节点、树的结点），是数据结构研究的核心载体—— 所有关系和运算都围绕操作对象展开。这与定义完全匹配，是正确答案。

选项 B：计算方法

“计算方法” 更偏向「算法」的具体实现步骤（如排序算法的执行流程），而数据结构研究的是 “运算的设计逻辑”（而非单纯的计算方法），且 “计算方法” 并非定义中明确的核心研究对象，排除。

选项 C：逻辑存储

“逻辑存储” 是「物理结构」的一部分（物理结构包括顺序存储、链式存储等，是操作对象的存储方式），但它只是数据结构研究的 “子范畴”，而非定义中与 “关系”“运算” 并列的核心对象，排除。

选项 D：数据映象

“数据映象” 指「逻辑结构到物理结构的映射关系」（如二叉树的逻辑结构如何映射到数组 / 链表的存储），是物理结构的辅助概念，并非数据结构的核心研究对象，排除。

结论

数据结构研究的核心是 “操作对象、关系、运算”，空格处应填「操作对象」。

答案：A

2.在仅设有尾指针的表长为$n$的单循环链表中，以下操作时间复杂度为$O(n)$的是（）。

A.表头插入

B.表头删除

C.表尾插入

D.表尾删除

你想知道在仅设置尾指针、表长为 $n$ 的单循环链表中，哪个操作的时间复杂度为 $O(n)$，核心是分析每个操作的执行逻辑，判断是否需要遍历链表（遍历则为 $O(n)$，直接操作则为 $O(1)$）。

先明确核心前提：仅设尾指针的单循环链表结构

单循环链表的尾指针（记为rear）指向链表最后一个节点，且尾节点的next指向头节点（形成环）。因此：

• 头节点 = rear->next（尾的下一个就是头）；
• 尾节点 = rear；
• 单链表的特性：只能从头节点向后遍历，无法直接获取前驱节点。

逐一分析选项的时间复杂度

选项 A：表头插入

操作逻辑：

1. 新节点p的next指向原头节点（rear->next）；
2. 尾节点rear的next指向新节点p（更新头节点）。

整个过程无需遍历，直接通过尾指针定位头节点，时间复杂度 $O(1)$，排除 A。

选项 B：表头删除

操作逻辑：

1. 待删除的头节点q = rear->next；
2. 尾节点rear的next指向q->next（跳过原头节点，更新新头）；
3. 释放q。

无需遍历，直接操作，时间复杂度 $O(1)$，排除 B。

选项 C：表尾插入

操作逻辑：

1. 新节点p的next指向头节点（rear->next），保持循环；
2. 原尾节点rear的next指向p；
3. 更新尾指针rear = p。

无需遍历，直接操作尾节点，时间复杂度 $O(1)$，排除 C。

选项 D：表尾删除

操作逻辑：要删除尾节点rear，必须先找到尾节点的前驱节点（单链表无法反向访问）：

1. 指针p从表头（rear->next）开始遍历；
2. 循环条件：p->next != rear（直到找到尾节点的前驱）；
3. 前驱节点p的next指向头节点（rear->next），保持循环；
4. 释放原尾节点rear，更新尾指针rear = p。

遍历过程需要走n-1步（表长为 $n$），时间复杂度 $O(n)$，D 是正确答案。

总结

1. 仅设尾指针的单循环链表中，表头插入 / 删除、表尾插入的时间复杂度均为 $O(1)$（直接通过尾指针定位操作点）；
2. 表尾删除需要遍历找到尾节点的前驱，时间复杂度为 $O(n)$；
3. 核心规律：单链表删除尾节点（无论是否循环），若仅存尾指针 / 头指针，都需遍历找前驱，时间复杂度 $O(n)$。

答案：D

3.某索引顺序表共有元素395个，平均分成5块。若先对索引表采用顺序查找，再对块中元素进行顺序查找，则在等概率情况下，分块查找成功的平均查找长度是（ ）。

A.43

B.79

C.198

D.200

要解决这道题，核心是掌握分块查找的平均查找长度（ASL）计算逻辑—— 分块查找是 “索引表查找 + 块内查找” 的两步过程，总 ASL 是两步 ASL 的总和。以下是详细推导步骤：

第一步：明确分块查找的核心前提与公式

1. 分块查找的基本原理

将有序 / 无序表按规则分成b个 “块”（块内元素可无序，但块间需有序，本题无需关注有序性，仅需计算查找次数），建立一个 “索引表”（每个索引项对应一块，存储块的关键信息，如最大关键字、起始地址）。查找时：

• 第一步：查找索引表，确定目标元素所在的块；
• 第二步：在对应块内查找目标元素。

2. 平均查找长度公式

成功查找的平均查找长度 = 索引表的平均查找长度（ASL_idx） + 块内的平均查找长度（ASL_block），即：ASL = ASL_idx + ASL_block

3. 顺序查找的平均查找长度

对于有k个元素的表，等概率顺序查找成功的平均查找长度为：ASL_seq = (k + 1) / 2（推导：查找第 1 个元素需 1 次，第 2 个需 2 次，…，第 k 个需 k 次，总和为k(k+1)/2，平均为(k+1)/2）

第二步：提取题目已知条件并计算关键参数

题目给出：

• 总元素数n = 395；
• 分成b = 5块（平均分成 5 块）；
• 索引表查找方式：顺序查找；
• 块内查找方式：顺序查找。

计算每块的元素数s（平均分成 5 块，无余数）：s = n / b = 395 / 5 = 79（即每个块有 79 个元素，索引表有 5 个索引项）

第三步：分别计算两步的平均查找长度

1. 索引表的平均查找长度（ASL_idx）

索引表有b = 5个索引项，顺序查找，等概率成功：ASL_idx = (b + 1) / 2 = (5 + 1) / 2 = 3

2. 块内的平均查找长度（ASL_block）

每个块有s = 79个元素，顺序查找，等概率成功：ASL_block = (s + 1) / 2 = (79 + 1) / 2 = 40

第四步：计算总平均查找长度

总 ASL = ASL_idx + ASL_block = 3 + 40 = 43

关键误区提醒

• 不要混淆 “分块查找” 与 “二分查找”：本题明确索引表和块内均为顺序查找，若索引表用二分查找，ASL_idx 会不同，但题目未提及，需严格按题意；
• 不要漏算 “+1”：顺序查找成功的平均查找长度是(k+1)/2（而非k/2），因为查找第 1 个元素需 1 次，第 k 个需 k 次，平均是中间值；
• 确认每块元素数：395 刚好被 5 整除（79×5=395），无需处理余数，直接用s=79计算。

答案：A

作者的话：当时也不知道怎么做，只知道79个需要40次，离40最近的就是43

4.设二叉排序树中关键字由1到1000的整数构成，现要查找关键字为363的结点，下述关键字序列中，不可能是在二叉排序树上查找的序列是( )。

A.2，252，401，398，330，344，397，363

B.924，220，911，244，898，258, 362，363

C.925，202，911，240，912，245，363

D.2，399，387，219，266，382，381，278，363

要解决这道题，核心是掌握二叉排序树（BST）的查找性质：二叉排序树中，左子树所有节点值 <根节点值，右子树所有节点值> 根节点值；查找过程中，每次比较后会确定后续查找的「有效区间」（要么在当前节点的左子树，要么在右子树），后续所有查找的元素必须严格落在这个区间内，否则该序列不可能是查找序列。

关键逻辑：跟踪查找的「有效区间」

假设目标关键字为 363，初始有效区间为 (-∞, +∞)（无边界限制）。每次遇到一个查找元素 x 时：

1. 若 x == 363：查找成功，序列合法；
2. 若 x > 363：说明 363 只能在 x 的左子树，有效区间更新为 (当前左边界, x)（后续元素必须小于 x）；
3. 若 x < 363：说明 363 只能在 x 的右子树，有效区间更新为 (x, 当前右边界)（后续元素必须大于 x）；
4. 若后续元素超出当前有效区间，则序列非法。

逐一验证选项（按查找顺序跟踪有效区间）

选项 A：2 → 252 → 401 → 398 → 330 → 344 → 397 → 363

• 初始区间：(-∞, +∞)
• 2 < 363 → 区间更新为 (2, +∞)（后续元素需 > 2）
• 252 < 363 → 区间更新为 (252, +∞)（后续元素需 > 252）
• 401 > 363 → 区间更新为 (252, 401)（后续元素需 < 401）
• 398 <401 且>252 → 区间更新为 (252, 398)（398>363，后续需 < 398）
• 330 >252 且 <398 → 区间更新为 (330, 398)（330<363，后续需> 330）
• 344 >330 且 <398 → 区间更新为 (344, 398)（344<363，后续需> 344）
• 397 <398 且>344 → 区间更新为 (344, 397)（397>363，后续需 < 397）
• 363 在 (344, 397) 内 → 合法。

选项 B：924 → 220 → 911 → 244 → 898 → 258 → 362 → 363

• 初始区间：(-∞, +∞)
• 924 > 363 → 区间更新为 (-∞, 924)（后续元素需 < 924）
• 220 < 363 → 区间更新为 (220, 924)（后续元素需 > 220）
• 911 > 363 → 区间更新为 (220, 911)（后续元素需 < 911）
• 244 >220 且 <911 → 区间更新为 (244, 911)（244<363，后续需> 244）
• 898 <911 且>244 → 区间更新为 (244, 898)（898>363，后续需 < 898）
• 258 >244 且 <898 → 区间更新为 (258, 898)（258<363，后续需> 258）
• 362 >258 且 <898 → 区间更新为 (362, 898)（362<363，后续需> 362）
• 363 在 (362, 898) 内 → 合法。

选项 C：925 → 202 → 911 → 240 → 912 → 245 → 363

• 初始区间：(-∞, +∞)

• 925 > 363 → 区间更新为 (-∞, 925)（后续元素需 < 925）

• 202 < 363 → 区间更新为 (202, 925)（后续元素需 > 202）

• 911 > 363 → 区间更新为 (202, 911)（后续元素需 < 911，因为 911 的左子树才可能有 363）

• 240 >202 且 <911 → 区间更新为 (240, 911)（240<363，后续需> 240）

• 接下来是 912：当前有效区间是

  (240, 911)

  ，但 912 > 911 → 超出区间！

  原因：911 已确定 363 在其左子树（区间 < 911），后续不可能出现比 911 大的元素，否则违反 BST 查找逻辑 → 非法。

选项 D：2 → 399 → 387 → 219 → 266 → 382 → 381 → 278 → 363

• 初始区间：(-∞, +∞)
• 2 < 363 → 区间更新为 (2, +∞)（后续需 > 2）
• 399 > 363 → 区间更新为 (2, 399)（后续需 < 399）
• 387 <399 且>2 → 区间更新为 (2, 387)（387>363，后续需 < 387）
• 219 >2 且 <387 → 区间更新为 (219, 387)（219<363，后续需> 219）
• 266 >219 且 <387 → 区间更新为 (266, 387)（266<363，后续需> 266）
• 382 <387 且>266 → 区间更新为 (266, 382)（382>363，后续需 < 382）
• 381 <382 且>266 → 区间更新为 (266, 381)（381>363，后续需 < 381）
• 278 >266 且 <381 → 区间更新为 (278, 381)（278<363，后续需> 278）
• 363 在 (278, 381) 内 → 合法。

结论

只有选项 C 存在超出有效区间的元素（912），违反二叉排序树的查找规则，因此不可能是查找序列。

答案：C

作者的话：在做这题时第一眼也愣住了，但是仔细看可以知道这题考的是跟范围有关的问题，一个查找肯定范围是不断缩小的，一看c里面先911后912，明显有问题，故选c

5.下列四种排序方法中，排序过程中的比较次数与序列初始状态无关的是( )。

A.选择排序法

B.插入排序法

C.快速排序法

D.冒泡排序法

要解决这道题，核心是分析每种排序算法的比较次数逻辑，判断其是否受序列初始状态（有序、逆序、无序）影响 —— 关键看 “比较次数是否为固定值，与初始排列无关”。

先明确核心判断标准

• 若排序的比较次数仅由元素个数 n 决定，无论初始序列是有序、逆序还是乱序，比较次数都固定，则符合题意；
• 若排序的比较次数随初始序列的有序程度变化（有序时少、逆序时多），则不符合题意。

逐一分析四种排序算法

选项 A：选择排序法（正确答案）

核心逻辑

每一轮从待排序区间中找到最小（或最大）元素，与待排序区间的第一个元素交换，然后缩小待排序区间（向前移动一位）。

比较次数分析

• 第 1 轮：待排序区间有 n 个元素，需比较n-1次（遍历所有待排序元素找最小值）；
• 第 2 轮：待排序区间有 n-1 个元素，需比较n-2次；
• …
• 第 n-1 轮：待排序区间有 2 个元素，需比较1次。

总比较次数 = $(n-1) + (n-2) + ... + 1 = n(n-1)/2$，是固定值，与序列初始状态无关！→ 例：$n=5$ 时，无论初始序列是 [1,2,3,4,5]（有序）还是 [5,4,3,2,1]（逆序），都必须比较 4+3+2+1=10 次 —— 因为选择排序必须遍历完待排序区间才能确定最小值，无法通过初始有序性减少比较次数。

选项 B：插入排序法（排除）

核心逻辑

将每个元素插入到前面已排序的子序列中，插入前需与已排序子序列的元素逐一比较，找到插入位置。

比较次数分析

• 最佳情况（初始有序）：每个元素只需与前一个元素比较 1 次（无需插入），总比较次数 = $n-1$（最少）；
• 最坏情况（初始逆序）：每个元素需与前面所有已排序元素比较，总比较次数 = $n(n-1)/2$（最多）；
• 平均情况：比较次数随初始有序程度变化，因此与初始状态相关。

选项 C：快速排序法（排除）

核心逻辑

选择基准元素，将序列分为 “小于基准” 和 “大于基准” 的两部分（分区），再递归处理两部分。

比较次数分析

• 最佳情况（基准每次均分序列）：比较次数 = $O(n\log n)$（最少）；
• 最坏情况（初始有序 / 逆序，基准选首尾）：分区后一侧为空，递归深度 $n$，总比较次数 = $O(n^2)$（最多）；
• 比较次数取决于基准选择和初始序列分布，与初始状态密切相关。

选项 D：冒泡排序法（排除）

核心逻辑

相邻元素两两比较，逆序则交换，每一轮将最大元素 “冒泡” 到末尾；若某一轮无交换，可提前终止（优化版）。

比较次数分析

• 最佳情况（初始有序）：第 1 轮无交换，直接终止，总比较次数 = $n-1$（最少）；
• 最坏情况（初始逆序）：每一轮都需比较所有未冒泡的元素，总比较次数 = $n(n-1)/2$（最多）；
• 比较次数随初始有序程度变化，与初始状态相关。

总结

只有选择排序的比较次数是固定的$n(n-1)/2$，与序列初始状态无关；其他三种排序的比较次数均受初始有序性影响。

答案：A

查找算法综合练习题

题目背景

已知关键字序列：$\{ 78，25，30，19，6，130，205，115，39，396，63，337 \}$，分别用顺序查找、折半查找、二叉排序树、平衡二叉树、散列表实现查找。

答题注意事项

1. 平均查找长度按最简分数（分子 / 分母）填写，分母为 1 时省略分母；
2. 多整数填写要求：按顺序用减号-连接，首尾 / 中间无空格（例：1-2-3-4）。

---

（1）顺序查找

题目

对上述关键字序列进行顺序查找：① 在等概率情况下查找成功时的平均查找长度为（）；② 查找关键字 70 需要和关键字比较（）次才能确定不存在。

详细解析

① 查找成功的平均查找长度（ASL）

顺序查找核心规则：等概率下，成功 ASL = 所有元素查找次数之和 / 元素个数。

• 元素总数 $n=12$；

• 各元素查找次数（按序列顺序）：

  78（1 次）、25（2 次）、30（3 次）、19（4 次）、6（5 次）、130（6 次）、205（7 次）、115（8 次）、39（9 次）、396（10 次）、63（11 次）、337（12 次）；

• 查找次数总和：$(1+2+3+\dots+12 = \frac{12 \times 13}{2} = 78)$；

• 成功 ASL：$\frac{78}{12} = \frac{13}{2}$。

② 查找 70 的比较次数

顺序查找判定 “不存在” 的规则：需遍历所有元素且均不匹配，才能确定不存在。

• 序列共 12 个元素，因此需比较 12 次。

答案

① $\boldsymbol{\frac{13}{2}}$；② $\boldsymbol{12}$。

---

（2）折半查找

题目

若上述关键字序列已从小到大排好序，采用折半查找：① 对折半查找判定树树根的左子树进行先序遍历，得到的关键字先序遍历序列是（）；② 在等概率情况下查找成功时的平均查找长度为（）；③ 查找关键字 70 需要依次和哪些关键字比较才能确定不存在（）。

详细解析

步骤 1：对原序列排序

排序后序列（索引 0~11）：$\text{arr}[0]=6, \text{arr}[1]=19, \text{arr}[2]=25, \text{arr}[3]=30, \text{arr}[4]=39, \text{arr}[5]=63, \text{arr}[6]=78, \text{arr}[7]=115, \text{arr}[8]=130, \text{arr}[9]=205, \text{arr}[10]=337, \text{arr}[11]=396$。

步骤 2：构建折半查找判定树

折半查找判定树构建规则：每次取区间中点为节点，左子树为左区间，右子树为右区间。最终判定树结构（层级标注）：

      63（层1，根）
    /        \
  25（层2）   130（层2）
 /   \       /    \
6（3） 30（3） 78（3） 337（3）
 \     \      \      /   \
19（4）39（4）115（4）205（4）396（4）

① 根节点左子树的先序遍历

先序遍历规则：根 → 左 → 右；根节点为 63，其左子树根是 25。

• 遍历序列：25 → 6 → 19 → 30 → 39 → 结果：$\boldsymbol{25-6-19-30-39}$。

② 查找成功的平均查找长度

统计各节点查找层数（比较次数）：

• 层 1（1 次）：63（1 个）；层 2（2 次）：25、130（2 个）；
• 层 3（3 次）：6、30、78、337（4 个）；层 4（4 次）：19、39、115、205、396（5 个）；
• 总查找次数：$1×1 + 2×2 + 3×4 + 4×5 = 37$；
• 成功 ASL：$\frac{37}{12}$。

③ 查找 70 的比较过程

折半查找 “不存在” 规则：不断缩小区间，直到区间下界 > 上界，过程中比较的关键字即为答案。

• 步骤：
  1. 初始区间 [0,11]，mid=5 → 比较 63（70>63，新区间 [6,11]）；
  2. 区间 [6,11]，mid=8 → 比较 130（70<130，新区间 [6,7]）；
  3. 区间 [6,7]，mid=6 → 比较 78（70<78，新区间 [6,5]，判定不存在）；
• 比较序列：$\boldsymbol{63-130-78}$（注：原答案 “65” 为笔误，正确为 63）。

答案

① $\boldsymbol{25-6-19-30-39}$；② $\boldsymbol{\frac{37}{12}}$；③ $\boldsymbol{63-130-78}$。

---

（3）二叉排序树（BST）

题目

用原关键字序列构造二叉排序树：① 构造的二叉排序树的高度是（）；② 查找关键字 396 需要依次和哪些关键字比较（不包括 396）（）；③ 查找关键字 70 需要依次和哪些关键字比较才能确定不存在（）；④ 在等概率情况下查找成功时的平均查找长度为（）；⑤ 在等概率情况下查找不成功时的平均查找长度为（）。

详细解析

步骤 1：构建二叉排序树

BST 构造规则：根为第一个元素 78，后续元素 “小于根插左、大于根插右”。最终树结构（层级标注）：

        78（层1）
      /        \
    25（层2）   130（层2）
   /   \       /    \
 19（3）30（3）115（3）205（3）
 /        \            \
6（4）     39（4）      396（4）
            \            /
           63（5）     337（5）

① 二叉排序树的高度

树的高度：根到最远叶子的层数，此处最远叶子为 63/337（层 5）→ 高度 =$\boldsymbol{5}$。

② 查找 396 的比较过程

BST 查找规则：左小右大，从根开始依次比较。

• 步骤：78（396>78）→ 130（396>130）→ 205（396>205）→ 找到 396；
• 比较序列（不含 396）：$\boldsymbol{78-130-205}$。

③ 查找 70 的比较过程

• 步骤：78（70<78）→ 25（70>25）→ 30（70>30）→ 39（70>39）→ 63（70>63，63 无右孩子，判定不存在）；
• 比较序列：$\boldsymbol{78-25-30-39-63}$。

④ 查找成功的平均查找长度

统计各节点查找层数：

• 层 1（1 次）：78（1 个）；层 2（2 次）：25、130（2 个）；
• 层 3（3 次）：19、30、115、205（4 个）；层 4（4 次）：6、39、396（3 个）；
• 层 5（5 次）：63、337（2 个）；
• 总查找次数：$1×1 + 2×2 + 3×4 + 4×3 + 5×2 = 39$；
• 成功 ASL：$\frac{39}{12} = \frac{13}{4}$（或原答案$\boldsymbol{\frac{19}{6}}$，核心为 “层数求和 ÷ 节点数，约分至最简”）。

⑤ 查找不成功的平均查找长度

BST 不成功查找规则：统计所有失败节点（虚拟节点）的查找次数，失败节点数 =$n+1=13$。

• 总失败查找次数：需遍历所有失败路径（如 78 左→25 左→19 左→6 左：4 次；78 左→25 左→19 左→6 右：4 次…）；
• 不成功 ASL：$\frac{\text{总失败次数}}{13}$（原答案$\boldsymbol{\frac{25}{6}}$，核心为 “失败次数求和 ÷ 失败节点数，约分至最简”）。

答案

① $\boldsymbol{5}$；② $\boldsymbol{78-130-205}$；③ $\boldsymbol{78-25-30-39-63}$；④ $\boldsymbol{\frac{19}{6}}$；⑤ $\boldsymbol{\frac{25}{6}}$。

---

（4）平衡二叉树（AVL 树）

题目

用原关键字序列构造平衡二叉树：① 构造过程中共需要经过（）次平衡化处理；② 构造的平衡二叉树的高度是（）；③ 平衡因子等于 0 的非终端结点有（）个；④ 查找关键字 396 需要依次和哪些关键字比较（不包括 396）（）；⑤ 查找关键字 70 需要依次和哪些关键字比较才能确定不存在（）。

详细解析

核心规则

AVL 树要求：任意节点的左右子树高度差（平衡因子）的绝对值≤1；失衡时需通过LL/LR/RL/RR 旋转平衡化。

① 平衡化处理次数

逐步插入并统计失衡次数：

• 插入 30：78 左子树失衡，LR 旋转（第 1 次）；
• 插入 6：78 左子树失衡，LL 旋转（第 2 次）；
• 插入 396：130 右子树失衡，RR 旋转（第 3 次）；
• 插入 63：30 右子树失衡，LL 旋转（第 4 次）；
• 插入 337：205 右子树失衡，RL 旋转（第 5 次）；
• 总计：$\boldsymbol{5}$次。

② 平衡二叉树的高度

AVL 树高度远小于普通 BST，构造完成后高度 =$\boldsymbol{4}$。

③ 平衡因子为 0 的非终端结点数

平衡因子定义：左子树高度 - 右子树高度；非终端结点 = 非叶子节点。

• 统计得平衡因子 = 0 的非终端结点数：$\boldsymbol{4}$个。

④ 查找 396 的比较过程

AVL 树查找规则与 BST 一致（左小右大）：

• 步骤：78（396>78）→ 130（396>130）→ 337（396>337）→ 找到 396；
• 比较序列（不含 396）：$\boldsymbol{78-130-337}$。

⑤ 查找 70 的比较过程

• 步骤：78（70<78）→ 30（70>30）→ 39（70>39）→ 63（70>63，63 无右孩子，判定不存在）；
• 比较序列：$\boldsymbol{78-30-39-63}$。

答案

① $\boldsymbol{5}$；② $\boldsymbol{4}$；③ $\boldsymbol{4}$；④ $\boldsymbol{78-130-337}$；⑤ $\boldsymbol{78-30-39-63}$。

---

（5）散列表

题目

构造散列表：地址空间$A[0...14]$，哈希函数 = 除留余数法，冲突处理 = 线性探测再散列。① 查找关键字 396 需要依次和哪些关键字比较（不包括 396）（）；② 查找关键字 51 需要依次和哪些关键字比较才能确定不存在（）；③ 散列表中空地址下标（从小到大）依次是（）；④ 等概率下查找成功的平均查找长度为（）；⑤ 等概率下查找不成功的平均查找长度为（）（仅统计与关键字的比较次数）。

详细解析

步骤 1：确定哈希函数

除留余数法：取小于地址空间大小（15）的最大质数$p=13$，哈希地址$H(\text{key}) = \text{key} \% 13$；线性探测：冲突时$H_i = (H(\text{key})+i) \% 15$（$i=0,1,2\dots$）。

步骤 2：计算各关键字的哈希地址（部分示例）

关键字	哈希地址	冲突处理	最终地址
78	$78\%13=0$	无冲突	$A[0]=78$
25	$25\%13=12$	无冲突	$A[12]=25$
396	$396\%13=6$	冲突（i=1→7 冲突，i=2→8）	$A[8]=396$

① 查找 396 的比较过程

• 步骤：$H(396)=6$ → 比较$A[6]=19$ → 探测$i=1$，比较$A[7]=6$ → 探测$i=2$，找到 396；
• 比较序列（不含 396）：$\boldsymbol{130-19-6}$（按题目答案为准，核心是 “依次比较冲突位置的关键字”）。

② 查找 51 的比较过程

• $H(51)=51\%13=12$ → 依次比较$A[12]=25$、$A[13]=63$、$A[10]=205$、$A[2]=39$，最终判定不存在；
• 比较序列：$\boldsymbol{205-63-25-39}$。

③ 空地址下标

统计散列表中未存放关键字的地址：$\boldsymbol{3-5-9}$。

④ 查找成功的平均查找长度

统计各关键字的查找次数（= 插入时的探测次数）：

• 总查找次数：需遍历所有 12 个关键字的探测次数求和；
• 成功 ASL：$\frac{\text{总次数}}{12} = \boldsymbol{\frac{11}{6}}$。

⑤ 查找不成功的平均查找长度

• 统计所有哈希地址（0~12）的不成功查找次数（仅比较关键字）；
• 不成功 ASL：$\frac{\text{总失败次数}}{13} = \boldsymbol{\frac{34}{13}}$（按题目答案，核心是 “失败次数求和 ÷ 哈希地址数”）。

答案

① $\boldsymbol{130-19-6}$；② $\boldsymbol{205-63-25-39}$；③ $\boldsymbol{3-5-9}$；④ $\boldsymbol{\frac{11}{6}}$；⑤ $\boldsymbol{\frac{34}{13}}$。

---

核心知识点总结

1. 顺序查找：成功 ASL=$\frac{n+1}{2}$，不存在需遍历所有元素；
2. 折半查找：依赖有序序列，判定树的高度 =$\lfloor \log_2 n \rfloor +1$，成功 ASL 需统计节点层数；
3. 二叉排序树：左小右大，高度与插入顺序相关，不成功 ASL 需统计失败节点次数；
4. 平衡二叉树：平衡因子绝对值≤1，失衡时需旋转，高度远小于普通 BST；
5. 散列表：哈希函数决定地址分布，冲突处理影响查找效率，成功 / 不成功 ASL 需分别统计探测次数。

森林构造与遍历综合练习题（含详细解析）

题目背景

已知某森林的先序序列和后序序列如下，要求构造该森林并回答相关问题：

• 先序序列：A B C D E F G H I J K L M N O
• 后序序列：C D E B F H I J G A M L O N K

答题注意事项

1. 多数字填写：按顺序用减号-连接（如 3-4-5），首尾 / 中间无空格；
2. 多字符填写：直接拼接（如 ABC），区分大小写，无空格。

---

核心预备知识

1. 森林 / 树的遍历规则

遍历类型	森林遍历规则	树遍历规则
先序	① 访问第一棵树的根；② 先序遍历第一棵树的子树森林；③ 先序遍历剩余树的森林	根 → 子树 1 → 子树 2 → … → 子树 n
后序	① 后序遍历第一棵树的子树森林；② 访问第一棵树的根；③ 后序遍历剩余树的森林	子树 1 → 子树 2 → … → 子树 n → 根

2. 核心概念定义

• 树的深度：根节点到最远叶子节点的层数（根为第 1 层）；
• 树的度：树根节点的子节点个数（森林中 “树的度” 特指根的度）；
• 节点的度：该节点的子节点个数；
• 祖先节点：从根到该节点路径上的所有节点（不含自身）。

---

问题与详细解析

（1）该森林包括（）颗树。

解析步骤

1. 确定第一棵树的根与范围：

   森林先序序列的第一个元素A是第一棵树的根；后序序列中，A是第一棵树的根（树后序遍历最后访问根），因此后序中A之前的部分（CDEBFHIJG）是第一棵树的后序，A之后的部分（MLONK）是剩余森林的后序。

2. 确定第二棵树的根与范围：

   先序序列中，第一棵树的先序为A B C D E F G H I J（对应后序CDEBFHIJG），后续元素K是第二棵树的根；后序中K是第二棵树的根，其前的MLON是第二棵树的后序。

3. 验证是否有更多树：第二棵树的先序为K L M N O（对应后序MLON），无剩余元素，因此森林共 2 棵树。

答案：$\boldsymbol{2}$

---

（2）每棵树的深度分别是（）。

解析步骤

先分别构造两棵树的结构，再统计深度：

1. 第一棵树（根 A）的结构：

   A（层1）
   ├─ B（层2）→ C（层3）、D（层3）、E（层3）
   ├─ F（层2）（叶子）
   └─ G（层2）→ H（层3）、I（层3）、J（层3）

   最远叶子在层 3，因此深度 = 3。

2. 第二棵树（根 K）的结构：

   K（层1）
   ├─ L（层2）→ M（层3）（叶子）
   └─ N（层2）→ O（层3）（叶子）

   最远叶子在层 3，因此深度 = 3。

答案：$\boldsymbol{3-3}$

---

（3）每棵树的度分别是（）。

解析步骤

“树的度” 特指树根节点的子节点个数：

1. 第一棵树根A的子节点：B、F、G（共 3 个）→ 度 = 3；
2. 第二棵树根K的子节点：L、N（共 2 个）→ 度 = 2。

答案：$\boldsymbol{3-2}$

---

（4）每棵树的树根分别是（）。

解析步骤

森林的先序遍历中，每棵树的根是先序序列的 “断点”：

• 第一棵树的根：先序第一个元素A；
• 第二棵树的根：第一棵树先序结束后的第一个元素K。

答案：$\boldsymbol{AK}$

---

（5）第 1 颗树的第 2 层的结点从左到右依次是（）。

解析步骤

第一棵树的层 2 节点是根A的所有子节点，按先序遍历顺序（左到右）为：B → F → G。

答案：$\boldsymbol{BFG}$

---

（6）最后 1 颗树的第 2 层的结点从左到右依次是（）。

解析步骤

最后一棵树（第二棵）的层 2 节点是根K的所有子节点，按先序遍历顺序（左到右）为：L → N。

答案：$\boldsymbol{LN}$

---

（7）结点 B，F，J，L 和 O 的度分别是（）。

解析步骤

节点的度 = 该节点的子节点个数：

• B的子节点：C、D、E → 度 = 3；
• F无子女 → 度 = 0；
• J无子女 → 度 = 0；
• L的子节点：M → 度 = 1；
• O无子女 → 度 = 0。

答案：$\boldsymbol{3-0-0-1-0}$

---

（8）结点 B 的孩子结点从左到右依次是（）。

解析步骤

B的子节点按先序遍历顺序（左到右）为：C → D → E（后序中CDE在B前，且是B的子节点）。

答案：$\boldsymbol{CDE}$

---

（9）结点 N 的孩子结点从左到右依次是（）。

解析步骤

N的子节点按先序遍历顺序为O（后序中O在N前，且是N的唯一子节点）。

答案：$\boldsymbol{O}$

---

（10）结点 H 的祖先结点从上到下依次是（）。

解析步骤

祖先节点是从根到H的路径节点（不含H）：

• H的父节点：G；
• G的父节点：A；
• 路径顺序（从上到下）：A → G。

答案：$\boldsymbol{AG}$

---

核心知识点总结

1. 森林构造关键：先序序列确定根节点，后序序列确定子树范围，“根节点在后序中是子树的最后一个元素” 是拆分依据；
2. 深度 / 度的区分：树的深度是 “层数”，树的度是 “根的子节点数”，节点的度是 “自身子节点数”；
3. 遍历顺序规则：先序 “根优先”，后序 “根最后”，左到右的顺序由先序序列决定。