计算机专业基础综合数据结构（集合）历年真题试卷汇编9

(总分：70.00，做题时间：90分钟)

一、 单项选择题(总题数：20，分数：40.00)

1.下列二叉排序树中查找效率最高的是( )。【中南大学2003二、11(1分)】 （分数：2.00） A.平衡二叉树 √ B.二叉查找树

C.没有左子树的二叉排序树 D.没有右子树的二叉排序树 解析：

2.构造一棵具有n个结点的二叉排序树，最理想情况下的深度为( )。【华中科技大学2007一、14(2分)】 （分数：2.00） A.n／2 B.n

C.[log 2 (n+1)] D.[log 2 (n+1)] √ 解析：

3.设二叉排序中关键字由1到1000的整数构成，现要查找关键字为363的结点，下述关键字序列中，不可能是在二叉排序树上查找的序列的是( )。【北京交通大学2005一、1(2分)】 （分数：2.00）

A.2，252．401，398，330，344，397，363 B.924，220，911，244，898，258，363 C.925，202，911，240，912，245，363 √ D.2，399，387，219，266，382，381，278，363 解析：

4.分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是( )。【合肥工业大学2000一、4(2分)】 （分数：2.00）

A.(100，80，90，60，120，1 10，130) B.(100，120，110，130，80，60，90) C.(100，60，80，90，20，110，130) √ D.(100，80，60，90，120，130，110) 解析：

5.分别以下列序列构造二叉排序树，与众不同的是( )。【中国科学技术大学2004】 （分数：2.00）

A.100，80，60，85，110，120，150 √ B.100，80，60，85，120，110，150 C.100，80，85，60，120，110，150 D.100，80，60，85，120，150，110 解析：

6.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作( ) 型调整以使其平衡。【合肥工业大学2001一、4(2分)】 （分数：2.00） A.LL B.LR C.RL √ D.RR

解析：解析：根据A是最低的不平衡结点，“A的左孩子的平衡因子为0，右孩子的平衡因子为1”，可见应做RL型调整。

7.设输入序列为{20，35，…}，构造一棵平衡二叉树，当在树中插入值30时发生不平衡，则应进行的平衡旋转是( )。【南京理工大学2005一、4(1分)】 （分数：2.00） A.LL B.RL √ C.LR D.RR 解析：

8.已知一棵深度为k的平衡二叉树，其每个非叶子结点的平衡因子均为0，则该树共有结点总数为( )。【北京交通大学2006一、2(2分)】 （分数：2.00） A.2 -1 B.2 +1 C.2 -1 √ D.2 +1

解析：解析：该平衡二叉树实际上是深度为k的满二又树。

9.在平衡二叉树中，进行查找的效率与( )有关。【北京航空航天大学2004】 （分数：2.00） A.二叉树的深度 √ B.二叉排序树的结点的个数 C.后序线索树 D.所有线索树 解析：

10.下列关于m阶B一树的说法错误的是( )。【南京理工大学1997一、9(2分)】 （分数：2.00）

A.根结点至多有m棵子树 B.所有叶子都在同一层次上

C.非叶结点至少有m／2(m为偶数)或m／2-4—1(m为奇数)棵子树 √ D.根结点中的数据是有序的 解析：

11.下面关于m阶B树说法正确的是( )。【南京理工大学1999一、5(2分)】①每个结点至少有两棵非空子树；②树中每个结点至多有m-1个关键字；③所有叶子在同一层上；④当插入一个数据项引起B树结点分裂后，树长高一层。 （分数：2.00） A.①②③ B.②③ √ C.②③④ D.③ 解析：

12.下面关于B和B+树的叙述中，不正确的是( )。【北方交通大学2001一、17(2分)】 （分数：2.00）

A.B树和B+树都是平衡的多叉树 B.B树和B+树都可用于文件的索引结构 C.B树和B+树都能有效地支持顺序检索 √ D.B树和B+树都能有效地支持随机检索 解析：

kkk-1k-1

13.m阶B一树是一棵( )。【北京邮电大学2000二、2(20／8分)】 （分数：2.00） A.m叉排序树 B.m叉平衡排序树 √ C.m-1叉平衡排序树 D.m+1叉平衡排序树 解析：

14.在一棵含有n个关键字的m阶B一树中进行查找，至多读盘( )次。【中科院计算所2000一、6(2分)】 （分数：2.00） A.log 2 B.1+log 2 C. D.解析：

15.m路B+树是一棵((1))，其结点中关键字最多为m个，最少[m/2]个。【中科院计算所1999一、5(6分)】 （分数：2.00） A.m路平衡查找树 B.m路平衡索引树 √ C.m路Ptrie树 D.m路键树 E.m-1 解析：

16.一棵3阶B一树中含有2047个关键字，包括叶子结点层，该树的最大深度为( )。【北京交通大学2005一、2(2分)】 （分数：2.00） A.1 1 B.12 √ C.13 D.14

解析：解析：3阶B树又称2—3树。在结点含最少关键字的情况下，2—3树可以看做是满二叉树。高度包括叶子层。

17.已知一棵5阶B树有53个关键字，并且每个结点的关键字都达到最少状态，则它的深度是( )。【华南理工大学2006一、8(2分)】 （分数：2.00） A.3 B.4 C.5 √ D.6

解析：解析：5阶B树根结点最少1个关键字，其他结点最少2个关键字。所以，第1层1个关键字(两棵子树)，第2层4个关键字，第3层6个结点12个关键字，第4层18个结点36个关键字，上面5层53个关键字。第5层是叶子。

18.B 树是( )。【武汉理工大学2004一、13(3分)】 （分数：2.00） A.一利AVL树 √

B.索引表的一种组织形式 √ C.一种高度不小于1的树 D.一种与二进制Binary有关的树

+

nn

√ 解析：

19.当向B一树插入关键字时，可能引起结点的( )，最终可能导致整个B一树的高度( )。【浙江大学2004】 （分数：2.00） A.合并 B.增加1 √ C.分裂 √ D.减少1 解析：

20.在一棵m阶B一树中，若在某结点中插入一个新关键字而引起该关键字的分裂，则此结点中原有的关键字个数是( )。【湖南大学2003】 （分数：2.00） A.m B.m+1 C.m-1 √ D.m／2 解析：

二、 填空题(总题数：5，分数：10.00)

21.在有序表A[1．．20】中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是__________。【合肥工业大学2000三、10(2分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：1，3，6，8，11，13，16，19) 解析：

22.已知有序表为(12，18，24，35，47，50，62，83，90，115，134)，当用二分法查找90时，需__________次查找成功，查47时，需__________次查找成功，查100时，需__________次才能确定不成功。【南京理工大学2000二、7(4．5分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：2， 4， 3) 解析：

23.n个结点的用于折半查找的判定树，表示查找失败的外部结点共有__________个。【中南大学2003三、12(1分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：n+1) 解析：

24.设表长为1023的有序线性表，查找每个元素的概率相等，采用折半查找方法，查找成功的ASL是__________。【北京交通大学2005二、5(2分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：9) 解析：

25.在一个按值有序排列的顺序表示中进行折半查找，其查找过程可以用一棵称之为“判断树”的二叉树来描述。若顺序表的长度为19，则对应的“判断树”的根结点的左孩子之值(元素在表中的位置)是__________。【北京航空航天大学2006一、8(1分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：5) 解析：