一、习题答案

（一）选择题

1.C。本题考查顺序查找法的平均查找长度。由题干知查找n个关键字的概率是相等的，因此对于每个关键字的查找概率均为1/n。在表中第一个关键字的比较次数为1，以后的每个关键字的比较次数比前一个多1，一共n个记录，因此由等差数列求和公式可得所有记录比较次数的总和为（1+n）n/2，则平均查找长度为（1/n）×（1+n）n/2=（n+1）/2。

2.D，C。本题考查顺序查找法和折半查找法的平均查找长度。

1）顺序查找法的平均查找长度在第1题中已经讲过，答案选D。

2）根据折半查找法的执行过程可以做出一棵二叉树，即折半查找判定树，如果将这个二叉树的最底层结点去掉，则这棵二叉树是一棵满二叉树，而查找过程就是走了从根结点到树中某一结点的一条路径，路径上结点的个数就是关键字的比较次数。对于这棵二叉树，其高度为log₂n+1，这是表中关键字的最大比较次数，则折半查找的平均查找长度应该不大于log₂n+1，由此可知答案选C。

3.D。本题考查折半查找的适用情况。

选项A，折半查找是基于随机存储方式的算法，必须用顺序表而不能用链表，因此A错。

选项B，折半查找表要求元素有序，但没有要求其表中元素是递增有序还是递减有序。由折半查找的判定树也可以看出，只要根结点能将树中结点分为两部分，一部分结点值大于根结点值，一部分结点值小于根结点值即可，而没有左子树结点值必须小于右子树结点值这样的特殊规定，因此B错。

选项C，折半查找方法只要求关键字有序，而对关键字的数据类型没有规定，因此C错。

4.D。本题考查折半查找法与顺序查找法的性能比较。对于同一个表，如果找的是表中的第一个元素，则用顺序查找方法一定比折半查找快；如果找的是表中的最后一个元素，则用顺序查找方法一定比折半查找方法慢。因此本题选D。

5.A。本题考查折半查找平均查找长度的计算。我们可以假设关键字序列为{1，2，3，4，5，6，7，8，9，10，11，12}，只要表中的关键字个数相同，就一定会生成形状相同的判定树。这里的形状相同是指两棵树的结构是一样的，但同一位置上的结点的值可以不一样。判定树只要形状相同，平均查找长度就相同，含有12个关键字的有序表必然可以生成与图9-31所示的树形状相同的判定树。

由图9-31所示的判定树可以得出各关键字的比较次数，关键字的比较次数即为关键字在树中的层数。由此可以得出：

图9-31 选择题第5题答案

因此ASL=（3+4+2+3+4+1+3+4+2+4+3+4）/12=37/12，故本题选A。

6.D。本题考查折半查找算法的时间复杂度。由第2题的讲解可知，对规模为n的有序表进行折半查找的平均查找长度不大于log₂n+1。在不做特殊说明的情况下，算法的时间复杂度就是最坏情况下基本运算的执行次数f（n）。查找中基本运算为关键字的比较，因此对于折半查找，最坏情况下的比较次数f（n）=log₂n+1，折半查找算法的时间复杂度为O（log₂n）。因此本题选D。

7.C。本题考查二叉排序树的建立。对于这类选择题，其实不需要对每个选项都画出相应的二叉排序树之后再进行比较，直接观察选项即可。经过观察可知，选项A、B、D中根结点的左孩子结点为80，而选项C中根结点的左孩子结点为60，至此即可判断选项C所构造的二叉排序树一定和其他3项不同，因此本题选C。

8.C。本题考查平衡二叉树的平衡调整。由题意可知，在插入前，A的平衡因子为-1，A的右孩子（图9-32左图中的结点C）的平衡因子为0；插入结点后（新结点插入在D的子树上，图中没有画出）A的平衡因子变为-2，C的变为1。结点必插入到C的左子树上，A、C、D是需要进行平衡调整的3个结点。图9-32中虚线框内所示的A、C、D3个结点构成的子树需要进行RL型平衡调整，因此本题选C。

图9-32 选择题第8题答案

结点D中关键字大于A小于C，因此将D作为根，A、C分别为其左、右子树。此时A空出来一个右指针，C空出来一个左指针，而③、④变成了两棵独立的树。③中关键字都小于④中关键字，即在最终树中，③应该在④的左边。因此，③应该挂在A的右指针上，④应该挂在C的左指针上，最终结果如图9-32右图所示。

