【考研类试卷】计算机学科专业基础综合数据结构-查找(一)及答案解析.doc

《【考研类试卷】计算机学科专业基础综合数据结构-查找(一)及答案解析.doc》由会员分享，可在线阅读，更多相关《【考研类试卷】计算机学科专业基础综合数据结构-查找(一)及答案解析.doc（25页珍藏版）》请在麦多课文档分享上搜索。

1、计算机学科专业基础综合数据结构-查找(一)及答案解析(总分：100.00，做题时间：90 分钟)一、B单项选择题/B(总题数：38，分数：38.00)1.对长度为 n的有序单链表，若查找每个元素的概率相等，则顺序查找表中任一元素查找成功的平均查找长度为_。 A.n/2 B.(n+1)/2 C.(n-1)/2 D.n/4（分数：1.00）A.B.C.D.2.对线性表进行折半查找时，要求线性表必须_。 A.以顺序方式存储 B.以链接方式存储 C.以顺序方式存储，且结点按关键字有序排序 D.以链接方式存储，且结点按关键字有序排序（分数：1.00）A.B.C.D.3.采用折半查找方式查找一个长度为 n

2、的有序顺序表时，其平均查找长度为_。 A.O(n) B.O(log2n) C.O(n2) D.O(nlog2n)（分数：1.00）A.B.C.D.4.在对长度为 n的顺序存储的有序表进行折半查找时，对应的二叉判定树的高度为_。 An BC D （分数：1.00）A.B.C.D.5.采用折半查找法查找长度为 n的有序顺序表，查找每个元素的数据比较次数_对应二叉判定树的高度(设高度2)。 A.小于 B.大于 C.等于 D.小于等于（分数：1.00）A.B.C.D.6.已知有序顺序表(13，18，24，35，47，50，62，83，90，115，134)，当用折半查找法查找值为 18的元素时，查找成

3、功的数据比较次数为_。 A.1 B.2 C.3 D.4（分数：1.00）A.B.C.D.7.折半查找和二叉排序树的时间性能_。 A.相同 B.有时不相同 C.完全不同 D.不定（分数：1.00）A.B.C.D.8.m阶 B树是一棵_。 A.m叉查找树 B.m叉高度平衡查找树 C.m-1叉高度平衡查找树 D.m+1叉高度平衡查找树（分数：1.00）A.B.C.D.9.在 10阶 B树中根结点所包含的关键字个数最多为_，最少为 1。 A.7 B.8 C.9 D.10（分数：1.00）A.B.C.D.10.在一棵 m阶 B树的结点中插入新关键字时，若插入前结点的关键字数为_，则插入新关键字后该结点必

4、须分裂为两个结点。 A.m B.m-1 C.m+1 D.m-2（分数：1.00）A.B.C.D.11.在一棵高度为 h的 B树中插入一个新关键字时，为查找插入位置需读取_个结点。 A.h-1 B.h C.h+1 D.h+2（分数：1.00）A.B.C.D.12.下面关于 B树和 B+树的叙述中，错误的是_。 A.B树和 B+树都是平衡的多叉查找树 B.B树和 B+树都可用于文件的索引结构 C.B树和 B+树都能有效地支持顺序查找 D.B树和 B+树都能有效地支持随机查找（分数：1.00）A.B.C.D.13.散列法存储的基本思想是根据_来决定元素的存储地址。 A.元素的序号 B.元素个数 C.

5、关键字值 D.非码属性（分数：1.00）A.B.C.D.14.使用散列函数将元素的关键字值映射为散列地址时，常会产生冲突。此时的冲突是指_。 A.两个元素具有相同的序号 B.两个元素的关键字值不同，而非关键字值相同 C.不同关键字值对应到相同的存储地址 D.装填因子过大，数据元素过多（分数：1.00）A.B.C.D.15.以下关于散列函数选择原则的叙述中，不正确的是_。 A.散列函数应是简单的，能在较短的时间内计算出结果 B.散列函数的定义域应包括全部关键字值，值域必须在表范围之内 C.散列函数计算出来的地址应能均匀分布在整个地址空间中 D.装填因子必须限制在 0.8以下（分数：1.00）A.

