19. C
## 19. C
为使查找效率最高，每个索引块的大小应是 $\sqrt{65025} = 255$，为每个块建立索引，则索引表中索引项的个数为 255。若对索引项和索引块内部都采用折半查找，则查找效率最高，为 $\left[\log_2(255 + 1)\right] + \left[\log_2(255 + 1)\right] = 16$。
## 20. B
折半查找法在查找不成功时和给定值进行关键字的比较次数最多为树的高度，即 $\left[\log_2 n\right] + 1$ 或 $\left[\log_2 (n + 1)\right]$。在本题中，$n = 16$，所以比较次数最多为 5。
## 注意
在折半查找判定树中的方形结点是虚构的，它不计入比较的次数。
## 21. A
画出查找路径图，因为折半查找判定树是一棵二叉排序树，看其是否满足二叉排序树的要求。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
显然，选项 A 的查找路径不满足。
## 22. B
本题为送分题。
该程序采用跳跃式的顺序查找法查找升序数组中的 x。显然，x 越靠前，比较次数越少。
## 23. A
对于给定的一个有序查找表，其对应的折半查找判定树是确定且唯一的。在折半查找算法中，mid = $\lfloor (\text{low} + \text{high}) / 2 \rfloor$，因此若表中初始有 $2n + 1$ 个元素，则 mid 分割后，左右子树各有 $n$ 个元素；若表中初始有 $2n$ 个元素，则 mid 分割后，左子树有 $n - 1$ 个元素，右子树有 $n$ 个元素。即左子树的元素个数或者与右子树的元素个数相等，或者比右子树少一个。若令 mid = $\lceil (\text{low} + \text{high}) / 2 \rceil$，不难理解，左子树的元素个数或者与右子树的元素个数相等，或者比右子树多一个。对于选项 A，树中每个左子树都与右子树的结点个数相等，或者多一个结点，符合向上取整的规则。对于选项 B、C、D，存在有的左子树比右子树多一个结点，有的左子树比右子树少一个结点，不符合折半查找的规则。
## 24. B
用折半查找法查找给定值的比较次数最多不超过折半查找判定树的高度。折半查找判定树的树高 $h = \lceil \log_2(n + 1) \rceil$，将 $n = 600$ 代入，结果为 10。
## 25. D
折半查找必须满足两个条件：① 数组（或顺序表），折半查找的上一次查找和本次查找可能相
<!-- page: 288 -->
2027年数据结构考研复习指导
隔很远的距离，如依次查找下标为 $n/2, n/4, n/8, \cdots$ 的元素，若采用链表（或静态链表），则会使得时间复杂度非常高。② 有序，只有在有序的情况下才能根据上一次的比较情况舍弃一半的序列。
## 26. C
本题可直接套用书中的结论“每块记录数 $= \sqrt{n}$ 时，平均查找长度最小”。解释如下：分块查找的平均查找长度（ASL）等于查找索引表的ASL与块内查找的ASL之和。设每块含 $s$ 个元素，则块数为 $k = 400 / s$ 。总 $\mathrm{ASL} = (k + 1) / 2 + (s + 1) / 2 = (k + s) / 2 + 1$ 。要使ASL最小，需要最小化 $k + s = 400 / s + s$ 。根据均值不等式，当 $400 / s = s$ 时取最小值，解得 $s = 20$ 。
## 二、综合应用题
### 01. 【解答】
1）平均查找长度不同。因为有序顺序表查找到其关键字值比要查找值大的元素时就停止查找，并报告失败信息，不必查找到表尾；而无序顺序表必须查找到表尾才能确定查找失败。
2）平均查找长度相同。两者查找到表中元素的关键字值等于给定值时就停止查找。
3）平均查找长度不同。有序顺序表中关键字相等的元素相继排列在一起，只要查找到第一个就可以连续查找到其他关键字相同的元素。而无序顺序表必须查找全部表中的元素才能找出相同关键字的元素，因此所需的时间不同。
### 02. 【解答】
1）判定树如下图所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
2）若查找 275，依次与表中元素 509, 154, 275 进行比较，共比较 3 次。若查找 684，依次与表中元素 509, 677, 897, 765 进行比较，共比较 4 次。
3）在查找成功时，会找到图中的某个圆形结点，其平均查找长度为
$$
\mathrm {A S L} _ {\text {成功}} = \frac {1}{1 4} \sum_ {i = 1} ^ {1 4} C _ {i} = \frac {1}{1 4} (1 + 2 \times 2 + 3 \times 4 + 4 \times 7) = \frac {4 5}{1 4}
$$
在查找失败时，会找到图中的某个方形结点，但这个结点是虚构的，最后一次的比较元素为其父结点（圆形结点），所以其平均查找长度为
$$
\mathrm {A S L} _ {\text {不成功}} = \frac {1}{1 5} \sum_ {i = 0} ^ {1 5} C _ {i} ^ {\prime} = \frac {1}{1 5} (3 \times 1 + 4 \times 1 4) = \frac {5 9}{1 5}
$$
### 03. 【解答】
1）先在A[7]，A[15]，…，A[8n-1]内顺序查找，再在区间内折半查找。相应的判定树如下图所示。其中，每个关键字下的数字为其查找成功时的关键字比较次数。
2）等查找概率下，平均每个关键字查找成功的概率为 $1 / 8n$ ： $0 \sim 7$ 之间的关键字，顺序比较1次后，进行折半查找，查找成功的平均查找长度为 $2 + 3 \times 2 + 4 \times 4$ ： $8 \sim 15$ 之间的关键字，先顺序比较2次后，再进入折半查找；以此类推， $8(n - 1) \sim 8n - 1$ 之间的关键字，先顺序比较 $n$ 次，再进入折半查找，如上图所示。因此，查找成功的平均查找长度为
<!-- page: 289 -->
第7章 查找
277
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
$$
\begin{array}{l}
\mathrm{ASL}_{\text{成功}} = \frac{1}{8n} \sum_{i=0}^{8n-1} C_i = \frac{1}{8n} \left( \sum_{i=1}^{n} i + \sum_{i=2}^{n+1} i + 2 \sum_{i=3}^{n+2} i + 4 \sum_{i=4}^{n+3} i \right) \\
= \frac{1}{8n} \left( \sum_{i=1}^{n} (i + (i+1) + 2(i+2) + 4(i+3)) \right) \\
= \frac{1}{8n} \sum_{i=1}^{n} (8i+17) = \frac{1}{n} \sum_{i=1}^{n} i + \frac{17}{8} = \frac{n+1}{2} + \frac{17}{8}
\end{array}
$$
## 04. 【解答】
算法的基本思想：根据查找的起始位置和终止位置，将查找序列一分为二，判断所查找的关键字在哪一部分，然后用新的序列的起始位置和终止位置递归求解。
算法代码如下：
typedef struct{ //查找表的数据结构
ElemType *elem; //存储空间基址，建表时按实际长度分配，0号留空
int length; //表的长度
} SSTable;
int BinSearchRec(SSTable ST,ElemType key, int low, int high){
if (low&gt;high)
return 0;
mid=(low+high)/2; //取中间位置
if (key&gt;ST.elem[mid]) //向后半部分查找
BinSearchRec(ST,key,mid+1,high);
else if (key&lt;ST.elem[mid]) //向前半部分查找
BinSearchRec(ST,key,low,mid-1);
else //查找成功
return mid;
}
算法把规模为 $n$ 的复杂问题经过多次递归调用转化为规模减半的子问题求解。时间复杂度为 $O(\log_2 n)$，算法中用到了一个递归工作栈，其规模与递归深度有关，也是 $O(\log_2 n)$。
## 05. 【解答】
算法的基本思想：检索时可先从表头开始向后顺序扫描，若找到指定的结点，则将该结点和其前趋结点（若存在）交换。采用顺序表存储结构的算法实现如下：
int SegSrch(RcdType R[],ElemType k) {
//顺序查找线性表，找到后和其前面的元素交换
int i=0;
while((R[i].key!=k) &amp;&amp; (i<n)) i++)="" {="" if="" {="" }="">0) { //若找到，则交换
temp=R[i];R[i]=R[i-1];R[i-1]=temp;
return --i; //交换成功，返回交换后的位置
}
else return -1; //交换失败
}
链表的实现方式请读者自行思考。注意，链表方式实现的基本思想与上述思想相似，但要注</n))>
<!-- page: 290 -->
2027年数据结构考研复习指导
意用链表实现时，在交换两个结点之前需要保存指向前一结点的指针。
## 06. 【解析】
1）算法的基本设计思想：
从矩阵 $A$ 的右上角（最右列）开始比较，若当前元素小于目标值，则向下寻找下一个更大的元素；若当前元素大于目标值，则从右往左依次比较，若目标值存在，则只可能在该行中。
2）算法的实现：
3）比较次数不超过 $2n$ 次，时间复杂度为 $O(n)$；空间复杂度为 $O(1)$。
## 07. 【解答】
1）折半查找要求元素有序顺序存储，字符串默认按字典序排序（字典序是一种比较两个字符串大小的方法，它按字母顺序从左到右逐个比较对应的字符，若某一位可以比较出大小，则不再继续比较后面的字符，如 abd < acd、abc < abcd 等），对本题来说 do < for < repeat < while。若各个元素的查找概率不同，折半查找的性能不一定优于顺序查找。采用顺序查找时，元素按其查找概率的降序排列时查找长度最小。
采用顺序存储结构，数据元素按其查找概率降序排列。采用顺序查找方法。
查找成功时的平均查找长度 $= 0.35 \times 1 + 0.35 \times 2 + 0.15 \times 3 + 0.15 \times 4 = 2.1$。
此时，显然查找长度比折半查找的更短。
2）答案 1：采用链式存储结构时，只能采用顺序查找，其性能和顺序表一样，类似于上题。数据元素按其查找概率降序排列，构成单链表。采用顺序查找方法。
查找成功时的平均查找长度 $= 0.35 \times 1 + 0.35 \times 2 + 0.15 \times 3 + 0.15 \times 4 = 2.1$。
答案 2：还可以构造成二叉排序树的形式。采用二叉链表的存储结构，构造二叉排序树，元素的存储方式见下图。采用二叉排序树的查找方法。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
二叉排序树1
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
二叉排序树2 二叉排序树 查找成功时的平均查找长度 $= 0.15 \times 1 + 0.35 \times 2 + 0.35 \times 2 + 0.15 \times 3 = 2.0$。 ## 7.3 树形查找 ### 7.3.1 二叉排序树（BST） 构造一棵二叉排序树的主要目的并非直接输出有序序列，而是利用其有序结构支持高效的动态查找、插入和删除操作。这种非线性结构有利于实现快速的数据访问。 <!-- page: 291 --> 第7章 查找 279 # 1. 二叉排序树的定义 **考虑信息** ▶ 二叉排序树的应用（2013） 二叉排序树（也称二叉查找树）或者是一棵空树，或者是具有下列特性的二叉树： 1）若左子树非空，则左子树上所有结点的关键字均小于根结点的关键字。 2）若右子树非空，则右子树上所有结点的关键字均大于根结点的关键字。 3）左右子树也分别是一棵二叉排序树。 **考虑信息** ▶ 二叉排序树中结点值之间的关系（2015、2018、2024） 基于上述定义，对二叉排序树进行中序遍历可以得到一个递增的有序关键字序列。例如，图7.4所示二叉排序树的中序遍历序列为1,2,3,4,6,8。 # 2. 二叉排序树的查找 二叉排序树的查找是从根结点开始，逐层向下比较并选择左/右子树的搜索过程。若二叉排序树非空，先将给定关键字与根结点的关键字比较：若相等，则查找成功；若不等，小于根结点的关键字，则在根结点的左子树上查找，否则在根结点的右子树上查找。这一过程具有天然的递归结构，也可以用循环实现。以下是用循环实现二叉排序树查找的代码示例：
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图7.4 一棵二叉排序树 例如，在图7.4中查找关键字为4的结点。首先4与根结点6比较。因为 $4 < 6$，所以在根结点6的左子树中继续查找。因为 $4 > 2$，故在结点2的右子树中继续查找，该子树的根结点即为4，查找成功。 同样，二叉排序树的查找也可用递归算法实现，其实现较为简单，但由于递归可能导致较大的枝空间开销，执行效率较低。具体的代码实现留给读者思考。 # 3. 二叉排序树的插入 二叉排序树作为一种动态树表，其结构通常不是一次性生成的，而是在查找过程中动态构建：当查找失败（树中不存在关键字等于给定值的结点）时，才执行插入操作。 插入结点的过程如下：若原二叉排序树为空，则将新结点作为根结点直接插入；否则，从根结点开始比较，若关键字 $k$ 小于当前结点的关键字，则在左子树中继续查找并插入；若 $k$ 大于当前结点的关键字，则在右子树中继续查找并插入。新插入的结点在插入完成后一定是一个叶结点，且恰好是查找失败时所访问的最后一个结点的左孩子或右孩子。如图7.5所示，在一棵二叉排序树中依次插入结点28和58，虚线所示路径即为每次插入前的查找路径。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图7.5 向二叉排序树中插入结点 <!-- page: 292 --> 2027年数据结构考研复习指导 二叉排序树插入操作的算法描述如下：## 4. 二叉排序树的构造 **考点点击：** 构造二叉排序树的过程（2020） 从一棵空树开始，依次将给定元素插入二叉排序树的合适位置（重复关键字将被忽略）。设插入的关键字序列为{45, 24, 53, 45, 12, 24}，则生成的二叉排序树如图 7.6 所示。int BST_Insert(BiTree &amp;T,KeyType k) { if (T==NULL) { //原树为空，新插入的记录为根结点 T=(BiTree)malloc(sizeof(BSTNode)); T-&gt;data=k; T-&gt;lchild=T-&gt;rchild=NULL; return 1; //返回 1，插入成功 } else if (k==T-&gt;data) //树中存在相同关键字的结点，插入失败 return 0; else if (k<t->data) //插入 T 的左子树 return BST_Insert(T-&gt;lchild,k); else //插入 T 的右子树 return BST_Insert(T-&gt;rchild,k); }
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 7.6 二叉排序树的构造过程 构造二叉排序树的算法描述如下： ## 5. 二叉排序树的删除 在二叉排序树中删除一个结点时，不能把以该结点为根的子树都删除，而必须将该结点从存储结构中摘下，并重新连接因删除操作而断裂的链表，同时确保整棵树仍满足二叉排序树的性质。删除操作需根据被删结点的不同情况分别处理，具体分为以下三种情形： ① 若被删结点 $z$ 是叶结点，则直接删除即可，不会破坏二叉排序树的性质。 ② 若结点 $z$ 仅有一棵非空子树（左子树或右子树），则将其唯一的子树上移，作为 $z$ 的父结点的新子树，从而替代 $z$ 的位置。 ③ 若结点 $z$ 同时具有左右两棵子树，则可用 $z$ 的直接后继或直接前驱（分别为中序遍历中的下一个或上一个结点）来替代 $z$。替换完成后，再从树中删除该直接后继（或前驱）。由于直接后继（或前驱）至多只有一个子树，这样就转化为第①或第②种情况。</t-> <!-- page: 293 --> 第7章 查找 281 图 7.7 展示了分别删除结点 45, 78, 78 的过程。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 7.7 3 种情况下的删除过程 **骨架图12** ▶ 二叉排序树中删除并插入某结点的分析（2013） 思考：若在二叉排序树中删除某结点，再重新插入，所得的二叉排序树是否与原树相同？ ## 6. 二叉排序树的查找效率分析 二叉排序树的查找效率主要取决于树的高度。若左右子树高度之差的绝对值不超过 1（见下一节的平衡二叉树），其平均查找长度为 $O(\log_2 n)$。在最坏情况下，若构造二叉排序树的输入序列是有序的，则会形成一个只有右孩子（或只有左孩子）的单支树，此时树的高度为 $n$，性能显著下降，平均查找长度退化为 $(n + 1)/2$，如图 7.8(b)所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图 7.8 相同关键字组成的不同二叉排序树
<!-- page: 294 -->
2027年数据结构考研复习指导
在等概率情况下，图7.8(a)查找成功的平均查找长度为
$$
\mathrm{ASL}_a = (1 + 2 \times 2 + 3 \times 4 + 4 \times 3) / 10 = 2.9
$$
而图7.8(b)查找成功的平均查找长度为
$$
\mathrm{ASL}_b = (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10) / 10 = 5.5
$$
从查找过程来看，二叉排序树与二分查找相似。就平均时间性能而言，二者相近。但二分查找所对应的判定树是唯一的，而由相同关键字集合可能生成不同的二叉排序树——其具体形态取决于关键字的插入顺序，如图7.8所示。
就维护表的有序性而言，二叉排序树无须移动结点，仅需修改指针即可完成插入和删除操作，平均时间复杂度为 $O(\log_2 n)$。而二分查找的对象是有序顺序表，若需执行插入或删除操作，必须移动大量元素，时间复杂度为 $O(n)$。因此，当表为静态查找表时，宜采用顺序表存储并使用二分查找；若表为动态查找表（需频繁插入或删除），则应选择二叉排序树作为其逻辑结构。