9.B。本题考查B-树的定义及插入操作。

m阶B-树的根结点至少有两棵子树，并且这两颗子树可以是空树，其余结点至少有m/2个分支，即m/2棵子树，因此①不对。

每个结点中关键字的个数比分支数少1，m阶B-树的一个结点中至多有m个分支，因此最多有m-1个关键字，因此②正确。

B-树是平衡的多路查找树，叶子结点均在同一层上，因此③正确。

发生结点分裂的时候不一定会使树长高。例如，向图9-33a中的B-树插入一个关键字10，变成图9-33b中的B-树，使得第二层右端的一个结点分裂成两个，但是树并没有长高，因此④不对。

图9-33 选择题第9题答案

a）原B-树 b）插入一个关键字后的B-树

10.C。本题考查B-树和B+树的性质。由定义知选项A、B、D正确。B+树所有的叶子结点包含了全部的关键字信息，且叶子结点本身依照关键字的大小自小而大顺序连接，可以进行顺序查找，而B-树则不可以，因此选项C错误。

11.B。本题考查B-树的定义。m阶B-树说明每个结点至多有m个分支，B-树的所有叶子结点都在同一层上。因此，m阶B-树是一棵m叉平衡排序树，故本题选B。

12.A。本题考查B-树的定义。在m阶B-树中，除了根结点以外，其余结点的分支数为m/2≤S≤m，因此本题选A。

13.D。本题考查用除留余数法的Hash函数以及链地址法的冲突解决方法来建立Hash表的过程。只需用各个关键字与13做取余运算，结果为1的就是地址为1的链中的关键字，经运算可知14、1、27，79将被插入到地址为1的链中，因此本题选D。

14.A，C。本题考查用链地址法处理冲突。由Hash函数可知，地址范围为0～16，有17个地址，需要17个链表，因此本题选A、C。

15.C。本题考查Hash冲突的处理方法。

如果两个元素在同一个链表中，查找时间肯定不相同，因此①不正确。

若插入规定在链首，则插入操作不需要查找插入位置即可直接进行，因此插入任何一个元素的时间均相同，因此②正确。这是相对于链表的尾插法而言的，在尾插法中，需要找到链表的尾部，因此链表的长度决定了插入元素的执行时间。

所谓堆积问题，即在Hash表的建立过程中，某些Hash地址是由冲突处理产生的，而不是由Hash函数直接产生的，这就可能造成原本Key₁与Key₂虽然不是同义词，但是最后却得出了相同的Hash地址。例如，在线性探查法处理冲突的过程中，设第一个同义词占用单元d，这之后连续的若干同义词将占用Hash表的d、d+1、d+2等单元，此时随后任何d+1、d+2等单元上的Hash映射都会由于前面的同义词堆积而产生冲突，尽管随后的这些关键字并没有同义词，因此④不正确。显然链地址法不会产生堆积现象，因为多个同义词只会占用表中的一个地址，因此③不正确。

说明：在考研数据结构的考题中，如果问链地址法会不会产生堆积现象，答案是不会；如果问堆积现象可不可以完全避免，答案是不可以。关于这个问题的解释在本章某题答案解释处，各位认真做完本章的题目后自然会找到。

16.D。本题考查Hash表的构造方法，以及冲突处理方法。已含有关键字15、38、61、84的Hash表如下：

因H（49）=49 Mod 11=5，地址5处已经存在关键字，发生冲突，则另探查起始位置d=5并按照以下地址序列进行探查：d+1²，d-1²，d+2²，d-2²……经探查知d+2²=9处有空位置，因此49最终在Hash表中的位置为9处，故本题选D。

说明：本题在添加结点序列15、38、61、84的时候没有发生冲突，因此处理起来比较简单，有的题目在这个过程中也存在冲突，需要用题目要求的方法进行冲突解决。考生在这里需要注意，这里容易出错。