6、B.C.D.16.设一个散列表中有 n个元素，用散列法进行查找的平均查找长度是_。 A.O(1) B.O(n) C.O(log2n) D.O(n2)（分数：1.00）A.B.C.D.17.在采用链地址法解决冲突时，每一个散列地址所链接的同义词子表中各个表项的_相同。 A.关键字值 B.元素值 C.散列地址 D.含义（分数：1.00）A.B.C.D.18.散列表的平均查找长度_。 A.与处理冲突的方法有关而与表的长度无关 B.与处理冲突的方法无关而与表的长度有关 C.与处理冲突的方法有关且与表的长度有关 D.与处理冲突的方法无关且与表的长度无关（分数：1.00）A.B.C.D.19.对于长度为

7、9的有序顺序表，若采用折半查找，在相等查找概率的情况下查找成功的平均查找长度为_，查找不成功的平均查找长度为 34/10。 A.20/9 B.18/9 C.25/9 D.34/9（分数：1.00）A.B.C.D.20.下面关于 m阶 B树的说法中，正确的是_。每个结点至少有两棵非空子树B 树中每个结点至多有 m-1个关键字所有失败结点在同一层次上当插入一个索引项引起 B树结点分裂后，树长高一层 A. B. C. D.（分数：1.00）A.B.C.D.21.下列关于 m阶 B树的说法中，错误的是_。 A.根结点至多有 m棵子树 B.所有叶结点都在同一层次上 C.非失败结点至少有 m/2(m为偶数

8、)或 m/2+1(m为奇数)棵子树 D.根结点中的数据是有序的（分数：1.00）A.B.C.D.22.含有 n个结点(不包括失败结点)的 m阶 B树至少包含_个关键字。 An B(m-1)n C D （分数：1.00）A.B.C.D.23.具有 n个关键字的 m阶 B树有_个失败结点。 An+1 Bn-1 Cnm D （分数：1.00）A.B.C.D.24.已知一棵 5阶 B树有 53个关键字，并且每个结点的关键字都达到最少，则该树的高度是_。 A.3 B.4 C.5 D.6（分数：1.00）A.B.C.D.25.在一棵含有 n个关键字的 m阶 B树中进行查找，至多读盘_次。Alog 2nB1

9、+log 2nCD （分数：1.00）A.B.C.D.26.在一棵高度为 h的 B树中插入一个新关键字可能导致结点分裂，这种分裂过程可能从下向上直到根，使得树的高度增加。假设内存足够大，在插入过程中为查找插入位置读入的结点一直在内存中，在最坏情况下可能需要读/写_次磁盘。 A.h+1 B.2h+1 C.3h+1 D.4h+2（分数：1.00）A.B.C.D.27.如果在一棵 m阶 B树中删除关键字导致结点需要与其右兄弟或左兄弟结点合并，那么被删关键字所在结点的关键字数在删除之前应为_。 A B C D （分数：1.00）A.B.C.D.28.从一棵高度为 h的 B树中删除一个已有的关键字。假定

10、内存空间足够大，可以把查找被删关键字所在结点而读入的结点都保存在内存中，最坏情况下从下向上，一直到根都要进行结点的合并，那么在这种情况下需要读/写_次磁盘。 A.h+1 B.2h-1 C.3h-2 D.4h-3（分数：1.00）A.B.C.D.29.假定从空树开始建立一棵有 n个关键字的 m阶 B树，最终得到有 p(p2)个非失败结点的 B树，那么这 p个结点最多经过_次分裂得来。 A.p B.p-1 C.p-2 D.p-3（分数：1.00）A.B.C.D.30.设高度为 h的 m阶 B树有 n个关键字，即第 h+1层是失败结点，那么 n至少为_。 A B C D （分数：1.00）A.B.C

