19. D
## 19. D
堆积现象因冲突而产生，它对存储效率、散列函数和装填因子均不会有影响，而平均查找长度会因为堆积现象而增大。散列函数是指将关键字映射到哈希地址的函数。存储效率和装填（装载）因子的定义相同，指哈希表中已存储的元素个数与哈希表长度的比值。这些因素都与堆积现象无关，而只与哈希表的结构和设计有关。
## 20. C
根据题意，得到的HT如下：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| --- | --- | --- | --- | --- | --- | --- |
| | 22 | 43 | 15 | | | |
$$
\mathrm{ASL}_{\text{成功}} = (1 + 2 + 3) / 3 = 2.
$$
## 21. C
采用线性探查法计算每个关键字的存放情况如下表所示。
| 散列地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 关键字 | 98 | 22 | 30 | 87 | 11 | 40 | 6 | 20 | | | |
由于 $H(\text{key}) = 0 \sim 6$，查找失败时可能对应的地址有7个，对于计算出地址为0的关键字 $\text{key}0$，只有比较完 $0 \sim 8$ 号地址后才能确定该关键字不在表中，比较次数为9；对于计算出地址为1的关键字 $\text{key}1$，只有比较完 $1 \sim 8$ 号地址后才能确定该关键字不在表中，比较次数为8；以此类推。需要特别注意的是，散列函数不可能计算出地址7，因此有
$$
\mathrm{ASL}_{\text{失败}} = (9 + 8 + 7 + 6 + 5 + 4 + 3) / 7 = 6
$$
## 22. D
原题再现。填装因子越大，说明哈希表中存储的元素越满，发生冲突的可能性就越高，导致平均查找长度越大。散列函数、冲突解决策略也会影响发生冲突的可能性。说法I、II、III都正确。
## 23. C
当采用开放定址法时，不能随便物理删除表中的已有元素，因为若删除元素，则可能截断其他具有相同散列地址的元素的查找地址。因此，当要删除一个元素时，可给它做一个删除标记。依次将2022.12.25插入散列表，然后删除25，得到的散列表如下：
| 地址 | 0 | 1 | 2 | 3 | 4 |
| --- | --- | --- | --- | --- | --- |
| 关键字 | | 2022 | 12 | | 25（删除） |
| 查找失败次数 | 1 | 3 | 2 | 1 | 2 |
当查找位置是删除标记时，应继续往后查找。
查找失败的平均查找长度为 $(1 + 3 + 2 + 1 + 2) / 5 = 1.8$。
## 24. A
线性探查法按顺序依次探查下一个地址，其探查序列覆盖整个散列表，因此只要表中尚有空闲位置，该方法就一定能找到一个空位，选项A正确。二次探查法的探查序列仅访问部分地址（取决于表长是否为质数等条件），即使表未满，也可能无法遍历所有位置，从而找不到空位，选项B错误。线性探查处理的冲突不仅限于同义词（散列地址相同的关键词），非同义词因探查路径重叠也
<!-- page: 339 -->
第7章 查找
327
可能发生冲突，故选项C错误；同理，二次探查处理的冲突既可能来自同义词，又可能来自非同义词，选项D中“一定发生在非同义词之间”的说法同样错误。
## 二、综合应用题
### 01. 【解答】
在散列表中删除一个记录，在拉链法情况下可以物理地删除。但在开放定址法情况下，不能物理地删除，只能做删除标记。该地址可能是该记录的同义词查找路径上的地址，物理地删除就中断了查找路径，因为查找时碰到空地址就认为是查找失败。
### 02. 【解答】
1）不能作为散列函数，因为 $\mathrm{key} / n$ 可能大于 $n$ ，这样就无法找到适合的位置。
2）能够作为散列函数，但不是一个好的散列函数，因为所有关键字都映射到同一位置，造成大量的冲突机会。
3）不能当作散列函数，因为该函数的返回值不确定，这样无法进行正常的查找。
4）能够作为散列函数，是一个好的散列函数。
### 03. 【解答】
由散列函数可知散列地址的范围为 $0\sim 10$
采用线性探测法构造散列表时，首先应计算出关键字对应的散列地址，然后检查散列表中对应的地址是否已经有元素。若没有元素，则直接将该关键字放入散列表对应的地址中；若有元素，则采用线性探测的方法查找下一个地址，从而决定该关键字的存放位置。
采用链地址法构造散列表时，在直接计算出关键字对应的散列地址后，将关键字结点插入此散列地址所在的链表。
具体解答如下。
1）线性探测法。
$H(1) = 1$ ，无冲突，地址1存放关键字1。 $H(13) = 2$ ，无冲突，地址2存放关键字13。 $H(12) = 1$ ，发生冲突，根据线性探测法： $H_{1} = 2$ ，发生冲突，继续探测 $H_{2} = 3$ ，无冲突，于是12存放在地址为3的表项中。 $H(34) = 1$ ，发生冲突，根据线性探测法： $H_{1} = 2$ ，发生冲突， $H_{2} = 3$ ，发生冲突， $H_{3} = 4$ ，没有冲突，于是34存放在地址为4的表项中。
同理，可以计算其他的数据存放情况，最后结果如下表所示。
| 散列地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 关键字 | 33 | 1 | 13 | 12 | 34 | 38 | 27 | 22 | | | |
| 冲突次数 | 0 | 0 | 0 | 2 | 3 | 0 | 1 | 7 | | | |
下面计算平均查找长度：
查找成功时，显然查找每个元素的概率都是 $1 / 8$ 。对于33，因为冲突次数为0，所以仅需1次比较便可查找成功；对于22，因为计算出的地址为0，但需要8次比较才能查找成功，所以22的查找长度为8；其他元素的分析类似。因此有
$$
\mathrm {A S L} _ {\text {成功}} = (1 + 1 + 1 + 3 + 4 + 1 + 2 + 8) / 8 = 2 1 / 8
$$
查找失败时， $H(\mathrm{key}) = 0\sim 10$ ，因此对每个位置查找的概率都是1/11，对于计算出的地址为0的关键字key0，只有探测完 $0\sim 8$ 号地址后才能确定该元素不在表中，比较次数为9；对于计算出的地址为1的关键字key1，只有探测完 $1\sim 8$ 号地址后，才能确定该元素不在表中，比较次数为8，以此类推。而对于计算出的地址为8,9,10的关键字，这些单元中没有存放元素，所以只需比较1次便可确定查找失败，因此有
<!-- page: 340 -->
2027年数据结构考研复习指导
$$
\mathrm{ASL}_{\text{失败}} = (9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 1 + 1) / 11 = 47 / 11
$$
2）链地址法构造的表如下：
在链地址表中查找成功时，查找关键字为33的记录需进行1次比较，查找关键字为22的记录需进行2次比较，以此类推。因此有
$$
\mathrm{ASL}_{\text{成功}} = (1 \times 4 + 2 \times 3 + 3) / 8 = 13 / 8
$$
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
查找失败时，对于地址0，比较3次后确定元素不在表中（空指针算1次），所以其查找长度为3；对于地址1，其查找长度为4；对于地址2，查找长度为2；以此类推。因此有
$$
\mathrm{ASL}_{\text{失败}} = (3 + 4 + 2 + 1 + 1 + 3 + 1 + 1 + 1 + 1 + 1) / 11 = 19 / 11
$$
**注意**
求查找失败的平均查找长度时有两种观点：其一，认为比较到空结点才算失败，所以比较次数等于冲突次数加1；其二，认为只有与关键字的比较才算比较次数。
04. 【解答】
由装填因子的计算公式 $\alpha = n / N$ （$n$ 为关键字个数，$N$ 为表长），不难得出表长，而根据散列函数的选择要求，$P$ 应该取不大于表长的最大素数，从而可以确定 $P$ 的大小，也就构造出了散列函数。采用链地址法解决冲突。具体解答如下。
1）由 $\alpha = n / N$ 得 $N = n / \alpha$ ，即 $N = n / \alpha \approx 15$ ，从而 $P = 13$ 。因此散列函数为 $H(\mathrm{key}) = \mathrm{key} \% 13$ 。
2）由1）求出的散列函数，计算各关键字对应的散列地址如下表所示。
| 关键字 | 26 | 36 | 41 | 38 | 44 | 15 | 68 | 12 | 6 | 51 | 25 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 散列地址 | 0 | 10 | 2 | 12 | 5 | 2 | 3 | 12 | 6 | 12 | 12 |
由此构造的链地址法处理冲突的散列表为
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
<!-- page: 341 -->
第7章 查找
329
由上图不难计算出
$$
\mathrm{ASL}_{\text{成功}} = (1 \times 7 + 2 \times 2 + 3 \times 1 + 4 \times 1) / 11 = 18 / 11
$$
$$
\mathrm{ASL}_{\失败} = (1 + 0 + 2 + 1 + 0 + 1 + 1 + 0 + 0 + 0 + 1 + 0 + 4) / 13 = 11 / 13
$$
## 05. 【解答】
1）$H_0(2) = 2, H_0(8) = 8, H_0(31) = 5, H_0(20) = 7, H_0(19) = 6$，没有冲突。$H_0(18) = 5$，发生冲突，$H_1(18) = (H_0(18) + \mathrm{REV}(18 + 1)\%11 + 1)\%13 = (5 + 3 + 1)\%13 = 9$，没有冲突。$H_0(53) = 1$，没有冲突。$H_0(27) = 1$，发生冲突，$H_1(27) = (H_0(27) + \mathrm{REV}(27 + 1)\%11 + 1)\%13 = (1 + 5 + 1)\%13 = 7$，发生冲突，$H_2(27) = (H_1(27) + \mathrm{REV}(27 + 1)\%11 + 1)\%13 = 0$，没有冲突。构造的散列表如下：
| 散列地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 关键字 | 27 | 53 | 2 | | | 31 | 19 | 20 | 8 | 18 | | | |
| 比较次数 | 3 | 1 | 1 | | | 1 | 1 | 1 | 1 | 2 | | | |
2）由1）中散列表的构造过程，各个关键字查找成功的比较次数如上表所示，所以有
$$
\mathrm{ASL}_{\text{成功}} = (3 + 1 + 1 + 1 + 1 + 1 + 1 + 2) / 8 = 11 / 8
$$
## 06. 【解答】
1）由装填因子0.7和数据总数7，得一维数组大小为 $7 / 0.7 = 10$，数组下标为 $0\sim 9$。所构造的散列函数值如下所示：
| key | 7 | 8 | 30 | 11 | 18 | 9 | 14 |
| --- | --- | --- | --- | --- | --- | --- | --- |
| H(key) | 0 | 3 | 6 | 5 | 5 | 6 | 0 |
采用线性探测再散列法处理冲突，所构造的散列表为
| 地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 关键字 | 7 | 14 | | 8 | | 11 | 30 | 18 | 9 | |
2）查找成功时，在等概率情况下，查找每个表中元素的概率是相等的。因此，根据表中元素的个数来计算平均查找长度，各关键字的比较次数如下所示：
| key | 7 | 8 | 30 | 11 | 18 | 9 | 14 |
| --- | --- | --- | --- | --- | --- | --- | --- |
| 比较次数 | 1 | 1 | 1 | 1 | 3 | 3 | 2 |
所以 $\mathrm{ASL}_{\text{成功}} = \text{查找次数/元素个数} = (1 + 2 + 1 + 1 + 1 + 3 + 3) / 7 = 12 / 7$。
在计算查找失败时的平均查找长度时，要特别注意防止思维定式，在查找失败的情况下既不是根据表中的元素个数，也不是根据表长来计算平均查找长度的。
查找失败时，在等概率情况下，经过散列函数计算后只可能映射到表中的 $0\sim 6$ 位置，且映射到 $0\sim 6$ 中任意一个位置的概率是相等的。因此，是根据散列函数（mod后面的数字）来计算平均查找长度的。在等概率情况下，查找失败的比较次数如下所示：
| H(key) | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| --- | --- | --- | --- | --- | --- | --- | --- |
| 比较次数 | 3 | 2 | 1 | 2 | 1 | 5 | 4 |
所以 $\mathrm{ASL}_{\text{不成功}} = \text{查找次数/散列后的地址个数} = (3 + 2 + 1 + 2 + 1 + 5 + 4) / 7 = 18 / 7$。
## 07. 【解答】
1）① $H(20) = 5$，装入地址5；② $H(3) = 9$，装入地址9；③ $H(11) = 0$，装入地址0；④ $H(18) = 10$，装入地址10；⑤ $H(9) = 5$，冲突，$H_{1}(9) = (5 + 1)\%11 = 6$，装入地址6；⑥ $H(14) = 9$，冲突，$H_{1}(14) = (9 + 1)\%11 = 10$，冲突，$H_{2}(14) = (9 + 4)\%11 = 2$，装入地址2。散列表如下。
<!-- page: 342 -->
2027年数据结构考研复习指导
| 散列地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 关键字 | 11 | | 14 | 7 | | 20 | 9 | | | 3 | 18 |
装填因子 $\alpha = 7 / 11$。
2）$H(14) = 9$，和关键字3比较，不命中；$H_{1}(14) = (9 + 1)\% 11 = 10$，和18比较，不命中；$H_{2}(14) = (9 + 4)\% 11 = 2$，和14比较，命中。因此，关键字比较序列是3,18,14。
3）$H(8) = 2$，和关键字14比较，不命中；$H_{3}(8) = (2 + 1)\% 11 = 3$，和7比较，不命中；$H_{2}(8) = (2 + 4)\% 11 = 6$，和9比较，不命中；$H_{3}(8) = (2 + 9)\% 11 = 0$，和11比较，不命中；$H_{4}(8) = (2 + 16)\% 11 = 7$，是空位置，确认查找失败。因此，确认查找失败时的散列地址是7。
# 归纳总结
本章的核心考点是平均查找长度（ASL），以度量各种查找算法的性能。查找算法依赖于特定的查找结构，而查找结构由相同数据类型的记录构成，因此其性能差异最终源于数据结构类型的不同。虽然各类查找算法的ASL都采用加权平均的形式，但其具体取值因结构而异。
查找成功的平均查找长度 $\mathrm{ASL}_{\mathrm{成功}} = \sum_{i=1}^{n} p_i c_i$。
查找失败的平均查找长度 $\mathrm{ASL}_{\mathrm{不成功}} = \sum_{j=0}^{n} q_j c_j$。
设一个查找集合中已有 $n$ 个数据元素，每个元素的查找概率为 $p_i$，查找成功的比较次数为 $c_i$（$i = 1,2,\dots,n$）；不在此集合中的数据元素分布在由这 $n$ 个元素划分出的 $n+1$ 个失败区间内，每个区间的查找概率为 $q_j$，查找失败的比较次数为 $c_j$（$j = 0,1,\dots,n$）。因此，对某一特定查找算法的查找成功的 $\mathrm{ASL}_{\mathrm{成功}}$ 与查找失败的 $\mathrm{ASL}_{\mathrm{不成功}}$，通常是综合考虑还是分开考虑呢？
若综合考虑，即 $\sum_{i=1}^{n} p_i + \sum_{j=0}^{n} q_j = 1$，若所有元素查找概率相等，则有 $p_i = q_j = \frac{1}{2n+1}$；若分开考虑，即 $\sum_{i=1}^{n} p_i = 1$，$\sum_{j=0}^{n} q_j = 1$，若所有元素查找概率相等，则有 $p_i = \frac{1}{n}$，$q_j = \frac{1}{n+1}$。
虽然综合考虑更为全面，但在实际应用中大多是分开考虑的，通常分别计算 $\mathrm{ASL}_{\mathrm{成功}}$ 或 $\mathrm{ASL}_{\mathrm{不成功}}$。这是因为查找失败的概率分布往往未被明确给出，容易被忽略。但读者仍需注意：两种计算方式的结果不同，考试中务必仔细审题，按要求作答，以免失误。
# 思维拓展
本章介绍了几种基本的查找算法，在实际中又会碰到怎样的查找问题呢？
题目：数组中有一个数字出现的次数超过了数组长度的一半，请找出这个数字。读者也许会想到先进行排序，位于位置 $(n + 1)/2$ 的数即要找的数，这样最小时间复杂度就为 $O(n \log_2 n)$；若进行散列查找，数字的范围又未知，则应如何将时间复杂度控制在 $O(n)$ 内呢？
# 提示
出现的次数超过数组长度的一半，表明这个数字出现的次数比其他数字出现的次数的总和还多。所以我们可以考虑每次删除两个不同的数，则在剩下的数中，待查找数字出现的次数仍然超过总数的一半。通过不断重复这个过程，不断排除其他的数字，最终剩下的都为同一个数字，即要找的数字。
<!-- page: 343 -->
第8章
# 排序
## 【考纲内容】
（一）排序的基本概念
（二）插入排序
直接插入排序；折半插入排序；希尔排序（shell sort）
（三）交换排序
冒泡排序（bubble sort）；快速排序
（四）选择排序
简单选择排序；堆排序
（五）2路归并排序（merge sort）
（六）基数排序
（七）外部排序
（八）排序算法的分析和应用
## 【知识框架】
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
视频讲解
排序
插入排序
直接插入排序
折半插入排序
希尔排序
排序
交换排序
冒泡排序
快速排序
选择排序
简单选择排序
归并排序
堆排序
外部排序——多路归并排序
## 【复习提示】
堆排序、快速排序和归并排序是本章的重点与难点。读者应深入掌握各类算法的思想、排序过程（能动手模拟）及其特性，包括初始状态的影响、时空复杂度、稳定性和适用场景等。考试通常以选择题形式考查不同算法的对比。此外，应对常用排序算法的关键代码做到熟练编写，并能根据给定序列的特点，结合算法特性选择最合适的排序方法。
## 8.1 排序的基本概念
### 8.1.1 排序的定义
排序是指将表中的元素重新排列，使其按关键字有序的过程。在许多应用中，为了便于后续查找，通常会将表组织成有序形式。排序的确切定义如下。
<!-- page: 344 -->
2027年数据结构考研复习指导
输入：$n$ 个记录 $R_{1}, R_{2}, \dots, R_{n}$，对应的关键字为 $k_{1}, k_{2}, \dots, k_{n}$。
输出：输入序列的一个重排 $R_{1}^{\prime}, R_{2}^{\prime}, \dots, R_{n}^{\prime}$，使得 $k_{i}^{\prime} \leqslant k_{2}^{\prime} \leqslant \dots \leqslant k_{n}^{\prime}$（其中“$\leqslant$”可根据需要替换为其他比较关系）。
算法的稳定性。若待排序表中有两个元素 $R_{i}$ 和 $R_{j}$，则其关键字相同（$\mathrm{key}_i = \mathrm{key}_j$），且排序前 $R_{i}$ 位于 $R_{j}$ 之前；若使用某一排序算法排序后，$R_{i}$ 仍位于 $R_{j}$ 之前，则称该排序算法是稳定的，否则，称为不稳定的。需要注意的是，稳定性并不能用来衡量算法的优劣，而只是描述其性质之一。当待排序关键字互不重复时，排序结果唯一，此时算法是否稳定就无关紧要了。