17.D。本题考查Hash冲突解决方法中的线性探查法。在不发生堆积现象的时候，k个互为同义词的关键字中，第一个关键字需要探查一次，以后的关键字均比前一个关键字要多探查一次，则每个关键字需要探查的次数构成一个首项为1、公差为1、项数为k的等差数列，因此总共需要k（k+1）/2次探查。如果在这个过程中发生了堆积现象（如图9-34所示，发生了堆积，a占据了k_i+1的地址，则k_i+1的探查次数将比没有发生堆积现象的时候多1次），则会发生更多的探查，因此至少需要探查k（k+1）/2次，故本题选D。

图9-34 选择题第17题答案

18.D。本题考查构造Hash函数应遵循的原则。这个原则在知识点讲解中并没有明确提到，但是应该知道，Hash函数要尽可能地减少冲突的发生来提高查找的效率。如何减少冲突的发生呢？所谓冲突，通俗来讲就是关键字在表中扎堆，即关键字经Hash函数处理后落在表中各个位置上的概率不相等。因此要减少冲突，应当使得函数值以等概率取其值域中的每个值。这种题目就需要根据已有知识来推理得出答案，考生在学习的过程中要重在理解。

19.D，C。本题考查Hash表的建立以及冲突处理。先用59之前的关键字建表过程如下：

H（26）=9，不冲突；H（25）=8，不冲突；H（72）=4，不冲突；H（38）=4，冲突，冲突处理后地址为5；H（8）=8，冲突，冲突处理后地址为10；H（18）=1，不冲突。当放入关键字59时，H（59）=8，冲突，后移一位得地址9也冲突，继续后移得地址10也冲突，继续后移得地址11不冲突。因此59在表中的地址为11，共探查4次，故本题选D、C。

20.C。本题考查装填因子的性质。装填因子越大，则越可能发生冲突（这是显而易见的，装填因子大，证明表中的关键字多，而空位置少，所以冲突容易发生）；装填因子越小，则冲突发生的可能性越小。但是不论什么情况都不能绝对避免冲突，因此本题选C。

21.B。本题考查顺序查找所使用的存储结构。顺序查找方法适应于线性表，用顺序表或者链表来表示的线性表它都适应，因此本题选B。

22.C。本题考查二分查找法所适用的表的特点。二分查找要求查找对象采用顺序存储结构，并且元素有序，因此本题选C。

23.C。本题考查二分查找的过程。解决此类题目最保险的方法是构造二分查找判定树，虽然这样速度有点慢，但是不容易出错，本题的判定树如图9-35所示。

图9-35 选择题第23题答案

由图9-35所示的判定树可知，找到82时，共进行了4次比较，因此本题选C。

24.D。本题考查二分查找的过程。本题可以通过构造二分查找判定树来解决，这里采用另一种方法，直接计算比较序列下标。第一次：（1+18）/2=9，下一次查找子区间为1～8；第二次：（1+8）/2=4，下一次查找子区间为1～3；第三次：（1+3）/2=2，下一次查找子区间为3～3；第四次：（3+3）/2=3。因此，比较序列下标为9，4，2，3，故本题选D。

25.D。本题考查二叉排序树的查找过程。可以根据选项画出查找路线上的结点，根据二叉排序树的规定来排除不满足条件的选项。根据题目选项所得查找路线如图9-36所示。

选项A中28的右子树中出现了小于它的18，不满足二叉排序树规定，排除。

选项B中36的左子树中出现了大于它的46，不满足二叉排序树规定，排除。

选项C中28的左子树中出现了大于它的36，不满足二叉排序树规定，排除。

因此本题选D。

图9-36 选择题第25题答案

a）选项A b）选项B c）选项C d）选项D

26.C，A。本题考查二叉排序树平均查找长度的计算。由题意进行如下分析：查找成功：

查找成功时的平均查找长度=（1+2+2+3+3+4）/6=15/6。

查找失败：

查找失败时的平均查找长度=（3+3+4+4+3+2+2）/7=21/7。

27.A。本题考查平衡因子的定义以及平衡二叉树的定义。结点的平衡因子为其左子树与右子树的高度之差。平衡二叉树其左、右子树都是平衡二叉树，且左、右子树高度之差的绝对值不超过1。因此本题选A。

28.B。本题考查平衡因子的定义以及平衡二叉树的定义。计算出各结点的平衡因子如图9-37所示。

图9-37 选择题第28题答案

a）选项A b）选项B c）选项C d）选项D