11、.D.31.已知一棵 10阶 B+树中含有 960个关键字，则该树的最小高度为_。 A.3 B.4 C.5 D.6（分数：1.00）A.B.C.D.32.计算出的地址分布最均匀的散列函数是_。 A.数字分析法 B.除留余数法 C.平方取中法 D.折叠法（分数：1.00）A.B.C.D.33.散列函数有一个共同的性质，即函数值应当以_取其值域的每个值。 A.最大概率 B.最小概率 C.平均概率 D.同等概率（分数：1.00）A.B.C.D.34.在用开放定址法造出的散列表中，散列到同一个地址而引起的“堆积”问题是由于_引起的。 A.同义词之间发生冲突 B.非同义词之间发生冲突 C.同义词之间或非

12、同义词之间发生冲突 D.散列表“溢出”（分数：1.00）A.B.C.D.35.假设有 k个关键字互为同义词，若用线性探测法把这 k个关键字值存入散列表中，至少要进行_次探测。 A.k-1 B.k C.k+1 D.k(k+1)/2（分数：1.00）A.B.C.D.36.随着散列表的装填因子 a的增大，查找表中指定表项的平均查找长度也要增大，但如果采用_法解决冲突，可平稳控制平均查找长度的增大幅度达到最小。 A.线性探测 B.二次探测 C.双散列 D.链地址（分数：1.00）A.B.C.D.37.解决散列法中出现的冲突问题常采用的方法是_。 A.数字分析法、除留余数法、平方取中法 B.数字分析法、

13、除留余数法、线性探测法 C.数字分析法、线性探测法、双散列法 D.线性探测法、双散列法、链地址法（分数：1.00）A.B.C.D.38.已知一个线性序列38，25，74，63，52，48，假定采用散列函数 Hash(key)=key%7计算散列地址，散列存储在散列表 A10中。若采用线性探测法解决冲突，且各元素的查找概率相等，则在该散列表上查找不成功的平均查找长度为_。 A.2.60 B.3.14 C.3.71 D.4.33（分数：1.00）A.B.C.D.二、B综合应用题/B(总题数：9，分数：62.00)39.给出在一个递增有序表 A中采用二分查找算法查找值为 x的元素的递归算法。（分数：

14、7.00）_40.使用散列函数： H(k)=3k mod 11 并采用链地址法处理冲突。试对关键字序列(22，41，53，46，30，13，01，67)构造哈希表，求等概率情况下查找成功的平均查找长度，并设计构造哈希表的完整的算法。（分数：7.00）_41.给定整型数组 B0，M0，N。已知 B中数据在每一维方向上都按从小到大的次序排列，且整型变量 x在 B中存在。设计一个程序段，找出一对满足 Bij=x的 i，j 值，找到后输出 i和 j的值，要求比较次数不超过 M+N。（分数：7.00）_42.编写一个函数，利用二分查找算法在一个有序表中插入一个元素 x，并保持表的有序性。（分数：7.00

15、）_43.以下图所示的索引表结构为例，设计一个进行数据查找的算法。（分数：7.00）_44.使用散列函数：H(k)=3k mod 11并采用开放地址法处理冲突，所求下一地址函数为d1=H(k)di=(di-1+(7k mod 10)+1)%11(i=2，3，)试在 010 的散列地址空间中对关键字序列(22，41，53，46，30，13，01，67)构造哈希表，求等概率情况下查找成功的平均查找长度，并设计构造哈希表的完整的算法。（分数：7.00）_45.使用散列函数： H(k)=3k mod 11 采用开放地址法处理冲突时，设计一个算法查找一个指定元素值的位置。（分数：7.00）_46.使用散

16、列函数： H(k)=3k mod 11 采用链地址法处理冲突时，设计一个算法删除一个指定的结点。（分数：7.00）_47.有一棵如下图所示的 B-树(m=3)，设计一个算法对其进行先序遍历(遍历到结点时直接输出结点中的关键字)和查找给定值的结点，要求写出 B-树结点结构。（分数：6.00）_计算机学科专业基础综合数据结构-查找(一)答案解析(总分：100.00，做题时间：90 分钟)一、B单项选择题/B(总题数：38，分数：38.00)1.对长度为 n的有序单链表，若查找每个元素的概率相等，则顺序查找表中任一元素查找成功的平均查找长度为_。 A.n/2 B.(n+1)/2 C.(n-1)/2

