1、计算机专业基础综合数据结构（集合）历年真题试卷汇编 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.n2B.nC.log 2 (n+1)D.log 2 (n+1)3.设二叉排序中关键字由 1到 1000的整数构成，现要查找关键字为
2、 363的结点，下述关键字序列中，不可能是在二叉排序树上查找的序列的是( )。【北京交通大学 2005一、1(2 分)】（分数：2.00）A.2，252401，398，330，344，397，363B.924，220，911，244，898，258，363C.925，202，911，240，912，245，363D.2，399，387，219，266，382，381，278，3634.分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是( )。【合肥工业大学 2000一、4(2 分)】（分数：2.00）A.(100，80，90，60，120，1 10，130)B.(100，120
3、，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，150B.100，80，60，85，120，110，150C.100，80，85，60，120，110，150D.100，80，60，85，120，150，1106.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为 A，并已知 A的左孩子的平衡因子为 0，右孩子的平衡因子为 1，则应作( )
4、 型调整以使其平衡。【合肥工业大学 2001一、4(2 分)】（分数：2.00）A.LLB.LRC.RLD.RR7.设输入序列为20，35，构造一棵平衡二叉树，当在树中插入值 30时发生不平衡，则应进行的平衡旋转是( )。【南京理工大学 2005一、4(1 分)】（分数：2.00）A.LLB.RLC.LRD.RR8.已知一棵深度为 k的平衡二叉树，其每个非叶子结点的平衡因子均为 0，则该树共有结点总数为( )。【北京交通大学 2006一、2(2 分)】（分数：2.00）A.2 k-1 -1B.2 k-1 +1C.2 k -1D.2 k +19.在平衡二叉树中，进行查找的效率与( )有关。【北京
5、航空航天大学 2004】（分数：2.00）A.二叉树的深度B.二叉排序树的结点的个数C.后序线索树D.所有线索树10.下列关于 m阶 B一树的说法错误的是( )。【南京理工大学 1997一、9(2 分)】（分数：2.00）A.根结点至多有 m棵子树B.所有叶子都在同一层次上C.非叶结点至少有 m2(m 为偶数)或 m2-41(m 为奇数)棵子树D.根结点中的数据是有序的11.下面关于 m阶 B树说法正确的是( )。【南京理工大学 1999一、5(2 分)】每个结点至少有两棵非空子树；树中每个结点至多有 m-1个关键字；所有叶子在同一层上；当插入一个数据项引起 B树结点分裂后，树长高一层。（分数
6、：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+树都能有效地支持随机检索13.m阶 B一树是一棵( )。【北京邮电大学 2000二、2(208 分)】（分数：2.00）A.m叉排序树B.m叉平衡排序树C.m-1叉平衡排序树D.m+1叉平衡排序树14.在一棵含有 n个关键字的 m阶 B一树中进行查找，至多读盘( )次。【中科院计算所 2000一、6(2 分)】（分数：2.
7、00）A.log 2 nB.1+log 2 nC.D.15.m路 B+树是一棵(1)，其结点中关键字最多为 m个，最少m/2个。【中科院计算所 1999一、5(6 分)】（分数：2.00）A.m路平衡查找树B.m路平衡索引树C.m路 Ptrie树D.m路键树E.m-116.一棵 3阶 B一树中含有 2047个关键字，包括叶子结点层，该树的最大深度为( )。【北京交通大学2005一、2(2 分)】（分数：2.00）A.1 1B.12C.13D.1417.已知一棵 5阶 B树有 53个关键字，并且每个结点的关键字都达到最少状态，则它的深度是( )。【华南理工大学 2006一、8(2 分)】（分数：
8、2.00）A.3B.4C.5D.618.B + 树是( )。【武汉理工大学 2004一、13(3 分)】（分数：2.00）A.一利 AVL树B.索引表的一种组织形式C.一种高度不小于 1的树D.一种与二进制 Binary有关的树19.当向 B一树插入关键字时，可能引起结点的( )，最终可能导致整个 B一树的高度( )。【浙江大学2004】（分数：2.00）A.合并B.增加 1C.分裂D.减少 120.在一棵 m阶 B一树中，若在某结点中插入一个新关键字而引起该关键字的分裂，则此结点中原有的关键字个数是( )。【湖南大学 2003】（分数：2.00）A.mB.m+1C.m-1D.m2二、填空题(
9、总题数：5，分数：10.00)21.在有序表 A120】中，按二分查找方法进行查找，查找长度为 4的元素的下标从小到大依次是_。【合肥工业大学 2000三、10(2 分)】（分数：2.00）_22.已知有序表为(12，18，24，35，47，50，62，83，90，115，134)，当用二分法查找 90时，需_次查找成功，查 47时，需_次查找成功，查 100时，需_次才能确定不成功。【南京理工大学 2000二、7(45 分)】（分数：2.00）_23.n个结点的用于折半查找的判定树，表示查找失败的外部结点共有_个。【中南大学 2003三、12(1分)】（分数：2.00）_24.设表长为 10
10、23的有序线性表，查找每个元素的概率相等，采用折半查找方法，查找成功的 ASL是_。【北京交通大学 2005二、5(2 分)】（分数：2.00）_25.在一个按值有序排列的顺序表示中进行折半查找，其查找过程可以用一棵称之为“判断树”的二叉树来描述。若顺序表的长度为 19，则对应的“判断树”的根结点的左孩子之值(元素在表中的位置)是_。【北京航空航天大学 2006一、8(1 分)】（分数：2.00）_三、判断题(总题数：10，分数：20.00)26.对一个堆，按二叉树层次进行遍历可以得到一个有序序列。( )【中国海洋大学 2006二、14(1 分)】（分数：2.00）A.正确B.错误27.以同一
11、组数的不同序列来构造平衡二叉树，可能会得到不同的解。( )【北京邮电大学 2006二、9(1分)】（分数：2.00）A.正确B.错误28.在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。( )【南京理工大学 1997二、3(2 分)】（分数：2.00）A.正确B.错误29.平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定是零。 ( )【中国科学技术大学 1991一、6(2 分)】（分数：2.00）A.正确B.错误30.完全二叉树肯定是平衡二叉树。 ( )【南京航空航天大学 1996六、5(1 分)】（分数：2.00）A.正确B.错误31.
12、一棵平衡二叉树中的任意两个叶子结点的层次差的绝对值不大于 1。( )【北京邮电大学 2006二、8(1分)】（分数：2.00）A.正确B.错误32.AVL树是一棵二叉树，该树上任一结点的平衡因子的绝对值不大于 1。( )【中国海洋大学 2007二、13(1分)】（分数：2.00）A.正确B.错误33.在一棵 7阶 B树中，一个结点中最多有 6棵子树，最少有 3棵子树。( )【南京理工大学 2004二、9(1分)】（分数：2.00）A.正确B.错误34.高度为 8的 3阶 B一树中关键字数最少是 255。( )【北京交通大学 2005三、9(2 分)】（分数：2.00）A.正确B.错误35.对
13、B树删除某一个关键字值时，可能会引起结点的分裂。( )【中国海洋大学 2005二、6(1 分)】（分数：2.00）A.正确B.错误计算机专业基础综合数据结构（集合）历年真题试卷汇编 9答案解析(总分：70.00，做题时间：90 分钟)一、单项选择题(总题数：20，分数：40.00)1.下列二叉排序树中查找效率最高的是( )。【中南大学 2003二、11(1 分)】（分数：2.00）A.平衡二叉树 B.二叉查找树C.没有左子树的二叉排序树D.没有右子树的二叉排序树解析：2.构造一棵具有 n个结点的二叉排序树，最理想情况下的深度为( )。【华中科技大学 2007一、14(2 分)】（分数：2.00
14、）A.n2B.nC.log 2 (n+1)D.log 2 (n+1) 解析：3.设二叉排序中关键字由 1到 1000的整数构成，现要查找关键字为 363的结点，下述关键字序列中，不可能是在二叉排序树上查找的序列的是( )。【北京交通大学 2005一、1(2 分)】（分数：2.00）A.2，252401，398，330，344，397，363B.924，220，911，244，898，258，363C.925，202，911，240，912，245，363 D.2，399，387，219，266，382，381，278，363解析：4.分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不
15、同的是( )。【合肥工业大学 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，150C.100，80，85，60，120，110，150D.100，80，60，85，12
16、0，150，110解析：6.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为 A，并已知 A的左孩子的平衡因子为 0，右孩子的平衡因子为 1，则应作( ) 型调整以使其平衡。【合肥工业大学 2001一、4(2 分)】（分数：2.00）A.LLB.LRC.RL D.RR解析：解析：根据 A是最低的不平衡结点，“A 的左孩子的平衡因子为 0，右孩子的平衡因子为 1”，可见应做 RL型调整。7.设输入序列为20，35，构造一棵平衡二叉树，当在树中插入值 30时发生不平衡，则应进行的平衡旋转是( )。【南京理工大学 2005一、4(1 分)】（分数：2.00）A.LLB.RL C.LRD
17、.RR解析：8.已知一棵深度为 k的平衡二叉树，其每个非叶子结点的平衡因子均为 0，则该树共有结点总数为( )。【北京交通大学 2006一、2(2 分)】（分数：2.00）A.2 k-1 -1B.2 k-1 +1C.2 k -1 D.2 k +1解析：解析：该平衡二叉树实际上是深度为 k的满二又树。9.在平衡二叉树中，进行查找的效率与( )有关。【北京航空航天大学 2004】（分数：2.00）A.二叉树的深度 B.二叉排序树的结点的个数C.后序线索树D.所有线索树解析：10.下列关于 m阶 B一树的说法错误的是( )。【南京理工大学 1997一、9(2 分)】（分数：2.00）A.根结点至多有
18、 m棵子树B.所有叶子都在同一层次上C.非叶结点至少有 m2(m 为偶数)或 m2-41(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
19、.B树和 B+树都能有效地支持顺序检索 D.B树和 B+树都能有效地支持随机检索解析：13.m阶 B一树是一棵( )。【北京邮电大学 2000二、2(208 分)】（分数：2.00）A.m叉排序树B.m叉平衡排序树 C.m-1叉平衡排序树D.m+1叉平衡排序树解析：14.在一棵含有 n个关键字的 m阶 B一树中进行查找，至多读盘( )次。【中科院计算所 2000一、6(2 分)】（分数：2.00）A.log 2 nB.1+log 2 nC. D.解析：15.m路 B+树是一棵(1)，其结点中关键字最多为 m个，最少m/2个。【中科院计算所 1999一、5(6 分)】（分数：2.00）A.m路平
20、衡查找树B.m路平衡索引树 C.m路 Ptrie树D.m路键树E.m-1解析：16.一棵 3阶 B一树中含有 2047个关键字，包括叶子结点层，该树的最大深度为( )。【北京交通大学2005一、2(2 分)】（分数：2.00）A.1 1B.12 C.13D.14解析：解析：3 阶 B树又称 23树。在结点含最少关键字的情况下，23 树可以看做是满二叉树。高度包括叶子层。17.已知一棵 5阶 B树有 53个关键字，并且每个结点的关键字都达到最少状态，则它的深度是( )。【华南理工大学 2006一、8(2 分)】（分数：2.00）A.3B.4C.5 D.6解析：解析：5 阶 B树根结点最少 1个关
21、键字，其他结点最少 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有关的树解析：19.当向 B一树插入关键字时，可能引起结点的( )，最终可能导致整个 B一树的高度( )。【浙江大学2004】（分数：2.00）A.合并B.增加 1 C.分裂 D.减少 1解析：20.在一棵
22、 m阶 B一树中，若在某结点中插入一个新关键字而引起该关键字的分裂，则此结点中原有的关键字个数是( )。【湖南大学 2003】（分数：2.00）A.mB.m+1C.m-1 D.m2解析：二、填空题(总题数：5，分数：10.00)21.在有序表 A120】中，按二分查找方法进行查找，查找长度为 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时
23、，需_次查找成功，查 100时，需_次才能确定不成功。【南京理工大学 2000二、7(45 分)】（分数：2.00）_正确答案：(正确答案：2， 4， 3)解析：23.n个结点的用于折半查找的判定树，表示查找失败的外部结点共有_个。【中南大学 2003三、12(1分)】（分数：2.00）_正确答案：(正确答案：n+1)解析：24.设表长为 1023的有序线性表，查找每个元素的概率相等，采用折半查找方法，查找成功的 ASL是_。【北京交通大学 2005二、5(2 分)】（分数：2.00）_正确答案：(正确答案：9)解析：25.在一个按值有序排列的顺序表示中进行折半查找，其查找过程可以用一棵称之为
24、“判断树”的二叉树来描述。若顺序表的长度为 19，则对应的“判断树”的根结点的左孩子之值(元素在表中的位置)是_。【北京航空航天大学 2006一、8(1 分)】（分数：2.00）_正确答案：(正确答案：5)解析：三、判断题(总题数：10，分数：20.00)26.对一个堆，按二叉树层次进行遍历可以得到一个有序序列。( )【中国海洋大学 2006二、14(1 分)】（分数：2.00）A.正确B.错误 解析：27.以同一组数的不同序列来构造平衡二叉树，可能会得到不同的解。( )【北京邮电大学 2006二、9(1分)】（分数：2.00）A.正确 B.错误解析：28.在平衡二叉树中，向某个平衡因子不为零
25、的结点的树中插入一新结点，必引起平衡旋转。( )【南京理工大学 1997二、3(2 分)】（分数：2.00）A.正确B.错误 解析：29.平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定是零。 ( )【中国科学技术大学 1991一、6(2 分)】（分数：2.00）A.正确 B.错误解析：30.完全二叉树肯定是平衡二叉树。 ( )【南京航空航天大学 1996六、5(1 分)】（分数：2.00）A.正确B.错误 解析：解析：从平衡因子定义看，完全二叉树任一结点的平衡因子的绝对值确实是小于等于 1。但是，平衡二叉树本质上是二叉排序树，完全二叉树不一定是二叉排序树。故不能说完
26、全二叉树是平衡二叉树。31.一棵平衡二叉树中的任意两个叶子结点的层次差的绝对值不大于 1。( )【北京邮电大学 2006二、8(1分)】（分数：2.00）A.正确B.错误 解析：解析：平衡二叉树是指任意结点的左右子树层次(高度)差的绝对值小于等于 1。32.AVL树是一棵二叉树，该树上任一结点的平衡因子的绝对值不大于 1。( )【中国海洋大学 2007二、13(1分)】（分数：2.00）A.正确 B.错误解析：33.在一棵 7阶 B树中，一个结点中最多有 6棵子树，最少有 3棵子树。( )【南京理工大学 2004二、9(1分)】（分数：2.00）A.正确B.错误 解析：解析：7 阶 B树每个结点至多 7棵子树，除根结点最少可以有 2棵子树外，其余非终端结点最少有4棵子树。34.高度为 8的 3阶 B一树中关键字数最少是 255。( )【北京交通大学 2005三、9(2 分)】（分数：2.00）A.正确 B.错误解析：解析：具有最少关键字的 3阶 B树等价于平衡二叉树，而且是满二叉树。高度为 8(不含叶子层)的满二叉树有 255个结点。若含叶子层共 8层，则 127个结点。所以，本题叙述不严格。35.对 B树删除某一个关键字值时，可能会引起结点的分裂。( )【中国海洋大学 2005二、6(1 分)】（分数：2.00）A.正确B.错误 解析：
