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