由各结点平衡因子可知选项B中的二叉树为平衡二叉树。

29.B。本题为平衡二叉树知识的扩展，属于考纲模糊范围内的考点。设N_h表示高度为h的平衡二叉树中含有的最少结点数，则有

N₀=0，N₁=1，N2=2，…，N_h=N_h-1+N_h-2+1

由以上递推公式可知N₅=12。因此本题选B。

30.D。本题为平衡二叉树知识的扩展。由第29题的公式N₀=0，N₁=1，N₂=2，…，N_h=N_h-1+N_h-2+1可以算出N₃=4，N₄=7，N₅=12。也就是说，12个结点的平衡二叉树中叶子结点的最小层数为3，最大层数为5，又由于35是存在的，因此最多查找5次就一定能找到，可以排除A、B、C三项。

31.C。本题为平衡二叉树知识的扩展。根据第29题的公式有N₃=4，N₄=7，N₅=12，N₆=20＞15。也就是说，高度为6的平衡二叉树最少有20个结点，因此15个结点的平衡二叉树的最大高度为5，而最小叶子结点的层数为3，所以选项A错。而选项B和D的查找过程不能构成二叉排序树，因此错误。

说明：在第29、30、31三个题中，介绍了一个公式，即N_h表示高度为h的平衡二叉树中含有的最少结点数，有

N₀=0，N₁=1，N₂=2，…，N_h=N_h-1+N_h-2+1

通过本公式可以确定一定高度的平衡二叉树的最少结点数。例如，N₅=12，即表示高度为5的平衡二叉树中最少有12个结点，可以做出此平衡二叉树，如图9-38所示。

以上树形中反映的信息有助于解决相关题目，这一点在第29、30、31三个题中体现得非常明显。

32.D。本题考查平衡因子与满二叉树知识的综合应用。由于每个非叶子结点的平衡因子均为0，也即每个非终端结点都有左子树和右子树，且高度相等，因此这样的平衡二叉树为满二叉树，而高度为k的满二叉树的结点为2^k-1。

图9-38 高度为5的平衡二叉树

33.C。本题考查平衡二叉树的查找效率。二叉排序树的查找效率取决于其高度。对于结点个数相同的二叉排序树，平衡二叉树的高度最小，因此效率最高。

34.A。本题考查Hash表的查找效率。Hash查找法是由关键字结合Hash函数和冲突处理方法直接算出关键字在表中的位置，与表的长度n无关，其查找的时间复杂度对于n为常量级，即O（1）。

（二）综合应用题

1.基础题

（1）答

构造出来的二叉排序树与原来的相同。

因为二叉排序树是二叉树，它的前序序列的第一个元素一定是二叉排序树的根，而对应前序序列的根后面的所有元素分为两组：从根的后一元素开始，其值小于根的值的一组元素就是树的左子树的结点的前序序列，剩下的元素的值大于根的值，即为树的右子树的结点的前序序列。在把前序序列的元素依次插入初始为空的二叉排序树时，第一个元素就成为树的根，它后面第一组元素的值都小于根结点的值，可以递归建立根的左子树；第二组元素的值都大于根结点的值，可以递归地建立根的右子树。最后插入的结果就是一棵与原来二叉排序树相同的二叉排序树。

（2）答

1）最小元素必无左子女，最大元素必无右子女，此命题正确。

根据二叉排序树的定义，二叉排序树的根结点的关键字值一定大于左子树（若非空）上所有结点的关键字值，同时一定小于右子树（若非空）上所有结点的关键字值，而根结点的左、右子树也是二叉排序树。这是一个递归的定义。因此寻找最小元素的过程可以是一个递归的过程，逐层查找树（或子树）根结点的左子树，直至根结点的左子树空为止，这个子树的根结点就是最小元素所在结点，它无左子女；同样，寻找最大元素的过程也可以是一个递归的过程，逐层查找树（或子树）根结点的右子树，直至根结点的右子树空为止，这个子树的根结点就是最大元素所在结点，它无右子女。

2）最小元素和最大元素不一定是叶结点。

具有最小关键字值的结点可以有右子树，具有最大关键字值的结点可以有左子树。

3）一个新元素总是作为叶结点插入二叉排序树的。

