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

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

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

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

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

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

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

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

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

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】 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分)】 A.LL B.LR C.RL √ D.RR

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

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

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

k-1

B.2 +1 C.2 -1 √ D.2 +1

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

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

10.下列关于m阶B一树的说法错误的是( )。【南京理工大学1997一、9(2分)】 A.根结点至多有m棵子树 B.所有叶子都在同一层次上

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

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

12.下面关于B和B+树的叙述中，不正确的是( )。【北方交通大学2001一、17(2分)】 A.B树和B+树都是平衡的多叉树 B.B树和B+树都可用于文件的索引结构 C.B树和B+树都能有效地支持顺序检索 √ D.B树和B+树都能有效地支持随机检索

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

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

kk

k-1

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

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

D.14

3阶B树又称2—3树。在结点含最少关键字的情况下，2—3树可以看做是满二叉树。高度包括叶子层。 17.已知一棵5阶B树有53个关键字，并且每个结点的关键字都达到最少状态，则它的深度是( )。【华南理工大学2006一、8(2分)】 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分)】 A.一利AVL树 √

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

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

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

+

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

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

__________________________________________________________________________________________ 正确答案：(正确答案：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， 4， 3)

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

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

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

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

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

__________________________________________________________________________________________

正确答案：(正确答案：5)

三、 判断题(总题数：10，分数：20.00)

26.对一个堆，按二叉树层次进行遍历可以得到一个有序序列。( )【中国海洋大学2006二、14(1分)】 A.正确 B.错误 √

27.以同一组数的不同序列来构造平衡二叉树，可能会得到不同的解。( )【北京邮电大学2006二、9(1分)】 A.正确 √ B.错误

28.在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。( )【南京理工大学1997二、3(2分)】 A.正确 B.错误 √

29.平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定是零。 ( )【中国科学技术大学1991一、6(2分)】 A.正确 √ B.错误

30.完全二叉树肯定是平衡二叉树。 ( )【南京航空航天大学1996六、5(1分)】 A.正确 B.错误 √

从平衡因子定义看，完全二叉树任一结点的平衡因子的绝对值确实是小于等于1。但是，平衡二叉树本质上是二叉排序树，完全二叉树不一定是二叉排序树。故不能说完全二叉树是平衡二叉树。

31.一棵平衡二叉树中的任意两个叶子结点的层次差的绝对值不大于1。( )【北京邮电大学2006二、8(1分)】 A.正确 B.错误 √

平衡二叉树是指任意结点的左右子树层次(高度)差的绝对值小于等于1。

32.AVL树是一棵二叉树，该树上任一结点的平衡因子的绝对值不大于1。( )【中国海洋大学2007二、13(1分)】 A.正确 √ B.错误

33.在一棵7阶B树中，一个结点中最多有6棵子树，最少有3棵子树。( )【南京理工大学2004二、9(1分)】 A.正确 B.错误 √

7阶B树每个结点至多7棵子树，除根结点最少可以有2棵子树外，其余非终端结点最少有4棵子树。 34.高度为8的3阶B一树中关键字数最少是255。( )【北京交通大学2005三、9(2分)】 A.正确 √ B.错误

具有最少关键字的3阶B树等价于平衡二叉树，而且是满二叉树。高度为8(不含叶子层)的满二叉树有255个结点。若含叶子层共8层，则127个结点。所以，本题叙述不严格。

35.对B树删除某一个关键字值时，可能会引起结点的分裂。( )【中国海洋大学2005二、6(1分)】 A.正确 B.错误 √