17、D.n/4（分数：1.00）A.B. C.D.解析：解析 对单链表和顺序表进行顺序查找，都需要逐个扫描表中元素，因此其平均查找长度相同，都是(n+1)/2。2.对线性表进行折半查找时，要求线性表必须_。 A.以顺序方式存储 B.以链接方式存储 C.以顺序方式存储，且结点按关键字有序排序 D.以链接方式存储，且结点按关键字有序排序（分数：1.00）A.B.C. D.解析：解析 折半查找要求表的存储结构有随机存储特性，且表中元素要有序，因此本题选 C。3.采用折半查找方式查找一个长度为 n的有序顺序表时，其平均查找长度为_。 A.O(n) B.O(log2n) C.O(n2) D.O(nlog2n

18、)（分数：1.00）A.B. C.D.解析：解析 对长度为 n的有序顺序表进行折半查找，其平均查找长度与有 n个结点的完全二叉树同数量级，即 O(log2n)，因此本题选 B。4.在对长度为 n的顺序存储的有序表进行折半查找时，对应的二叉判定树的高度为_。 An BC D （分数：1.00）A.B.C.D. 解析：解析 折半查找的平均查找长度可用二叉判定树分析，其高度与完全二叉树相同，根据完全二叉树的性质，有*。5.采用折半查找法查找长度为 n的有序顺序表，查找每个元素的数据比较次数_对应二叉判定树的高度(设高度2)。 A.小于 B.大于 C.等于 D.小于等于（分数：1.00）A.B.C.D

19、. 解析：解析 对有序顺序表中的元素进行查找所需要的总比较次数与对应元素在表中的位置有关，最多不会超出该表对应二叉判定树的高度，因此本题选 D。6.已知有序顺序表(13，18，24，35，47，50，62，83，90，115，134)，当用折半查找法查找值为 18的元素时，查找成功的数据比较次数为_。 A.1 B.2 C.3 D.4（分数：1.00）A.B.C.D. 解析：解析 采用折半查找的查找序列为 50，24，13，18。注意，每次在一个查找区间找中点时，如果区间中元素个数为偶数，如 n=4，则取中间偏前的元素，即*。7.折半查找和二叉排序树的时间性能_。 A.相同 B.有时不相同 C.

20、完全不同 D.不定（分数：1.00）A.B. C.D.解析：解析 折半查找的平均查找长度和最大查找长度都是 O(log2n)；二叉排序树的查找性能与数据的输入顺序有关，最好情况下的平均查找长度与折半查找相同，但最坏情况下，即形成单支树的场合，其查找长度为 O(n)。8.m阶 B树是一棵_。 A.m叉查找树 B.m叉高度平衡查找树 C.m-1叉高度平衡查找树 D.m+1叉高度平衡查找树（分数：1.00）A.B. C.D.解析：解析 根据 m阶 B树的定义，树中的每个结点最多有 m棵子树，且严格限制所有失败结点在同一层次上，所以是 m叉高度平衡树。此外，B 树根结点中的各关键字值都大于它左边子树上

21、所有结点的关键字值，同时小于它右边子树上所有结点的关键字值，且结点内所有关键字是从小到大有序排列的，所以它又是查找树。9.在 10阶 B树中根结点所包含的关键字个数最多为_，最少为 1。 A.7 B.8 C.9 D.10（分数：1.00）A.B.C. D.解析：解析 根据 B树的定义，10 阶 B树的根结点最多可以有 9个关键字(m=10-1)，最少有 1个关键字。10.在一棵 m阶 B树的结点中插入新关键字时，若插入前结点的关键字数为_，则插入新关键字后该结点必须分裂为两个结点。 A.m B.m-1 C.m+1 D.m-2（分数：1.00）A.B. C.D.解析：解析 根据 m阶 B树的定义