在插入新元素时，插入算法总是先调用查找算法，从根开始查找是否具有相等关键字值的结点，如果查找成功，则不插入；如果查找失败，则新结点作为叶结点插入到刚刚查找失败的位置。

（3）分析

1）查找长度不同。原因：扫描有序表，只要发现第一个比关键字大的值，即可结束扫描，无须扫描整个表，因此平均查找长度与无序表不同。

2）查找成功时，对于两种表都是逐个扫描关键字，直到找到与给定的Key相同的关键字为止，因此平均查找长度均为（n+1）/2。

3）有序表中相同关键字在表中的位置一定是相邻的，而无序表中相同关键字是随机散落在表中的。因此，对于有序表，找到第一个与Key相同的元素后，只需继续扫描，找到最后一个与Key不相同的元素即可；而对于无序表，则需要扫描整个表。对于无序表的平均查找长度为n+1，而对于有序表则小于n+1。

答：

1）不同，有序顺序表为（n+1）/2，无序顺序表为n+1。

2）相同，有序顺序表为（n+1）/2，无序顺序表也为（n+1）/2。

3）不同，有序顺序表小于n+1，无序顺序表为n+1。

（4）分析

此题为简单的Hash构造题目，按照之前所讲的方法直接构造即可。

1）由装填因子a=0.75，表中元素个数n=11，得表长为n/a=15。p取不大于表长的最大素数，因此p为13。

所构造的Hash函数为H（Key）=KeyMod13。

由Hash函数求各关键字的Hash地址如下：

{26，36，41，38，44，15，68，12，6，51，25}

H（26）=0，H（36）=10，H（41）=2，H（38）=12，H（44）=5，H（15）=2，H（68）=3，H（12）=12，H（6）=6，H（51）=12，H（25）=12。(www.daowen.com)

由此可以构造出用链地址法处理冲突的Hash表，如图9-39所示。

图9-39 基础题第（4）题答案

2）由图9-39可知，ASL₁=（1+1+2+1+1+1+1+1+2+3+4）/11=18/11。

3）ASL₂=（1+0+2+1+0+1+1+0+0+0+1+0+4）/13=11/13。

（5）分析

本题是一般的除留余数法的变形，可以先将关键字散列到0～9的范围内，然后向右平移100个单位，即可散列到100～109内。

设Hash函数为H（key）=keyModp+100，因表长为10，p取不大于表长的最大素数即7，因此得Hash函数为H（key）=keyMod7+100。

所得的Hash表见表9-13。

表9-13 基础题第（5）题所得的Hash表

用线性探测在散列解决冲突时，查找成功时的平均查找长度ASL=（1+2+1+1+1+1+2+3+5+10）/10=27/10。

（6）分析

本题考查一般的B-树建立，按照例题中所讲的步骤解题即可。

3阶B-树的结点中，关键字个数范围为1～2。按照关键字序列逐个插入后所得的B-树如图9-40所示。

图9-40 基础题第（6）题答案

（7）分析

由B-树的定义可知，根结点最少有两个分支，其余结点分支数为m/2～m个。因此，第一层有1个结点，第二层至少有2个结点，第三层有2×m/2个结点，第四层有2×m/2²个结点……第h+1层至少有2×m/2^h-1个结点（h≥2）。结点总数为：

N=1+2+2×m/2+2×m/2²+…+2×m/2^h-1=2×（1-m/2^h）/（1-m/2）+1

注意：高度为h的B-树有h+1层，因本书规定高度不包含叶子结点层，这在不同的书中有不同的规定。有的书中高度包含叶子结点层，则高度为h的B-树有h层。这需要考生根据自己目标学校的指定参考书或者历年考卷来确定其具体规定。

（8）分析

在平衡二叉树上查找关键字Key，走了一条从根到叶子的路径，时间复杂度可以通过树的高度来反映，是O（log₂n）。在中序遍历输出的序列中查找关键字Key，如果采用顺序查找，则时间复杂度是O（n）；如果采用折半查找，则时间复杂度是O（log₂n）。

按序输入建立的二叉排序树，因为插入元素是有序的，因此所有的插入操作都会发生在最左边的叶子结点的左指针上，或者最右边的叶子结点的右指针上，这样所形成的二叉排序树蜕变为单枝树，折半查找也蜕变成了顺序查找，如图9-41所示，其平均查找长度是（n+1）/2，时间复杂度是O（n）。

