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

计算机专业基础综合数据结构（集合）历年真题试卷汇编9（总分：70.00，做题时间：90分钟）、单项选择题（总题数：20，分数：40.00）1.下列二叉排序树中查找效率最高的是（）。【中南大学2003二、11（1分）】平衡二叉树丿二叉查找树没有左子树的二叉排序树没有右子树的二叉排序树2•构造一棵具有n个结点的二叉排序树，最理想情况下的深度为（）。【华中科技大学2007—、14（2分）】n／2n[log （n+1）]2[log （n+1）]V2设二叉排序中关键字由1到1000的整数构成，现要查找关键字为363的结点，下述关键字序列中，不可能是在二叉排序树上查找的序列的是（）。【北京交通大学2005一、1（2分）】2，252．401，398，330，344，397，363924， 220， 911，244， 898， 258， 363925， 202， 911，240， 912， 245， 363 V2，399，387，219，266，382，381，278，363分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（）。【合肥工业大学2000一、4（2分）】（100，80，90，60，120，110，130）（100，120，110，130，80，60，90）（100，60，80，90，20，110，130）V（100，80，60，90，120，130，110）分别以下列序列构造二叉排序树，与众不同的是（）。【中国科学技术大学2004】A.100，80，60，85，110，120，150VB.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，则应作（）型调整以使其平衡。【合肥工业大学2001一、4（2分）】LLLRRLVRR根据A是最低的不平衡结点，“A的左孩子的平衡因子为0,右孩子的平衡因子为1”，可见应做RL型调整。7•设输入序列为{20,35,・・・},构造一棵平衡二叉树，当在树中插入值30时发生不平衡，则应进行的平衡旋转是（）。【南京理工大学2005一、4（1分）】TOC\o"1-5"\h\zLLRLVLRRR已知一棵深度为k的平衡二叉树，其每个非叶子结点的平衡因子均为0,则该树共有结点总数为（）。【北京交通大学2006一、2（2分）】A.2k-1-1B.2k-1+12k-1丿2k+1该平衡二叉树实际上是深度为k的满二又树。在平衡二叉树中，进行查找的效率与（）有关。【北京航空航天大学2004】二叉树的深度丿二叉排序树的结点的个数后序线索树所有线索树下列关于m阶B一树的说法错误的是（）。【南京理工大学1997—、9（2分）】根结点至多有m棵子树所有叶子都在同一层次上非叶结点至少有m/2（m为偶数）或m/2-4—1（m为奇数）棵子树丿根结点中的数据是有序的下面关于m阶B树说法正确的是（）。【南京理工大学1999一、5（2分）】①每个结点至少有两棵非空子树；②树中每个结点至多有m-1个关键字；③所有叶子在同一层上；④当插入一个数据项引起B树结点分裂后，树长高一层。TOC\o"1-5"\h\z①②③②③丿②③④③下面关于B和B+树的叙述中，不正确的是（）。【北方交通大学2001一、17（2分）】B树和B+树都是平衡的多叉树B树和B+树都可用于文件的索引结构B树和B+树都能有效地支持顺序检索丿B树和B+树都能有效地支持随机检索m阶B一树是一棵（）。【北京邮电大学2000二、2（20/8分）】m叉排序树m叉平衡排序树 丿m-1叉平衡排序树m+1叉平衡排序树在一棵含有n个关键字的m阶B一树中进行查找，至多读盘（）次。【中科院计算所2000一、6（2分）】logn2m路B+树是一棵（（1））,其结点中关键字最多为m个，最少［m/2］个。【中科院计算所1999一、5（6分）】m路平衡查找树m路平衡索引树丿m路Ptrie树m路键树m-1一棵3阶B一树中含有2047个关键字，包括叶子结点层，该树的最大深度为（）。【北京交通大学2005一、2（2分）】1112丿13143阶B树又称2—3树。在结点含最少关键字的情况下，2—3树可以看做是满二叉树。咼度包括叶子层。已知一棵5阶B树有53个关键字，并且每个结点的关键字都达到最少状态，则它的深度是（）。【华南理工大学2006一、8（2分）】TOC\o"1-5"\h\z345丿65阶B树根结点最少1个关键字，其他结点最少2个关键字。所以，第1层1个关键字（两棵子树），第2层4个关键字，第3层6个结点12个关键字，第4层18个结点36个关键字，上面5层53个关键字。第5层是叶子。B+树是（）。【武汉理工大学2004一、13（3分）】一利AVL树V索引表的一种组织形式V一种咼度不小于1的树一种与二进制Binary有关的树当向B一树插入关键字时，可能引起结点的（），最终可能导致整个B一树的高度（）。【浙江大学2004】合并增加1V分裂V减少1在一棵m阶B一树中，若在某结点中插入一个新关键字而引起该关键字的分裂，则此结点中原有的关键字个数是（）。【湖南大学2003】TOC\o"1-5"\h\zmm+1m-1Vm／2二、填空题（总题数：5，分数：10.00）21•在有序表A[1..20】中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是 。【合肥工业大学2000三、10（2分）】正确答案：（正确答案：1，3，6，8，11，13，16，19）已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用二分法查找90时，需 次查找成功，查47时，需 次查找成功，查100时，需 次才能确定不成功。【南京理工大学2000二、7（4.5分）】正确答案：（正确答案：2， 4， 3）n个结点的用于折半查找的判定树，表示查找失败的外部结点共有 个。【中南大学2003三、12（1分）】正确答案：（正确答案：n+1）设表长为1023的有序线性表，查找每个元素的概率相等，采用折半查找方法，查找成功的ASL是 。【北京交通大学2005二、5（2分）】正确答案：（正确答案：9）在一个按值有序排列的顺序表示中进行折半查找，其查找过程可以用一棵称之为“判断树”的二叉树来描述。若顺序表的长度为19，则对应的“判断树”的根结点的左孩子之值（元素在表中的位置）是 。【北京航空航天大学2006一、8（1分）】正确答案：（正确答案：5）三、判断题（总题数：10，分数：20.00）对一个堆，按二叉树层次进行遍历可以得到一个有序序列。（）【中国海洋大学2006二、14（1分）】正确错误丿以同一组数的不同序列来构造平衡二叉树，可能会得到不同的解。（）【北京邮电大学2006二、9（1分）】正确丿错误在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。（）【南京理工大学1997二、3（2分）】正确错误丿平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定是零。（）【中国科学技术大学1991一、6（2分）】正确丿错误完全二叉树肯定是平衡二叉树。（）【南京航空航天大学1996六、5（1分）】正确错误丿从平衡因子定义看，完全二叉树任一结点的平衡因子的绝对值确实是小于等于1。但是，平衡二叉树本质上是二叉排序树，完全二叉树不一定是二叉排序树。故不能说完全二叉树是平衡二叉树。一棵平衡二叉树中的任意两个叶子结点的层次差的绝对值不大于1。（）【北京邮电大学2006二、8（1分）】正确错误丿平衡二叉树是指任意结点的左右子树层次（高度）差的绝对值小于等于1。AVL树是一棵二叉树，该树上任一结点的平衡因子的绝对值不大于1。（）【中国海洋大学2007二、13（1分）】正确丿错误在一棵7阶B树中，一个结点中最多有6棵子树，最少有3棵子树。（）【南京理工大学2004二、9（1分）】正确错误丿7阶B树每个结点至多7棵子树，除根结点最少可以有2棵子树外，其余非终端结点最少有4