22、，树中每个结点最多有 m棵子树，有 m-1个关键字，若插入新关键字后该结点的关键字数超过了 m-1，则需要进行分裂。11.在一棵高度为 h的 B树中插入一个新关键字时，为查找插入位置需读取_个结点。 A.h-1 B.h C.h+1 D.h+2（分数：1.00）A.B. C.D.解析：解析 根据 B树的性质，新关键字插入在叶结点上。为查找插入位置需读取的结点数等于树的高度。12.下面关于 B树和 B+树的叙述中，错误的是_。 A.B树和 B+树都是平衡的多叉查找树 B.B树和 B+树都可用于文件的索引结构 C.B树和 B+树都能有效地支持顺序查找 D.B树和 B+树都能有效地支持随机查找（分数：

23、1.00）A.B.C. D.解析：解析 B 树和 B+树都是平衡的 m叉查找树，都用于文件的索引结构，都能有效地支持随机查找，因为结点中的元素有序，且是顺序存储。理想情况下，每深入一层，就把查找范围缩小到原来的 1/m，很快逼近到查找的目标。但对于 B树整体而言不支持顺序查找，即不能方便地顺序扫描整棵树中的所有结点，而 B+树所有叶结点有一条链把它们顺序链接起来，所以 B+树能支持顺序查找。13.散列法存储的基本思想是根据_来决定元素的存储地址。 A.元素的序号 B.元素个数 C.关键字值 D.非码属性（分数：1.00）A.B.C. D.解析：解析 散列法存储的基本原理是：将元素的关键字作为自

24、变量，通过一定的函数(称为散列函数)，计算出对应的函数值，把这个函数值作为元素的存储地址。14.使用散列函数将元素的关键字值映射为散列地址时，常会产生冲突。此时的冲突是指_。 A.两个元素具有相同的序号 B.两个元素的关键字值不同，而非关键字值相同 C.不同关键字值对应到相同的存储地址 D.装填因子过大，数据元素过多（分数：1.00）A.B.C. D.解析：解析 发生冲突的原因是由于在使用散列函数时经常把不同的关键字值映射到同一个散列地址上，即不同的自变量得到了相同的函数值。15.以下关于散列函数选择原则的叙述中，不正确的是_。 A.散列函数应是简单的，能在较短的时间内计算出结果 B.散列函数

25、的定义域应包括全部关键字值，值域必须在表范围之内 C.散列函数计算出来的地址应能均匀分布在整个地址空间中 D.装填因子必须限制在 0.8以下（分数：1.00）A.B.C.D. 解析：解析 装填因子不是选择散列函数的原则。当然，不同的散列函数在装填因子不断增大的情况下，平均查找长度的增长速度是不同的。16.设一个散列表中有 n个元素，用散列法进行查找的平均查找长度是_。 A.O(1) B.O(n) C.O(log2n) D.O(n2)（分数：1.00）A. B.C.D.解析：解析 散列法通过函数值可以直接找出其存储地址，而无须进行多次关键字的比较(冲突发生时除外)，因此查找速度非常快，时间复杂度

26、为常量级。17.在采用链地址法解决冲突时，每一个散列地址所链接的同义词子表中各个表项的_相同。 A.关键字值 B.元素值 C.散列地址 D.含义（分数：1.00）A.B.C. D.解析：解析 同义词子表所链接的各个表项的关键字互为同义词，意味着虽然这些关键字的值不同，但用同一个散列函数计算出的散列地址相同。18.散列表的平均查找长度_。 A.与处理冲突的方法有关而与表的长度无关 B.与处理冲突的方法无关而与表的长度有关 C.与处理冲突的方法有关且与表的长度有关 D.与处理冲突的方法无关且与表的长度无关（分数：1.00）A. B.C.D.解析：解析 散列表的平均查找长度与处理冲突的方法有关，与装