图9-41 按序列{3，4，6，8，9，10} 所建立起的二叉排序树

（9）分析

按照二叉排序树的插入算法将关键字逐个插入树中，在发生不平衡现象的时候进行平衡调整，最后即可得到平衡二叉树，操作步骤如下：

1）插入关键字xal、wan、wil后发生不平衡现象，进行调整，如图9-42所示。

2）插入关键字zol、yo后发生不平衡现象，进行调整，如图9-43所示。

图9-42 基础题第（9）题答案一

图9-43 基础题第（9）题答案二

3）插入关键字xul后发生不平衡现象，进行调整，要特别注意结点xul的连接，调整后wil和yo两个结点都有空闲指针，xul应该连接在yo的左指针上，因为xul大于xal，结果如图9-44所示。

4）插入关键字yum、wen后发生了不平衡现象，调整后如图9-45所示。

图9-44 基础题第（9）题答案三

图9-45 基础题第（9）题答案四

5）插入关键字zi后发生了不平衡现象，调整后如图9-46所示。

图9-46 基础题第（9）题答案五

6）插入最后一个关键字yon，发生了不平衡现象，进行调整。要特别注意的是，调整后yon应该连接在yo的右指针上，而不是zi的左指针上，因为yon比yum小。调整后的最终结果如图9-47所示。

图9-47 基础题第（9）题答案六

由图9-47右图可得各个关键字的比较次数为：

则查找成功时的平均查找长度ASL=（1+3+3+4+3+4+2+2+4+3+4）/11=33/11=3。

说明：本题为了让读者容易理解，整个过程写得比较详细，篇幅较大。如果题目不要求写出中间过程，则只画出最终的平衡二叉树即可。

（10）解析

实际上，增设的lsize域里面记入的就是以该结点为根的子树中该结点的次序。含有lsize域的结点定义如下：

算法描述如下：

2.思考题

（1）解析

向以t为根的二叉排序树中插入一个元素x（假设x用int型来表示），若树中已经有该元素，则将匹配结点中的count域的值加1，否则该元素作为新结点插入。算法描述如下：

（2）解析

根据二叉排序树的特点，查找路径只可能沿某一结点的左分支或右分支逐层向下查找，而不可能在两个分支之间横向跳跃或往上回溯。查找范围应在给定关键字值的上下波动，不断接近给定关键字值，并且在结点左子树上的关键字值不会大于结点的关键字值，右子树上的关键字值不会小于结点的关键字值。

例如，给定一个值60，在二叉排序树上寻找关键字值为60的结点时，访问的关键字值序列S={20，30，90，80，40，50，70，60}。若将S分为两个子序列，S1所包含的都是小于或等于60的数据，S1={20，30，40，50，60}；S2所包含的都是大于60的数据，S2={90，80，70}。如此可得判断是否是查找序列的原则：如果从S所生成的S1单调递增，S2单调递减，且除待查元素外，S1中的每个数据都小于给定值，S2中的每个数据都大于给定值，则S是一个查找序列，否则不是查找序列。算法描述如下：

二、真题精选答案

（一）选择题

1.D。选项D描述的是B+树的特点，而不是B-树的特点。

2.B。折半查找法在查找不成功时和给定值进行比较的关键字个数最多为log₂n+1，即折半查找判定树的高度。在本题中，n=16，故比较次数最多为5。

3.B。要提高查找效率，就要减少Hash表的冲突，因此②是正确的措施。对于①，装填因子增大，则相应的表中空闲位置就少，更容易发生冲突，因此①不对。堆积现象是不可避免的，因此③不对。

说明：在去年本书微信公众平台的读者反馈中，有不少同学提出堆积现象可以通过使用链地址法来避免，因此③也是对应的这个异议。的确，在使用链地址法时，不会产生堆积现象，但是在处理实际问题时，不可能完全抛弃线性探测法而只使用链地址法，两种方法各有自己的适用条件。堆积现象不可避免是针对可能出现的所有情况而言的，这个范围包括只能用链地址法来处理的问题，也包括只能用线性探测法来处理的问题，面对只能用线性探测法来处理的问题，当然堆积现象是不可避免的。打个不太严谨的比喻，要避免交通事故，禁止使用交通工具是行不通的。

