计算机考研数据结构试卷十一(练习题含答案)

共25套适用于计算机考研数据结构系统练习（PS：其他正在整理，敬请期待）数据结构试卷11一、填空:1.设需要对5个不同的记录关键字进行排序，则至少需要比较_____________次，至多需要比较_____________次。2.设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较_________次。3.设在长度为20的有序表中进行二分查找，则比较一次查找成功的结点数有_________个，比较两次查找成功有结点数有_________个。4.数据结构从逻辑上划分为三种基本类型：___________、__________和___________。5.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。6.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___________。7.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。8.在快速排序、堆排序、归并排序中，_________排序是稳定的。9.在有n个叶子结点的哈夫曼树中，总结点数是_______。10.一棵树T采用二叉链表存储，如果树T中某结点为叶子结点，则在二叉链表BT中所对应的结点一定_______。二、选择题：1.队列的特点是【】。A先进后出B先进先出C任意位置进出D前面都不正确2.有n个记录的文件，如关键字位数为d，基数为r，则基数排序共要进行【】遍分配与收集。AnBdCrDn-d3.在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序【】。A都不相同B完全相同C先序和中序相同，而与后序不同D中序和后序相同，而与先序不同4.设有198个初始归并段，如采用K-路平衡归并三遍完成排序，则K值最大为【】。A12B13C14D155.下面关于广义表的叙述中，不正确的是【】。A广义表可以是一个多层次的结构B广义表至少有一个元素C广义表可以被其他广义表所共享D广义表可以是一个递归表6.设二叉树根结点的层次为0，一棵深度（高度）为k的满二叉树和同样深度完全二叉树各有f个结点和c个结点，下列关系式不正确的是【】。Af=cBcfCf=2k+1-aDcsk-17.从L=((apple,pear),(orange,banana))中，取出banana元素的表达式为【】。Ahead(tail(L))Bhead(head(tail(L)))Ctail(head(tail(L)))Dhead(tail(head(tail(L))))8.下列文件的物理结构中，不利于文件长度动态增长的文件物理结构是【】。A顺序结构B链接结构C索引结构DHash结构9.在数据结构中，数据元素可由【】。A实体B域C数据项D字段10.对于有n个顶点的有向图，由弗洛伊德（FloyD算法求每一对顶之间的最短路径的时间复杂度是【】。AO(1)BO(n)CO(n)DO(n3)三、计算与算法应用题：1.已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};按照普里姆算法从顶点1出发得到最小生成树，试写出在最小生成树中依次得到的各条边。2.一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处的内容，并画出该二叉树。先序序列：BFICEHG中序序列：DKFIAEJC后序序列：KFBHJGA四、阅读下列算法，分析它的作用：1.intAA(LNode*HL,ElemTypex){intn=0;LNode*p=HL;while(p!=NULL){if(p-data==x)n++;p=p-next;}returnn;}对于结点类型为LNode的单链表，以上算法的功能为：2.intAA(LNode*HL,ElemTypex){intn=0;LNode*p=HL;while(p!=NULL){if(p-data==x)n++;p=p-next;}returnn;}对于结点类型为LNode的单链表，以上算法的功能为：五、算法设计题：1.编写复制一棵二叉树的非递归算法。2.假设二叉树中每个结点所含数据元素均为单字母，以二叉链表为存储结构，试编写算法按如下图所示的树状显示二叉树。11.评卷人12.得分答案（PS:后15套较难，有不会的可以@我）一、填空题1.4，102.n3.1，24.线性结构，树型结构，图型结构5.n(n-1)/2n(n-1)6.增加17.O(log2n)O(nlog2n)8.归并9.n-110.左右子树空二、单项选择题1---5BBBCB6---10BDACD三、计算与算法应用题1.普里姆算法从顶点1出发得到最小生成树为：(1,2)3,(1,3)5,(1,4)8,(4,6)4,(2,5)10,(4,7)202.在先序序列空格中依次填ADKJ，中序中依次填BHG，后序中依次填DIEC。四、阅读下列算法，分析它的作用1.统计单链表中结点的值等于给定值x的结点数。2.对数组A中的n个元素进行排序，称为起泡算法。五、算法设计题：1.将算法实现函数声明为二叉树类的友元函数，可采用层次遍历的方式进行复制，将已复制的结点进入一个队列中即可。具体算法实现如下：//文件路径名:exam5\alg.htemplateclassElemTypevoidCopyBitree(BinaryTreeElemType*fromBtPtr,BinaryTreeElemType*&toBtPtr)//操作结果:复制二叉树fromBt到toBt的非递归算法{if(toBtPtr!=NULL)deletetoBtPtr;//释放toBtPtrif(fromBtPtr-Empty()){//空二叉树toBtPtr=NULL;//空二叉树}else{//非空二叉树LinkQueueBinTreeNodeElemType*fromQ,toQ;//队列BinTreeNodeElemType*fromPtr,*toPtr,*fromRoot,*toRoot;13.14.fromRoot=fromBtPtr-GetRoot();//取出fromBtPtr的根toRoot=newBinTreeNodeElemType(fromRoot-data);//复制根结点fromQ.InQueue(fromRoot);toQ.InQueue(toRoot);//入队while(!fromQ.Empty()){//fromQ非空fromQ.OutQueue(fromPtr);//出队toQ.OutQueue(toPtr);//出队if(fromPtr-leftChild!=NULL){//左子树非空toPtr-leftChild=newBinTreeNodeElemType(fromPtr-leftChild-data);//复制fromPtr左孩子fromQ.InQueue(fromPtr-leftChild);toQ.InQueue(toPtr-leftChild);//入队}if(fromPtr-rightChild!=NULL){//右子树非空toPtr-rightChild=newBinTreeNodeElemType(fromPtr-rightChild-data);//复制fromPtr左孩子fromQ.InQueue(fromPtr-rightChild);toQ.InQueue(toPtr-rightChild);//入队}}toBtPtr=newBinaryTreeElemType(toRoot);//生成toBtPtr}}2.从上图来看，二叉树的第一层显示在第一列，第二层显示在第二列，第三层显示在第三列；每行显示一个结点，从上至下是先显示右子树，再显示根，最后最左子树，也就是以先遍历右子树，最后遍历左子树的中序遍历次序显示各结点。具体算法实现如下：//文件路径名:exam1\alg.hssElemTypevoidDisplayHelp(BinTreeNodeElemType*r,intlevel)//操作结果：按树状形式显示以r为根的二叉树，level为层次数，可设根结点的层次数为1{if(r!=NULL){//空树不显式，只显式非空树DisplayHelpElemType(r-rightChild,level+1);//显示右子树coutendl;//显示新行for(inti=0;ilevel-1;i++)cout;//确保在第level列显示结点coutr-data;//显示结点DisplayHelpElemType(r-leftChild,level+1);//显示左子树}}templateclassElemTypevoidDisplay(constBinaryTreeElemType&bt)//操作结果：树状形式显示二叉树{DisplayHelpElemType(bt.GetRoot(),1);//树状显示以bt.GetRoot()为根的二叉树coutendl;//换行}