27、填因子 a有关，与表的长度无关。19.对于长度为 9的有序顺序表，若采用折半查找，在相等查找概率的情况下查找成功的平均查找长度为_，查找不成功的平均查找长度为 34/10。 A.20/9 B.18/9 C.25/9 D.34/9（分数：1.00）A.B.C. D.解析：解析 在长度为 9的有序顺序表中进行折半查找，在相等查找概率下的查找性能可以用如下图所示的二叉判定树来分析。*每个圆形结点代表表中的一个数据元素，结点旁边附加的数字是该数据元素在表中的序号。在相等查找概率的情况下，查找成功的平均查找长度和查找不成功的平均查找长度分别为ASLsucc=(11+22+34+42)/9=25/9ASL

28、unsucc=(36+44)/10=34/1020.下面关于 m阶 B树的说法中，正确的是_。每个结点至少有两棵非空子树B 树中每个结点至多有 m-1个关键字所有失败结点在同一层次上当插入一个索引项引起 B树结点分裂后，树长高一层 A. B. C. D.（分数：1.00）A.B. C.D.解析：解析 根据 m阶 B树的定义，每个结点至多有 m棵子树，所以至多有 m-1个关键字；所有失败结点都在同一层上，所以正确。不正确，因为除根结点之外所有非失败结点至少有*棵子树；当插入一个索引项引起 B树结点分裂后，只有当根结点需要分裂时，树才长高一层。综合以上分析，本题选B。21.下列关于 m阶 B树的说

29、法中，错误的是_。 A.根结点至多有 m棵子树 B.所有叶结点都在同一层次上 C.非失败结点至少有 m/2(m为偶数)或 m/2+1(m为奇数)棵子树 D.根结点中的数据是有序的（分数：1.00）A.B.C. D.解析：解析 根据 m阶 B树的定义，每个结点(包括根结点)至多有 m棵子树，选项 A正确。B 树是高度平衡的，它限制所有失败结点都在同一层次上，B 树的叶结点是最底层非叶结点，不是失败结点，它也应在同一层次上，选项 A、B、D 正确。B 树除根结点以外的所有非失败结点至少有 m/2(m为偶数)或 m/2+1(m为奇数)棵子树，根结点至少有两棵子树，选项 C不正确。22.含有 n个结点

30、(不包括失败结点)的 m阶 B树至少包含_个关键字。 An B(m-1)n C D （分数：1.00）A.B.C.D. 解析：解析 根据 m阶 B树的定义，除根结点之外所有非失败结点至少有*棵子树，所以除根结点之外的所有非失败结点至少有*-1 个关键字，根结点至少有 1个关键字，所以共有(n-1)(*-1)+1 个关键字。23.具有 n个关键字的 m阶 B树有_个失败结点。 An+1 Bn-1 Cnm D （分数：1.00）A. B.C.D.解析：解析 m 阶 B树的失败结点即为查找失败走到的结点，对 n个关键字查找不成功的情况是待查找的关键字值介于 n个关键字中某两个关键字值之间，这样的可能

31、性有 n+1种，因此失败结点有 n+1个。24.已知一棵 5阶 B树有 53个关键字，并且每个结点的关键字都达到最少，则该树的高度是_。 A.3 B.4 C.5 D.6（分数：1.00）A.B. C.D.解析：解析 当每个结点的关键字都达到最少的时候，求此时树的高度即为求树的最大高度，可以用以下公式计算：*。25.在一棵含有 n个关键字的 m阶 B树中进行查找，至多读盘_次。Alog 2nB1+log 2nCD （分数：1.00）A.B.C. D.解析：解析 在具有 n个关键字的 m阶 B树中进行查找时，从根结点到关键字所在结点的路径上所涉及的结点数最多等于树的高度*，而每访问一个结点，最多读

32、 1次盘，因此读盘次数最多为 h。26.在一棵高度为 h的 B树中插入一个新关键字可能导致结点分裂，这种分裂过程可能从下向上直到根，使得树的高度增加。假设内存足够大，在插入过程中为查找插入位置读入的结点一直在内存中，在最坏情况下可能需要读/写_次磁盘。 A.h+1 B.2h+1 C.3h+1 D.4h+2（分数：1.00）A.B.C. D.解析：解析 在插入过程中为查找插入位置读入的结点数为 h，假设它们一直保存在内存中，最坏情况下从叶结点到根结点都要分裂，共分裂 h次，每次写出 2个结点，再加上 1次写出分裂出的新根结点，共读/写了 3h+1次磁盘。27.如果在一棵 m阶 B树中删除关键字导

