253 KiB
查找习题
线性表查找
顺序查找
例题 由$n$个数据元素组成的两个表：一个递增有序，一个无序。采用顺序查找算法，对有序表从头开始查找，发现当前元素已不小于待查元素时，停止查找，确定查找不成功，已知查找任一元素的概率是相同的，则在两种表中成功查找()。
$A.$平均时间后者小
$B.$平均时间两者相同
$C.$平均时间前者小
$D.$无法确定
解：$B$。对于顺序查找，不管线性表是有序的还是无序的，成功查找第一个元素的比较次数为$1$，成功查找第二个元素的比较次数为$2$，以此类推，即每个元素查找成功的比较次数只与其位置有关（与是否有序无关），因此查找成功的平均时间两者相同。
折半查找
比较次数
例题 已知一个有序表$(13,18,24,35,47,50,62,83,90,115,134)$，当二分查找值为$90$的元素时，查找成功的比较次数为()。
A.1
B.2
C.4
D.6
解：$B$。开始时$low$指向$13$，$high$指向$134$，$mid$指向$50$，比较第一次$90>50$，所以将$low$指向$62$，$high$指向$134$，$mid$指向$90$，第二次比较找到$90$。
最多比较次数
计算查找次数，特别是最多查找次数，就找二叉树的层数，对总数以2取对数向上取整，即为最多查找次数。
平均查找长度
例题 具有$12$个关键字的有序表中，对每个关键字的查找概率相同，折半查找算法查找成功的平均查找长度为()，折半查找查找失败的平均查找长度为()。
A.37/12
B.35/12
C.39/13
D.49/13
解：$A,D$。假设有序表中元素为$A[0\cdots11]$，不难画出对它进行折半查找的判定树，如下图所示（向下取整），圆圈是查找成功结点，方形是虚构的查找失败结点。查找成功$ASL$=($\sum\limits_{i=1}^n$第$i$层的成功结点数\times i)$\div$成功结点总数，查找失败$ASL$=($\sum\limits_{i=1}^n$第$i$层的失败结点数\times i)$\div$失败结点总数。从而可以求出查找成功的$ASL=(1+2\times2+3\times4+4\times5)\div12=37/12$，查找失败的$ASL=(3\times3+4\times10)\div13$。
二叉查找
二叉排序树
平衡二叉树
例题 在任意一棵非空平衡二叉树（$AVL$树）$T_1$中，删除某结点$v$之后形成平衡二叉树$T_2$，再将$v$插入$T_2$，形成平衡二叉树$T_2$。下列关于$T_1$与$T_3$的叙述中，正确的是()。
Ⅰ.若$v$是$T$的叶结点，则$T_1$与$T_3$可能不相同
Ⅱ.若$v$不是$T$的叶结点，则$T_1$与$T_3$一定不相同
Ⅲ.若$v$不是$T$的叶结点，则$T_1$与$T_3$一定相同
$A.$仅Ⅰ
$B.$仅Ⅱ
$C.$仅Ⅰ、Ⅱ
$D.$仅Ⅰ、Ⅲ
解：$A$。在非空平衡二叉树中插入结点，在失去平衡调整前，一定插入在叶结点的位置。若删除的是$T_1$的叶结点，则删除后平衡二叉树不会失去平衡，即不会发生调整，再插入此结点得到的二叉平衡树$T_1$与$T_3$相同。若删除后平衡二叉树失去平衡而发生调整，再插入结点得到的二叉平衡树$T_1$与$T_3$可能不同，如一个平衡树的一个子树只有一个结点，删除这个结点则平衡树必然失衡，肯定会重新调整。Ⅰ正确。若$v$不是$T$的叶结点，则删除可能相同也可能不同。一般而言删除一个结点，然后重新加入是从叶子结点处加入，所以肯定不是在原来的根位置。但是如果删除会失衡，则会调整，所以可能会调整回原来的位置。
深度
例题 含有$20$个结点的平衡二叉树的最大深度为()。
A.4
B.5
C.6
D.7
解：$C$。平衡二叉树结点数的递推公式为$n_0=0$，$n_1=1$，$n_2=2$，$n_h=1+n_{h-1}+n_{h-2}$（$h$为平衡二叉树高度，$n$为构造此高度的平衡二叉树所需的最少结点数）。通过递推公式可得，构造$5$层平衡二叉树至少需$12$个结点，构造$6$层至少需要$20$个结点。
平衡因子
例题 若将关键字$1,2,3,4,5,6,7$依次插入初始为空的平衡二叉树$T$，则$T$中平衡因子为$0$的分支结点的个数是()。
A.0
B.1
C.2
D.3
解：$D$。平衡因子为$0$的分支结点即树两边同样高度。根据平衡二叉树的构造过程可得这个平衡二叉树是满二叉树，结点为$2,4,6$。
红黑树
树表查找
B树
B树操作
例题 已知一棵$3$阶$B$树，如下图所示。删除关键字$78$得到一棵新$B$树，其最右叶结点中的关键字是()。
A.60
B.60,62
C.62,65
D.65
解：$D$。对于图中所示的$3$阶$B$树，被删关键字$78$所在的结点在删除前的关键字个数$=\lceil\dfrac{3}{2}\rceil-1=1$，且其左兄弟结点的关键字个数$=2>\lceil\dfrac{3}{2}\rceil$，属于“兄弟够借”的情况，因此要把该结点的左兄弟结点中的最大关键字$62$上移到双亲结点中，同时把双亲结点中大于上移关键字的关键字$65$下移到要删除关键字的结点中，这样就达到了新的平衡。
例题 依次将关键字$5,6,9,13,8,2,12,15$插入初始为空的$4$阶$B$树后，根结点中包含的关键字是().
A.8
B.6,9
C.8,13
D.9,12
解：$B$。由于是$4$阶，所以关键字最少为$1$最多为$3$：
B树结点数
例题 具有$n$个关键字的$m$阶$B$树，应有()个叶结点。
A.n+1
B.n-1
C.mn
D.nm/2
解：$A$。$B$树的叶结点对应查找失败的情况，对有$n$个关键字的查找集合进行查找，失败可能性有$n+1$种。
例题 高度为$5$的$3$阶$B$树至少有()个结点，至多有()个结点。
A.32
B.31
C.120
D.121
解：$B,D$。由$m$阶$B$树的性质可知，根结点至少有$2$棵子树；根结点外的所有非终端结点至少有$\lceil\dfrac{m}{2}\rceil$棵子树，结点数最少时，$3$阶$B$树形状至少类似于一棵满二叉树，即高度为$5$的$B$树至少有$25- 1=31$个结点。由于每个结点最多有$m$棵子树，所以当结点数最多时，$3$阶$B$树形状类似于满三叉树，结点数为$(3^5-1)\div2=121$（注意，这里求的是结点数而非关键字数，若求的是关键字数，则还应把每个结点中关键字数的上下界确定出来）。
散列表查找
映射冲突
例题 采用开放定址法解决冲突的散列查找中，发生聚集的原因主要是()。
$A.$数据元素过多
$B.$负载因子过大
$C.$散列函数选择不当
$D.$解决冲突的方法选择不当
解：$D$。聚集是因选取不当的处理冲突的方法，而导致不同关键字的元素对同一散列地址进行争夺的现象。用线性再探测法时，容易引发聚集现象。
ASL
对于成功的长度往往是比较固定的，分子为关键字比较成功次数之和，分母为关键字数量。
对于失败的长度需要注意。分母为$MOD$的值，因为取余操作时只能取到$[0,MOD-1]$的范围，即使表长$L$再大也不可能映射到其他位置。
例题 现有长度为$11$且初始为空的散列表$HT$，散列函数是$H(key)=key%7$，采用线性探查（线性探测再散列）法解决冲突。将关键字序列$87,40,30,6,11,22,98,20$依次插入$HT$后，$HT$查找失败的平均查找长度是()。
A.4
B.5.25
C.6
D.6.29
解：$C$。
| 散列地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 关键字 | 98 | 22 | 30 | 87 | 11 | 40 | 20 |
由于$H(key)=0\sim6$，查找失败时可能对应的地址有$7$个，对于计算出地址为$0$的关键字$key0$，只有比较完$0\sim8$号地址后才能确定该关键字不在表中，比较次数为$9$，对于计算出地址为$1$的关键字$key1$，只有比较完$1\sim8$号地址后才能确定该关键字不在表中，比较次数为$8$。以此类推。需要特别注意的是，散列函数不可能计算出地址$7$，因此有 $ASL$失败$=(9+8+7+6+5+4+3)\div7=6$。