4.D。

说明：本题在不同版本的试卷中可能有不同的题干描述，即有的会把本题题干中的终端结点说成叶子结点，其实指的就是图中画出的最底层的结点，这与本书的规定是不同的。本书规定叶子结点不含关键字，是查找失败的位置。所以解题的时候要善于根据题干来判断具体规定，但在国内不同学校、不同版本的教材中，该处可能有不同的规定。

5.A。一棵高度为2的5阶B-树，根结点只有到达5个关键字的时候才能产生分裂，成为高度为2的B-树。

注意：B-树的阶数是人为规定的，而不是因当前B-树中结点所含有的最大分支数而定。严格来说，本题B-树画出来应该如图9-48所示，每个结点都最多可以包含4个关键字，只是当前状态中还没有一个结点达到这个关键字个数。

图9-48 一棵5阶B-树

说明：在考研数据结构中，如果题目说了B-树的阶数是多少，就认为是多少，不因当前树中结点的最大分支数而变；如果没有明确说而是画出了一棵树，则根据树中分支最多的结点来确定其阶数。

注意：本题所体现的难度并不在于题目本身，而是不同参考书中对B-树高度规定的不同而给考生造成的困惑，有的参考书（如严蔚敏版数据结构）规定B-树高度包含叶子结点层，根据本题题意，高度为2，而叶子结点层不含关键字，所以只有一个非叶结点，即根结点，其关键字最少为1，没有答案。显然本题规定高度不包含叶子结点层，就如图9-48所示，图中没有画出叶子结点层，实际上这棵高度为2的B-树有3层。本题也很好地体现了如何克服因规定不同而造成的解题困难。

（二）综合应用题

1.解析

（1）因为装填因子为0.7，数据总数为7，所以存储空间长度为7/0.7=10。因此可选表长m=10。

分别计算各个数据元素的散列地址：

H（7）=（7×3）%7=0，一次比较到位。

H（8）=（8×3）%7=3，一次比较到位。

H（30）=（30×3）%7=6，一次比较到位。

H（11）=（11×3）%7=5，一次比较到位。

H（18）=（18×3）%7=5，冲突；探测下一位置6，冲突；探测下一位置7，3次比较到位。

H（9）=（9×3）%7=6，冲突；根据上一步的探测结果可知，最终位置为8，3次比较到位。

H（14）=（14×3）%7=0，冲突；探测下一位置1，两次比较到位。

根据以上分析得到关键字的散列地址，可以得到散列表为

（2）由（1）中结果可以计算出查找成功和不成功时的平均查找长度，具体如下：

查找成功时的平均查找长度为：

ASL_成功=（1+1+1+1+3+3+2）/7=12/7

查找不成功时的平均查找长度为：

ASL_不成功=（3+2+1+2+1+5+4）/7=18/7

说明：此题与空位置的比较也要计算在内。这里可以做一个小的总结：当题目无特殊说明，在以顺序表为存储结构的情况下，如果空位置作为结束标记，则与空位置的比较次数也要计算在内；在以链表为存储结构的情况下，与空指针的比较次数不计算在内。

2.解析

（1）采用顺序存储结构，数据元素按其查找概率降序排列。

采用顺序查找方法。

查找成功时的平均查找长度=0.35×1+0.35×2+0.15×3+0.15×4=2.1。

（2）

答案一：

采用链式存储结构，数据元素按其查找概率降序排列，构成单链表。

采用顺序查找方法。

查找成功时的平均查找长度=0.35×1+0.35×2+0.15×3+0.15×4=2.1。

答案二：

采用二叉链表存储结构，构造二叉排序树，元素存储方式如图9-49所示。

图9-49 真题精选综合应用题第2题答案

a）二叉排序树1 b）二叉排序树2

采用二叉排序树的查找方法。

查找成功时的平均查找长度=0.15×1+0.35×2+0.35×2+0.15×3=2.0。

（1）、（2）的评分说明：

① 若考生以实际元素表示“降序排列”，同样给分。

② 若考生正确求出与其查找方法对应的查找成功时的平均查找长度，给2分；若计算过程正确，但结果错误，给1分。

③ 若考生给出其他更高效的查找方法且正确，可参照评分标准给分。