33、致结点需要与其右兄弟或左兄弟结点合并，那么被删关键字所在结点的关键字数在删除之前应为_。 A B C D （分数：1.00）A.B. C.D.解析：解析 根据 m阶 B树的定义，除根结点之外每个非失败结点至少有*个关键字。因为在 B树中不论被删关键字在哪一层的结点上，最后都能归结到叶结点上的删除。如果在删除关键字之前叶结点中关键字数已经是*，那么在删除关键字之后该结点的关键字数不足*就必须进行结点的调整，当然不一定是结点合并，还要看兄弟结点内的关键字数。但如果要做结点合并，其兄弟结点关键字数一定也是*。28.从一棵高度为 h的 B树中删除一个已有的关键字。假定内存空间足够大，可以把查找被删关键

34、字所在结点而读入的结点都保存在内存中，最坏情况下从下向上，一直到根都要进行结点的合并，那么在这种情况下需要读/写_次磁盘。 A.h+1 B.2h-1 C.3h-2 D.4h-3（分数：1.00）A.B.C. D.解析：解析 如果被删关键字不在叶结点，则需要用它右边子树最小关键字(在叶结点内)或它左边子树最大关键字(在叶结点内)填补上来，再到叶结点中删除填补上去的关键字，这个过程需要读盘 h次。假设它们一直保存在内存中，最坏情况下从叶结点到根结点的下一层结点共 h-1层要做结点合并，每次合并需读入 1个兄弟结点，写出合并后的结点，共 3h-2次读/写盘，另外共删除了 h个结点。29.假定从空树开

35、始建立一棵有 n个关键字的 m阶 B树，最终得到有 p(p2)个非失败结点的 B树，那么这 p个结点最多经过_次分裂得来。 A.p B.p-1 C.p-2 D.p-3（分数：1.00）A.B. C.D.解析：解析 从空树开始，最初建立的是根结点，又是叶结点。以后分裂成 p个结点，经过了 p-1次分裂。30.设高度为 h的 m阶 B树有 n个关键字，即第 h+1层是失败结点，那么 n至少为_。 A B C D （分数：1.00）A. B.C.D.解析：解析 根据 m阶 B树最大高度的推导，到了失败结点这一层*，因此有 n*。31.已知一棵 10阶 B+树中含有 960个关键字，则该树的最小高度为

36、_。 A.3 B.4 C.5 D.6（分数：1.00）A. B.C.D.解析：解析 让每一层关键字个数达到最多，高度就会降到最低。设该树的最小高度为 h，则10h960，*。32.计算出的地址分布最均匀的散列函数是_。 A.数字分析法 B.除留余数法 C.平方取中法 D.折叠法（分数：1.00）A.B. C.D.解析：解析 用除留余数法转换后的散列表在表的装填因子不断趋向 1的过程中，查找性能退化速度最慢，说明它产生的冲突最少，散列地址均匀分布在地址空间各处。33.散列函数有一个共同的性质，即函数值应当以_取其值域的每个值。 A.最大概率 B.最小概率 C.平均概率 D.同等概率（分数：1.0

37、0）A.B.C.D. 解析：解析 散列函数都有一个假定，即函数值应以同等概率取到值域的每个值，否则函数值不能均匀地分布到散列表的地址空间中。34.在用开放定址法造出的散列表中，散列到同一个地址而引起的“堆积”问题是由于_引起的。 A.同义词之间发生冲突 B.非同义词之间发生冲突 C.同义词之间或非同义词之间发生冲突 D.散列表“溢出”（分数：1.00）A.B.C. D.解析：解析 散列表中的“堆积”现象是由于同义词之间冲突而产生的探测序列占用了其他非同义词应该存放的存储空间，导致与非同义词之间冲突而产生探测序列之间的互相交织，从而延长了查找到“下一个空位”的时间，使得查找性能下降。35.假设有

