Relax1000 数据结构 · 第7章 查找 · 解析¶
第7章 查找¶
本章 65 题；解析册印刷页 52–65。
速对答案（原书）： A C D A B A C C C D C B B A A D A B B B C C C D B D D B C D A B B D C D D D C A B C C C A (CB) B A B C A C B A C B A C C D D C C A D
Q1¶
速对表原值： A
详细解析标注： A
采用顺序存储结构，数据元素按其查找概率降序排列可得到最小的查找成功查找长度。查找成功时的平均查找长度=0.35x1+0.35x2+0.15x3 +0.15x4=2.1
原页版面片段（用于核对图表、公式、矩阵或代码）
Q2¶
速对表原值： C
详细解析标注： C
当折半查找判定树是一棵满二叉树，那么失败平均查找长度等于树高，C 错误。在线性查找中，每轮只需要 1 次判断操作；而在二分查找中，需要 1 次加法、1 次除法、1 ～ 3 次判断操作、1 次加法（减法），共 4 ～ 6 个单元操作；因此，当数据量 n 较小时，线性查找反而比二分查找更快。
Q3¶
速对表原值： D
详细解析标注： D
在由n个元素组成的有序表上进行折半查找时，对任一个元素进行查找的长度都不会大于〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕 + 1。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q4¶
速对表原值： A
详细解析标注： A
450 比 200 大，说明后续查找走的是 200 的右边区间，该区间内的所有数都大于200，因此后续所有查找的关键字都应该比 200 大，但是 A 选项后续出现 180<200，不符合折半查找的规则，因此答案选 A。
Q5¶
速对表原值： B
详细解析标注： B
此二分查找判定树两种情况如下图所示：每个分支结点要么左右子树结点总数相等，要么左子树比右子树结点总数多一个每个分支结点要么左右子树结点总数相等，要么左子树比右子树结点总数少一个I 错误，没考虑左右子树结点总数相等的情况。II 正确，如上图所示。III 错误，IV 正确，此树是一棵 BST，也是一棵 AVL，但不一定是完全二叉树，因为最后一排叶子不一定连续排列。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q6¶
速对表原值： A
详细解析标注： A
一共 10 个元素，在选取 mid 元素时，可以取第 5 个（编号 1～10），也可以取第 6个，一旦确定左右谁多谁少的规则，后续都要满足这种规则。A选项中，第一次选20，即左边比右边少一个元素。58>20，应当继续查找右边区间。(30, 50, 70, 88, 100)中，mid 元素是 70，58<70，所以走左边。[30,50]，mid 元素取 30，58>30，走右边。(50)最后 58>50，到失败结点，查找失败。查找的元素依次是 20、70、30、50，A 正确。若是 B 选项，确定 30 为第一个 mid 元素，也就确定了划分时，左边比右边多一个的规则。58>30，走右边区间(50, 70, 88, 100)，继续遵循左边比右边多一个的规则，mid 元素应该是 88。58<88，走左边区间(50, 70)，mid 元素应该是 70，58<70，最后走(50)，所以查找依次是 30、88、70、50。
Q7¶
速对表原值： C
详细解析标注： C
511 = 29 − 1，所以折半查找判定树是一棵高度为 9 的满二叉树，所有的失败结点都在第 10 层，〔公式/符号见原页版面片段〕失败 =9∗512 512 = 9。A 选项是查找成功的平均查找长度，〔公式/符号见原页版面片段〕成功 =1∗1+2∗21+3∗22+...+9∗28 511 =4097 511（差比数列求和）
原页版面片段（用于核对图表、公式、矩阵或代码）
Q8¶
速对表原值： C
详细解析标注： C
有n个元素的有序顺序表，二分查找元素的次数上界为⌊〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕⌋ + 1 次，代入n=100即可得到答案为 7。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q9¶
速对表原值： C
详细解析标注： C
查找一次成功的节点数为 1，下标为 15（假设偶数个结点分两个区间时，左边比右边少一个）查找二次成功的节点数为 2，下标 7，23查找三次成功的节点数为 4，下标 3，11，19，27查找四次成功的节点数为 8，下标 1，5，9，13，17，21，25，29查找五次成功的节点数为 15，下标 2，4，6，8，10，12，14，16，18，20，22，24，26，28，30
Q10¶
速对表原值： D
详细解析标注： D
二叉查找树在最坏情况下是 O（n）。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q11¶
速对表原值： C
详细解析标注： C
每块长度为 8，则共有 152／8=19 块，即索引表项为 19，那么顺序查找索引表时的平均查找长度为（19+1）／2=10，而在一个块内的平均查找长度为（8+1）／2=4.5，因此综合上面两项为 C 答案。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q12¶
速对表原值： B
详细解析标注： B
分块查找是将数据分为若干块，不要求索引块内数据个数相等，且块内数据不必有序，块间有序，每块内最大(或最小)的数据组成索引块，故本题选 B。
Q13¶
速对表原值： B
详细解析标注： B
〔公式/符号见原页版面片段〕成功 = 〔公式/符号见原页版面片段〕二分查找查找成功 + 〔公式/符号见原页版面片段〕顺序查找查找成功 = ⌈ 1∗1+2∗21+3∗22+4∗23+5∗24 31 + 31+1 2 ⌉ = ⌈ 129 31 + 16⌉ = 21
原页版面片段（用于核对图表、公式、矩阵或代码）
Q14¶
速对表原值： A
详细解析标注： A
设块长为 b，索引表包含 n/b 项，索引表的 ASL=(n/b+1)/2，块内的ASL=(b+1)/2，〔公式/符号见原页版面片段〕总 = 〔公式/符号见原页版面片段〕索引表 + 〔公式/符号见原页版面片段〕块内 = 〔公式/符号见原页版面片段〕 + 〔公式/符号见原页版面片段〕/〔公式/符号见原页版面片段〕 + 2 /2，其中对于 b+ n/b，由均值不等式知b=n/b 时有最小值，此时。则最理想块长为 2500=50。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q15¶
速对表原值： A
详细解析标注： A
对于 A，因为二叉排序树的中序遍历序列一定是关键字的有序序列，所以可以将其先序遍历序列排序从而得到中序序列。而后由先序序列和中序序列来确定该二叉排序树。对于 B，一般意义上，二叉排序树优于顺序表的平均查找时间，但是若这组记录构造出的二又排序树恰巧是单枝状时，那么在其上的平均查找时间和顺序表是一样的，都是（n+1）/2，其中 n 是表中的结点数。对于 C，在二叉排序树上的一个结点被成功查找时，关键字比较次数就是它所在的层数，由于是等概率查找情况，要使所有结点总的比较次数最小，则平均查找长度也必为最佳，显然二叉排序树的树高最小可以满足要求。对于 D，在二叉排序树中，删除哪一个结点是可以按情况任意指定的，可以是根，可以是非叶结点，也可以是叶子结点；但是二叉排序树在插入结点时一定是发生在分支末端，即新添加一个叶子结点，所以删插结点前后的二叉排序树不能保证是一样的。另外，若给定一组记录，而给出的记录顺序不同，生成的二叉排序树也不一定相同，因为生成的过程是从空二叉排序树开始不断插入记录结点，其中的第一个记录生成根结点。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q16¶
速对表原值： D
详细解析标注： D
其余三个选项为
原页版面片段（用于核对图表、公式、矩阵或代码）
Q17¶
速对表原值： A
详细解析标注： A
只需依次判断后序结点是否全比当前结点大或者小，显然只有 A 符合。
Q18¶
速对表原值： B
详细解析标注： B
依次插入将带插入值直接放入二叉搜索树符合条件位置，使得整棵树左子树均比根小，右子树均比根大，查找 62 需要比较 3 次，分别是和 52、73、62 比较。
Q19¶
速对表原值： B
详细解析标注： B
不妨假设非空的高度为 h 的平衡二叉树的结点数至少为 f（h）。它是由 1 个根结点及其左右子树构成的，那么左右子树可以分别是树高为 h-1 和 h-2 的具有最少结点数的平衡二叉树。由递推公式 F(n)=F(n-1) + F(n-2) + 1;F(1) = 1, F(2) = 2，可递推 1, 2, 4, 7, 12, 20, 33, 54。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q20¶
速对表原值： B
详细解析标注： B
设 〔公式/符号见原页版面片段〕ℎ 表示高度为 h 的平衡二叉树中含有的最少结点数。由递推式〔公式/符号见原页版面片段〕ℎ = 〔公式/符号见原页版面片段〕ℎ−1 + 〔公式/符号见原页版面片段〕ℎ−2 + 1 可推：〔公式/符号见原页版面片段〕0 = 0, 〔公式/符号见原页版面片段〕1 = 1, 〔公式/符号见原页版面片段〕2 = 2, …, 〔公式/符号见原页版面片段〕3 = 4, 〔公式/符号见原页版面片段〕4 = 7, 〔公式/符号见原页版面片段〕5 = 12, 〔公式/符号见原页版面片段〕6 = 20 > 18所以 18 个结点的最大高度为 5，答案选 B。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q21¶
速对表原值： C
详细解析标注： C
设 〔公式/符号见原页版面片段〕ℎ 表示高度为 h 的平衡二叉树中含有的最少结点数。由递推式〔公式/符号见原页版面片段〕ℎ = 〔公式/符号见原页版面片段〕ℎ−1 + 〔公式/符号见原页版面片段〕ℎ−2 + 1 可推：〔公式/符号见原页版面片段〕0 = 0, 〔公式/符号见原页版面片段〕1 = 1, 〔公式/符号见原页版面片段〕2 = 2, …, 〔公式/符号见原页版面片段〕3 = 4, 〔公式/符号见原页版面片段〕4 = 7, 〔公式/符号见原页版面片段〕5 = 12, 〔公式/符号见原页版面片段〕6 = 20 > 15。（推导：套娃！）也就是说，高度为 6 的平衡二叉树最少有 20 个结点，因此 15 个结点的平衡二叉树的高度最大为 5，即叶子结点的最大高度为 5。最小叶子结点的层高为 3，因为高度为 5 的平衡二叉树，根据上述递归式〔公式/符号见原页版面片段〕ℎ = 〔公式/符号见原页版面片段〕ℎ−1 + 〔公式/符号见原页版面片段〕ℎ−2 + 1，根结点一侧树高为 4 的结点数最少平衡二叉树，一侧为树高为 3 的结点数最少平衡二叉树，高度为 3 的结点数最少平衡二叉树中，叶子结点最低为 2，所以在原来 h=5 的平衡二叉树中，叶子节点最低在第 3 层。所以叶子结点所在层高 h∈[3，5]，A、D 选项查找高度为 2，6，故错误。B 选项的查找过程不能构成二叉排序树，故错误。正确答案选 C。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q22¶
速对表原值： C
详细解析标注： C
插入结点导致不平衡，一定是某棵子树高度增加，导致比另外一边的子树高度相差 2，导致出现不平衡结点（平衡因子绝对值>1，即 2 或-2）。接下来应该判断是 2 还是-2，经过以上分析，插入之后势必所在子树的平衡因子要么是1，要么是-1（如果插入后平衡因子还是0，高度一定不会增加）。满足条件的是右孩子，所以插入元素的位置一定是右孩子的左子树。所以应该进行RL 调整。
Q23¶
速对表原值： C
详细解析标注： C
每个分支结点平衡因子为1（或全为-1）时，高度最大，此时 h 层所需最少结点数应按递推式 H(n) = H(n - 1) + H(n - 2) + 1 计算，各层的最少结点数分别为 1, 2, 4, 7 , 12, 20…，所以在这种情况下，12 个结点刚好在第 5 层，即 AVL 的最大高度为 5。树中，由度数+1=结点总数可以推出，2〔公式/符号见原页版面片段〕2 + 〔公式/符号见原页版面片段〕1 + 1 = 〔公式/符号见原页版面片段〕2 + 〔公式/符号见原页版面片段〕1 + 〔公式/符号见原页版面片段〕0，即〔公式/符号见原页版面片段〕2 + 1 = 〔公式/符号见原页版面片段〕0 → 2〔公式/符号见原页版面片段〕0 − 1 + 〔公式/符号见原页版面片段〕1 = 12，完全二叉树满足度为 1 的结点数最少，此时度为 1 的结点数为 1，得叶子结点数为 6，选 C。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q24¶
速对表原值： D
详细解析标注： D
按高度依次来分析不同平衡二叉树的情况：h=1，只有一个根节点，所以只有 1 种情况。h=2，一共 3 种情况，
①根节点+左孩子
②根节点+右孩子
③根节点+左右孩子h=3，根节点的左右子树高度之差不超过1，有三种情况：
①左子树h=2，右子树h=1，此时左子树h=2 的平衡二叉树有 3 种，h=1 只有一种，所以是 3*1=3；
②左子树 h=1，右子树 h=2，同样也是 1*3=3种；
③左子树 h=2，右子树 h=2，一共是 3*3=9 种；综合以上分析，h=3 的平衡二叉树的形态有3+3+9=15 种。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q25¶
速对表原值： B
详细解析标注： B
首先根据高度为h的平衡二叉树最少结点数公式：〔公式/符号见原页版面片段〕ℎ = 〔公式/符号见原页版面片段〕ℎ−1 + 〔公式/符号见原页版面片段〕ℎ−2 + 1，可以得到〔公式/符号见原页版面片段〕1 = 1, 〔公式/符号见原页版面片段〕2 = 2, 〔公式/符号见原页版面片段〕3 = 4, 〔公式/符号见原页版面片段〕4 = 7；所以 5 个结点的平衡二叉树高度最大为 3。而高度为 2 的满二叉树最多可容纳 3 个结点，所以 5 个结点的平衡二叉树高度一定是 3，且第二层是排满的 2 个结点，否则不平衡，第三层也就剩下 5-3=2 个结点。即从第三层的 4 个结点任意选出 2 个，都满足平衡二叉树，答案为〔公式/符号见原页版面片段〕4 2 = 6 种。在考场，第一时间也可以枚举，枚举的过程应该顺着上面的思路来确定情况。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q26¶
速对表原值： D
详细解析标注： D
插入过程如下图所示，平衡因子为 0 的分支结点个数为 3 个。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q27¶
速对表原值： D
详细解析标注： D
看看进行操作前是否符合 AVL。I、IV 正确，显然删除 2 和插入 5 之前是符合 AVL 树的。II 错误，BST 的 insert 操作一定是在叶子结点，不可能插入到根结点。III 正确，删除 4 的原树如右图所示，BST 删除后用前驱 3 作为新的根节点。V 错误，插入 8 之前不符合 AVL。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q28¶
速对表原值： B
详细解析标注： B
A 选项，若删除的是分支结点，则再插入后，二叉树一定改变。例子如下图：B 选项正确，插入的结点一定在叶子结点，再删除恢复到原状。C、D 选项错误，调整后可能会导致变化，也可能不变；C 选项不变化的图例：（同样，在第二步只有 1，3 结点的情况中，插入 2，再删除 2，D 选项可能无变化）C 选项变化的图例：删除 20，再插入 20，发生改变。D 选项发生变化的图例：
原页版面片段（用于核对图表、公式、矩阵或代码）
Q29¶
速对表原值： C
详细解析标注： C
I 错误，子树结点若是红色，则不符合红黑树根结点为黑色的要求。II 正确，最多的情况是黑色和红色交替出现的满二叉树。III 错误，比如三个结点，根为黑色，两个孩子为红色的树就是反例。IV 正确，任何一个结点的黑高确定，则两种极端是都是黑色和黑红交替，长的一侧不会超过短的一侧的两倍。V 正确，对比如下图所示。最坏时间复杂度 BST AVL 树 红黑树Search(查) 〔公式/符号见原页版面片段〕(〔公式/符号见原页版面片段〕) 〔公式/符号见原页版面片段〕(〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕) 〔公式/符号见原页版面片段〕(〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕) Insert（插） 〔公式/符号见原页版面片段〕(〔公式/符号见原页版面片段〕) 〔公式/符号见原页版面片段〕(〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕) 〔公式/符号见原页版面片段〕(〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕) Delete（删） 〔公式/符号见原页版面片段〕(〔公式/符号见原页版面片段〕) 〔公式/符号见原页版面片段〕(〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕) 〔公式/符号见原页版面片段〕(〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕)
原页版面片段（用于核对图表、公式、矩阵或代码）
Q30¶
速对表原值： D
详细解析标注： D
I 和Ⅱ都是红黑树的性质。AVL 是高度平衡的二叉查找树，红黑树是适度平衡的二叉查找树，从这一点也可以看出 AVL 的查询效率往往更优，III 错误。AVL 的某结点的左右孩子的平衡因子都是 0，并不能说明左右子树的高度相等，因此该结点的平衡因子不一定为零，IV 错误。
Q31¶
速对表原值： A
详细解析标注： A
红黑树是一种特殊的二叉排序树，选项 B 不满足二叉排序树的性质。选项 C 中，结点 2 的左右黑结点数不同。在选项 D 中，结点 3 的左右黑结点数不同。只有选项 A 满足红黑树的定义。
Q32¶
速对表原值： B
详细解析标注： B
插入结点 2 旦将其染成红色后违反不红红原则，并且叔结点是黑色，应进行 L 旋转，将结点 3 右旋旋转到结点 5 的位置，结点 2 和结点 5 分别成为结点 3 的左、右孩子，然后将结点 3染成黑色，结点 2 和结点 5 染成红色。因此，下一步应进行右旋操作。
Q33¶
速对表原值： B
详细解析标注： B
最后的红黑树的形态如下图所示，
注意：黑高是指除了自身之外到叶子结点（失败结点）的黑色结点数，B 正确。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q34¶
速对表原值： D
详细解析标注： D
关键字 5, 4.3.2, 1 依次插入红黑树后的形态变化如下：
原页版面片段（用于核对图表、公式、矩阵或代码）
Q35¶
速对表原值： C
详细解析标注： C
AVL 的删除步骤如下：
-
用 BST 的删除结点方法删除 当待删除节点的度为 0 时，表示待删除节点是叶节点，可以直接删除。 当待删除节点的度为 1 即只有左子树或右子树时，将待删除节点替换为其子节点即可。 当待删除节点的度为 2 即左右子树都存在时，我们无法直接删除它，而需要使用一个节点替换该节点。由于要保持二叉搜索树“左 < 根 < 右”的性质，因此这个节点可以是右子树的最小节点（在右子树的最左下位置）或左子树的最大节点(左子树的最右下位置)。最终转换成对叶子节点的删除。
-
从删除结点一直往上回溯，寻找第一个失衡结点，找不到说明此时 AVL 还是平衡的，到这里就结束了；否则标记它为 node，其高度最高的儿子结点为 child，高度最高的孙子结点为grandchild；(只有调整长得高的那部分子树才能重新恢复平衡)
-
对以 node 的最小不平衡子树进行调整，先观察 node、child 哪一种；然后执行相应的旋转操作，将以 node 为根的子树调整平衡；grandchild 的关系，判断是执行(LL/RR/LR/RL)中的
-
如果调整后由于子树高度-1 导致不平衡向上传导，则从第 2 步继续执行调整操作，直至该树平衡；本题的删除过程如下，进行 RL 调整。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q36¶
速对表原值： D
详细解析标注： D
删除的规则如下：
-
若删除的是非终端结点，则找到其前驱/后继关键字补到当前结点中，最终转换成删除终端结点
-
删除终端节点，自底向上找到第一个失衡的结点，接着看这个失衡结点的子树中，到所有叶子节点路径最长的那一条，确定这个路径的前两个结点是LL、RR、LR、RL中的哪一种。比如这一题，删除 32 后，第一个失衡的结点时 44。44 子树中到叶子结点的最长路径经过的孩子孙子是 78（R），60（L），所以是 RL 调整，旋转两次。
-
第一次调整完后，继续往上找失衡的结点，进行调整，直到全部平衡。可以发现第二次失衡的是根结点 33，进行 LR 调整，旋转两次。综上所述，两次调整 RL 和 LR，旋转次数是 4 次。判断出 44 是失衡的结点，找到距离 44 最远的叶子结点(48/62)，可以确定是 RL 调整，先右旋再左旋：调整完后，继续往上进行观察，31 失去平衡，找到最远的叶子节点是 21，确定是 LR 调整：
原页版面片段（用于核对图表、公式、矩阵或代码）
Q37¶
速对表原值： D
详细解析标注： D
A 正确，当关键字最多的情况时，B 树是满 m 叉树，每个结点都有 m - 1 个关键字。
C 正确，除根结点外所有非失败结点至少 ⌈〔公式/符号见原页版面片段〕/2⌉ − 1 个关键字，根结点至少有 1 个关键字。
D 错误，和二叉搜索树不同，二叉搜索树高度的增加发生在底部，而 B 树的高度增加发生在顶部，只有根节点分裂才会导致高度加 1。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q38¶
速对表原值： D
详细解析标注： D
AVL 和二叉查找树很类似，从根结点到叶子结点不一定有序，红黑树是一种二叉查找树，同理该路径不一定有序；堆符合这样的定义，应选 D。
Q39¶
速对表原值： C
详细解析标注： C
本题考查 B 树的高度，磁盘存取次数取决于 B 树的高度。对有 n 个关键字的 m阶 B 树，让每个结点中的关键字个数达到最少，则容纳同样多关键字的 B 树的高度达到最大。也就是说，第一层至少有 1 个结点；第二层至少有 2 个结点；除根结点外的每个非终端结点至少有⌈〔公式/符号见原页版面片段〕/2⌉ 棵子树，则第三层至少有 2⌈〔公式/符号见原页版面片段〕/2⌉个结点.……第 h+1 层至少有2 ⌈〔公式/符号见原页版面片段〕/2 ⌉)ℎ−1个结点，注意，第 h+1 层是不包含任何信息的叶结点。对关键字个数为 n 的 B 树，叶结点即查找不成功的结点为 n+1，由此有 n + 1⩾2(⌈〔公式/符号见原页版面片段〕/2⌉)ℎ−1 ,⩽log⌈〔公式/符号见原页版面片段〕/2⌉ ((〔公式/符号见原页版面片段〕 + 1)/2) + 1 。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q40¶
速对表原值： A
详细解析标注： A
II 错误，B+ 树支持顺序查找，因为它的叶结点通过指针串联起来，而 B 树没有。III 错误，(B+) 树每次都需查询到叶结点，B 树查找到元素即可，不一定需要查找到叶结点处。
Q41¶
速对表原值： B
详细解析标注： B
插入规则：
-
找到当前关键字的底层结点插入位置
-
判断插入后是否超过单个结点的关键字上限（阶数-1） 不超过，插入成功，结束。 超过了则进行分裂，取中间结点放入父亲结点，若父亲结点关键字也溢出，则继续分裂。若到根节点还溢出，则生成新的根节点，B 树高度+1。本题插入过程如下图所示：
原页版面片段（用于核对图表、公式、矩阵或代码）
Q42¶
速对表原值： C
详细解析标注： C
首先删除非终端结点关键字要通过前驱或者后继替换直到转化为对终端结点关键字的删除，这里选前驱 20 代替（也可以选后继 40 替代，结果相同），接着终端结点删除关键字后为空，要跟兄弟结点借，兄弟只有关键字 40 不够借，所以合并（见中间图）。合并后父亲结点关键字要放下去一个，导致父亲结点关键字低于关键字下限 1 且他自己的兄弟只有 56 也不够借，继续合并，得到最右边的图，即最终结果。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q43¶
速对表原值： C
详细解析标注： C
5 阶 B 树，关键字的范围为[2, 4]，B 树删除的规则：
-
若删除的是分支结点，则找到分支结点关键词的前驱或者后继关键词，转换成对终端节点的删除。
-
删除终端结点的关键字 若删除后结点关键字没有下溢（不少于最小关键词个数），则直接结束。 若删除后下溢，则需要向兄弟结点借，左右兄弟皆可。 兄弟借了后没有下溢（兄弟够借），则直接借，兄弟借出的关键字放到父结点，父结点中的下放到删除关键字的位置。 兄弟借了后下溢（兄弟不够借），则和兄弟合并，合并需要把父节点中的关键字和本身、兄弟的关键字合并到一个结点。若合并后，父亲结点也下溢，则继续找父亲结点的兄弟借，按上述步骤套娃，直到满足条件，或者直到根节点也被合并（B 树高度-1）。具体的删除过程如下图所示。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q44¶
速对表原值： C
详细解析标注： C
A 错误，根节点的范围下限是 2。
B 错误，B+树中删除仅在叶子结点进行，非叶子结点的关键字不删除，作为后续查找的“分解关键字”，所以非叶子结点关键字个数总和和叶子节点关键字总和不一定相等。
C正确，B+树叶子结点之间通过指针链接成一个链表，且所有关键字均出现在叶子节点，所以支持顺序查找。而且更适合査找某个范围内的所有关键字。例如，在 B+树上找出值在[a, b]内的所有关键字。处理方法如下：通过一次查找找出关键字 a，不管它是否存在，都可以到达可能出现 a 的叶子节点，然后在叶子节点中查找值等于 a（如果有）或大于 a 的那些关键字，对于所找到的每个关键字都有一个指针指向相应的记录，这些记录的关键字在所需要的范围。如果在当前节点中没有发现大于 b 的关键字，就可以使用当前叶子节点的指向下一个结点的指针找到下一个叶子结点，并继续进行同样的处理，直至在某个叶子节点中找到大于 b 的关键字，才停止查找。
D错误，B+树一定要查找到最后一层，因为中间结点不保存关键字代表记录的指针，只有叶子结点才有。
Q45¶
速对表原值： A
详细解析标注： A
B+树能够有效地支持顺序查找，因为它的叶子结点之间具有指针链接，可以顺序访问所有关键字。然而，B 树不能像 B+树那样高效地支持顺序査找，因为关键字分布在整个树中，没有指针链接叶子结点，因此 A 选项错误。在 B 树中进行随机查找时，从根结点开始，根据查找的关键字，按照结点中关键字的大小关系，选择合适的子结点进行查找，直到找到对应的关键字或者查找失败。B+树在随机查找时的过程与 B 树类似，从根结点开始，根据关键字的大小关系选择合适的子结点进行查找，直到找到对应的叶子结点。由于叶子结点形成了有序链表，可以更快地进行范围查询和顺序遍历操作。B 树和 B+树都能有效地支持随机查找。由于它们都是平衡的多叉树，它们的查找性能在最坏情况下为 O(logn)，因此 B 选项正确。B 树和 B+树都是平衡的多叉树，它们在插入和删除操作时会自动调整树的结构，确保树保持平衡，因此 C 选项正确。B 树和 B+树都可以用作文件索引结构，它们可以有效地支持随机査找和范围查询，因此在数据库和文件系统中经常被用作索引结构，因此 D 选项正确。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q46¶
速对表原值： (CB)
详细解析标注： C，B
5 阶 B 树中共有 53 个关键字，由最大高度公式 〔公式/符号见原页版面片段〕⩽log⌈〔公式/符号见原页版面片段〕/2⌉ 〔公式/符号见原页版面片段〕+1 2 + 1 = 4 得最大高度 4；由最小高度公式 ℎ⩾log〔公式/符号见原页版面片段〕 + 1 ≈ 2.5 得最小高度从而最小高度为 3。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q47¶
速对表原值： B
详细解析标注： B
搜索第 2025 个关键字并不代表只有 2025 个关键字，所以需要每层放尽可能少的关键字，第一层 1，第二层 2 * 3，第三层 2 * 4 * 3，第四层 2 * 4^2 * 3，第五层 2 * 4^3 * 3，...，以此累加，到第 5 层最少需要 511 个关键字，到第 6 层最少需要 2047 个关键字，因此第 2025 个关键字最高在第 6 层，根节点在内存，所以最多启动 5 次，答案选 B。提问：若问 7 阶 B 树只有 2025 个关键字，根节点已经读入内存，读取任意关键字至多需要多少次I/O？A。【解析】跟原题不同的是，本题确定了总的结点数，那么 2025 个关键字 B 树最高层高，根据B 树树高 h 的计算公式：log〔公式/符号见原页版面片段〕 + 1 ⩽ℎ⩽log⌈〔公式/符号见原页版面片段〕/2⌉ 〔公式/符号见原页版面片段〕+1 2 + 1，计算得 h=5(取整数)，因为 B 树的根结点已读入内存，所以最多需再启动 4 次磁盘 I/O。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q48¶
速对表原值： A
详细解析标注： A
n 个关键字的 B 树必有 n+1 个叶⼦结点（n 个关键字将数域切分为 n+1 个区间），注意最多是迷惑条件。
审计旁注（非原文）：改标号
选项区原文出现“B．C．”重叠标号；依后续解析，四项应按 A、B、C、D 理解，答案 A。
Q49¶
速对表原值： B
详细解析标注： B
在除留余数法中，p 应取小于存储区容量的质数，因此答案为 B。为什么要选质数作为模长？比如，若 p = 12，键值为 24, 36, 48 都会被映射到相同的桶（0），因为它们都被 12 整除。如果用质数作为模数，例如 11，这些值会均匀地落在不同位置。为什么模长要小于或等于 m？散列表的长度 m 是桶的数量，最终散列值必须映射到 [0, m-1] 之间：
-
如果你用 p > m，那么得到的哈希值还需要再次取模 m，多此一举。
-
如果你直接用 p ≤ m 的最大质数作为模长，就能直接映射到有效位置，效率更高。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q50¶
速对表原值： C
详细解析标注： C
同义词指的是在关键字不同，通过哈希函数映射到同一个值。而线性探测法处理冲突时，会把冲突的关键字按顺序往后放到空闲位置，可能导致不同同义词交叉排放，所以查找路径上的关键字可能是同义词。举例，比如哈希函数取 key %7，依次插入 1，9，8 三个元素，8 放在下标为 3 的位置，查找 8 时，路径上依次是 1，9，8。只有 1，8(% 7 = 1)是同义词，9 不是同义词。因此答案选 C。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q51¶
速对表原值： A
详细解析标注： A
对于 A，不存在特别好与坏的哈希函数，哈希函数计算不能过于复杂，同时还要兼顾减少冲突，因此选取怎样的哈希函数和哈希表中的记录关键字的特点相关。对于 B，聚集现象是非同义词发生的地址冲突，在链地址法的哈希表中，只有同义词才会发生地址冲突。对于 C，理想状态哈希表的查找应该不需要关键字之间的比较，而是由关键字通过哈希函数定址即可，但是由于冲突的不可避免性，在查找中也就需要通过比较来甄别冲突的情况。对于 D，a<1 只能说明哈希表的长度大于存储的记录个数，但存储的记录完全有可能发生冲突，冲突与否取决于两个关键字经过哈希函数运算后的值（即哈希地址），是否相同。
Q52¶
速对表原值： C
详细解析标注： C
表中记录个数为 n=5 时，装填因子为 a=0.33，则哈希表长为〔公式/符号见原页版面片段〕 = 〔公式/符号见原页版面片段〕／〔公式/符号见原页版面片段〕 = 5/0.33 ≈ 15，在放入关键字为49的记录之前哈希表HT［0..14］，发生冲突，然后按照〔公式/符号见原页版面片段〕 + 12, 〔公式/符号见原页版面片段〕 − 12, 〔公式/符号见原页版面片段〕 + 22, 〔公式/符号见原页版面片段〕 − 22...进行探查。关键字 49 的哈希地址为 49 MOD 11=5，第一次探测与 60 冲突。根据二次探测再散列的方法，第 2 次探测地址为 5 + 12 = 6，又与 83 冲突；第 3 次探测地址为 5－12 = 4，又与 37 冲突；第 4 次探测地址为 5 + 22 = 9，没有冲突发生，因此它的存放位置是 9。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q53¶
速对表原值： B
详细解析标注： B
依次取余后序列为{2, 8, 0, 8, 8, 10, 8, 6, 10, 5, 2, 1}，H（key）=0 ～ 10，查找失败对应的地址有 11 个，每次查找对应链的时候，查到空结点为止，故 0～10 的查找失败次数和为2+2+3+1+1+2+2+1+5+1+3=23，故答案选 B。
注意：有的书上空指针不算一次比较，这个也是合理的，应当在算/不算都计算一遍结果，如果发现有答案和自己结果对上，就果断选，一般的题目答案中不会同时包含两种方式的结果的。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q54¶
速对表原值： A
详细解析标注： A
34%7=6，69%7=6，9%7=2，56%7=0，24%7=3，44%7=2。初始如下：删除 24，再插入 51（%7=2），发生冲突后，插入下标为 3 的位置。〔公式/符号见原页版面片段〕失败 =2+1+4+3+2+1+3 7 =16 7
原页版面片段（用于核对图表、公式、矩阵或代码）
Q55¶
速对表原值： C
详细解析标注： C
再散列在处理冲突时依然会产生“堆积”现象，A 错误。在哈希表中进行查找依然需要进行关键字比较，B 错误。采用线性探测法处理冲突时，所有同义词在散列表中不一定相邻，D错误。
Q56¶
速对表原值： B
详细解析标注： B
拉链法的节点空间动态申请更适合无法确定表长的情况。
Q57¶
速对表原值： A
详细解析标注： A
A 错误，链地址法处理冲突，需要遍历链表，查找的时间不一定相同。
Q58¶
速对表原值： C
详细解析标注： C
线性探测是解决冲突的策略。第一个关键字最好情况是没有发生冲突，至少探测0 次，第 2 个关键字至少要探测 1 次，第 3 个关键字至少要探测 2 次，第 4 个关键字至少要探测 3次，……，第 k 个关键字至少要探测 k-1 次，至少共需进行 k(k - 1) / 2 次探测。
Q59¶
速对表原值： C
详细解析标注： C
顺序查找和折半查找都不适合动态变化。哈希查找插入的时间复杂度取决于冲突处理函数，最坏是 O(n)。分块查找的优点是：在表中插入和删除数据元素时，只要找到该元素对应的块，就可以在该块内进行插入和删除运算。由于块内是无序的，故插入和删除比较容易，无须进行大量移动。如果线性表既经常动态变化，又需对其进行快速查找，则可采用分块查找。其缺点是：要增加一个索引表的存储空间并对初始索引表进行排序运算。因此此题选 C。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q60¶
速对表原值： D
详细解析标注： D
散列函数和处理冲突的方法决定了值的映射地址和进行冲突探测后插入的位置，散列函数的好坏首先影响出现冲突的频繁程度，若是均匀的散列函数（对同一组随机的关键字，产生冲突的可能性相同），则平均查找长度只有处理冲突的方法和装填因子。装填因子〔公式/符号见原页版面片段〕 =表中填入的记录数散列表的长度，〔公式/符号见原页版面片段〕越小，发生冲突的可能性就越小；反之越大。所以答案选 D。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q61¶
速对表原值： D
详细解析标注： D
h 层的平衡二叉树，所需最少结点个数满足递推式 〔公式/符号见原页版面片段〕ℎ = 〔公式/符号见原页版面片段〕ℎ−1 + 〔公式/符号见原页版面片段〕ℎ−2 +1，〔公式/符号见原页版面片段〕1 = 1,〔公式/符号见原页版面片段〕2 = 2 计算得 〔公式/符号见原页版面片段〕5 = 12，I 正确；II 正确，h=5 时，要使得左右子树结点数相差最大，那么左子树高度 h=4，右子树高度 h=3，进一步拉开差距，左子树是 h=4 的满二叉树，共 15 个结点；而右子树是 h=3 的结点数最少的平衡二叉树，用 A 选项的递推式可知，h=3 时，至少需要 4 个结点。所以结点数之差最大为 11。III 正确，所有分支结点平衡因子为 1，即满足 h=5 的结点数最少的平衡二叉树形状，整体左倾，可知左子树是高度为 4 的结点数最少的平衡二叉树形状，根据递推式，结点数为 7。IV 正确，归纳法可知，h=1 或 2，层高差为 0；每增加 2 层，叶子节点层高差距+1，即 〔公式/符号见原页版面片段〕 = ⌊ ℎ−1 2 ⌋。h=5 代入得 2。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q62¶
速对表原值： C
详细解析标注： C
首先从高度为 1 的开始逐层归纳。高度为 1 的 AVL 只有 1 种树形也就一个根结点。高度为 2 的 AVL 有 3 种不同的树形，分别是根结点有左孩子无右孩子、有右孩子无左孩子、左右孩子都有。高度为3的AVL有15种，第一种情况是左子树高度为2（3种），右子树高度为1（1种），一共有 31=3 种，第二种情况左子树高度为 1 右子树高度为 2，一共有 13=3 种，第三种情况左右子树高度都为 2，一共有 3*3=9 种，共计 3+3+9=15 种。 高度为 4 时，一样的思路。
①左子树高度为 3 右子树高度为 2，共 15*3=45 种
②左子树高度为 2 右子树高度为 3，共 3*15=45 种
③左、右子树高度均为 3，共 15*15=225 种，一共 315 种。答案选 C。 本题出成 h=4 是让大家不想去用枚举法做题，而是用归纳的思想去总结规律。一般来说考试考 h=3 的概率比较大，一方面可以枚举暴力解题，另一方面也是本题思路，具有区分度。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q63¶
速对表原值： C
详细解析标注： C
高度为 h 的平衡二叉树所需最少结点满足递推式 〔公式/符号见原页版面片段〕ℎ = 〔公式/符号见原页版面片段〕ℎ−1 + 〔公式/符号见原页版面片段〕ℎ−2 + 1，其中〔公式/符号见原页版面片段〕1 = 1,〔公式/符号见原页版面片段〕2 = 2，递推得到 〔公式/符号见原页版面片段〕4 = 7,〔公式/符号见原页版面片段〕5 = 12，当结点数为 10 时，高度最大可达 4。由因为题目说任意一棵 10 个结点的平衡二叉树，那么假设根结点存在顺序表的第 1 个单元，第 4 层上的结点最大可在第 15的单元处，因此要满足任意性，至少需要 15 个存储单元。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q64¶
速对表原值： A
详细解析标注： A
4阶B树所有结点关键字范围[1,3]。
①根结点关键字为1个：第二层有两个结点，要想到达第三层，那么第三层至少 4 个结点，一共 7 个结点，每个结点刚好 1 个关键字，此时第二层只有 2 个关键字，不符合题目要求第二层关键字不小于 3 个。所以最高只有 2 层，且根结点只有 1 个关键字的情况下，第二层每个结点一定都是 3 个关键字。
②根结点关键字为 2 个：第二层有三个结点，还剩 5 个关键字，那么三个结点的关键字可能是 311 的组合，也可能是 221 的组合，311 组合有三种情况即 311、131、113，同理 221 也有三种情况，一共 3+3=6 种。
③根结点关键字为 3 个：第二层有 4 个结点，还剩 4 个关键字，刚好每个结点 1 个关键字，只有 1 种可能。综上所述，一共有 1+6+1=8 种，答案选 A。
原页版面片段（用于核对图表、公式、矩阵或代码）
Q65¶
速对表原值： D
详细解析标注： D
I 错误，插入一个新关键字，可能导致结点分裂，但不一定会使树高加 1，只有传递到根结点分裂，高度才会加 1，即生成一个新的根结点。II 正确，删除一个关键字导致结点合并不一定使树高减 1，只有合并操作传递到根节点，导致根节点和左右孩子也合并，才会使树高减 1。III 错误，合并会向上传递，最坏的情况下，每层合并后减少一个孩子，第二层上合并的时候，根节点和左右孩子也合并，导致减少 2 个，所以一共 h-1 次合并，最多减少 h 个结点。IV 正确，每次分裂会把一个结点分裂成两个新结点，每个新结点（关键字发生改变）都要写回磁盘，所以一次分裂写 2 次磁盘。分裂会向上传递，如果一直传递到根结点，根结点分裂，不光自身会一分为二，还会产生一个新的根结点，所以最后一次分裂会发生 3 次写磁盘操作，那么 h 层，最多有 2h+1 次写磁盘操作。综上所述，II、IV正确，答案选 D。