38、 k个关键字互为同义词，若用线性探测法把这 k个关键字值存入散列表中，至少要进行_次探测。 A.k-1 B.k C.k+1 D.k(k+1)/2（分数：1.00）A.B.C.D. 解析：解析 探查次数最少的情况是第 1个关键字通过 1次比较后插入，第 2个关键字通过 2次比较后插入第 k个关键字通过 k次比较后插入。总的探查次数=1+2+k=k(k+1)/2。36.随着散列表的装填因子 a的增大，查找表中指定表项的平均查找长度也要增大，但如果采用_法解决冲突，可平稳控制平均查找长度的增大幅度达到最小。 A.线性探测 B.二次探测 C.双散列 D.链地址（分数：1.00）A.B.C.D. 解析：

39、解析 线性探测、二次探测和双散列都属于解决冲突的开地址法，寻找下一个空位的操作仅限于散列表本身的基本存储空间，随着表的装满程度的增加，冲突越来越多，查找某一表项的平均查找次数也越来越多，以线性探测最甚。而链地址法设置溢出存储空间，装填因子 a的增大，仅表明基本存储空间装得越来越满，但大多数发生冲突的表项都存放到溢出空间去了，在基本存储空间的冲突没有大幅增加，平均查找次数也不会大幅增长。37.解决散列法中出现的冲突问题常采用的方法是_。 A.数字分析法、除留余数法、平方取中法 B.数字分析法、除留余数法、线性探测法 C.数字分析法、线性探测法、双散列法 D.线性探测法、双散列法、链地址法（分数：

40、1.00）A.B.C.D. 解析：解析 常用的解决冲突的方法有两大类：开地址法和链地址法。开地址法中寻找下一个可存放元素的空位不超出表的范围，它又有线性探测、二次探测或双散列之分。链地址法采用链表方式，在表的范围之外分配空间存放发生冲突的元素。38.已知一个线性序列38，25，74，63，52，48，假定采用散列函数 Hash(key)=key%7计算散列地址，散列存储在散列表 A10中。若采用线性探测法解决冲突，且各元素的查找概率相等，则在该散列表上查找不成功的平均查找长度为_。 A.2.60 B.3.14 C.3.71 D.4.33（分数：1.00）A.B. C.D.解析：解析 根据散列函

41、数可计算的散列地址有 7个，为 06。如果有新的元素需要插入到这些地址，需要的探测次数如下：0 号地址冲突，需要探查 2次找到空位；1 号地址、2 号地址本身为空，1 次探查就可找到空位；3 号地址需要 6次探查找到空位；4 号地址需要 5次，5 号地址需要 4次，6 号地址需要 3次探查找到空位。查找不成功的平均查找长度为 ASLunsucc=(2+1+1+6+5+4+3)/7=3.14。二、B综合应用题/B(总题数：9，分数：62.00)39.给出在一个递增有序表 A中采用二分查找算法查找值为 x的元素的递归算法。（分数：7.00）_正确答案：(每次在当前序列中取序列中点作为区域划分界限，

42、然后对子区域分别递归地进行查找即可，代码如下： int binsearch(int A,int l,int h,int x) int m; if(lh) return -1; /未找到，返回-1 else m=(l+h)/2; if(xAm) return(binsearch(A,l,m-1,x); /在右段中查找 else if(x=Am) return m; /找到了，返回下标 x else return(binsearch(A,m+1,h,x); /在左段中查找 )解析：40.使用散列函数： H(k)=3k mod 11 并采用链地址法处理冲突。试对关键字序列(22，41，53，46，30，13，01，67)构造哈希表，求等概率情况下查找成功的平均查找长度，并设计构造哈希表的完整的算法。（分数：7.00）_正确答案：(本题的哈希表构造过程如下：(1)H(22)=3*22 mod 11=0(2)H(41)=3*41 mod 11=2(3)H(53)=3*53 mod 11=5(4)H(46)=3*46 mod 11=6(5)H(30)=3*30 mod 11=2(6)H(13)=3*13 mo