北京邮电大学数据结构模拟题及答案

考研专业课2012《高分学习资料》    北京邮电大学 《数据结构》          文都教育 北京总部考研专业课教研中心 北京总部售后电话[phone]《考研专业课高分资料》之模拟试题2/11专业课研发中心目录 第五模块模拟试题.........................................................................................................................3 北京邮电大学数据结构模拟试题（一）...............................................................................3 北京邮电大学数据结构模拟试题（一）参考答案或答题纸...............................................6 北京邮电大学数据结构模拟试题（二）...............................................................................8 北京邮电大学数据结构模拟试题（二）参考答案或答题纸.............................................11 《考研专业课高分资料》之模拟试题3/11专业课研发中心第五模块模拟试题北京邮电大学数据结构模拟试题（一）所有答案必须做在答案题纸上，做在试题纸上无效！一、单选题（每小题2分，共8分）1、在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为()。AnBn/2C(n+1)/2D(n-1)/22、在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行()。As→link=p→link;p→link=s;Bp→link=s;s→link=q;Cp→link=s→link;s→link=p;Dq→link=s;s→link=p;3、栈的插入和删除操作在（）进行。A栈顶B栈底C任意位置D指定位置4、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A24B71C48D53二、填空题（每空1分，共32分）1、数据的逻辑结构被分为__________、___________、________和________四种。2、一种抽象数据类型包括______________和_____________两个部分。3、在下面的数组a中链接存储着一个线性表，表头指针为a[o].next，则该线性表为_________________________________________________。a012345678datanext4、在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为________________和____________________。5、用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的___________，该循环队列的最大长度为__________。6、当堆栈采用顺序存储结构时，栈顶元素的值可用———————表示；当堆栈采用链接存储结构时，栈顶元素的值可用_______________表示。7、一棵高度为5的二叉树中最少含有_________个结点，最多含有________个结点；一棵高度为5的理想平衡树中，最少含有_________个结点，最多含有_________个结点。8、在图的邻接表中，每个结点被称为____________，通常它包含三个域：一是_____________；二是___________；三是_____________。9、在一个索引文件的索引表中，每个索引项包含对应记录的_________和___________两项数据。得分评卷人6056423874254376201姓名：准考证号：学院：专业：《考研专业课高分资料》之模拟试题4/11专业课研发中心10、假定一棵树的广义表表示为A（B（C，D（E，F，G），H（I，J））），则树中所含的结点数为_________个，树的深度为_________,树的度为________,结点H的双亲结点为________,孩子结点为_______________。11、在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_________,整个堆排序过程的时间复杂度为________________。12、在对m阶的B_树插入元素的过程中，每向一个结点插入一个索引项（叶子结点中的索引项为关键字和空指针）后，若该结点的索引项数等于______个，则必须把它分裂为_______个结点。三、运算题（每小题6分，共24分）1、已知一组记录的排序码为（46，79，56，38，40，80,95，24），写出对其进行快速排序的每一次划分结果。2、一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散列函数为H（key）=key%13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。3、已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ，中序遍历的结果是EBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。4、已知一个图的顶点集V各边集G如下：V={0，1，2，3，4，5，6，7，8，9}；E={（0，1），（0，4），（1，2），（1，7），（2，8），（3，4），（3，8），（5，6），（5，8），（5，9），（6，7），（7，8），（8，9）}当它用邻接矩阵表示和邻接表表示时，分别写出从顶点V0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列。假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。四、阅读算法，回答问题（每小题8分，共16分）1、假定从键盘上输入一批整数，依次为：786345309134–1，请写出输出结果。#includeiostream.h#includestdlib.hconsstintstackmaxsize=30;typedefintelemtype;structstack{elemtypestack[stackmaxsize];inttop;};#include“stack.h”Voidmain(){stacka;initstack(a);intx;得分评卷人图深度优先序列广度优先序列邻接矩阵表示时邻接表表示时得分评卷人《考研专业课高分资料》之模拟试题5/11专业课研发中心cinx;while(x!=-1){push(a,x);cinx;}while(!stackempty(a))coutpop(a)””;coutend1;}该算法的输出结果为：__________________________________________________________.2、阅读以下二叉树操作算法，指出该算法的功能。TemplatecalsstypevoidBinTreeType：：unknown(BinTreeNodeType*t){BinTreeNodeType*p=t,*temp;if(p!=NULL){temp=p→leftchild;p→leftchild=p→rightchild;p→rightchild=temp;unknown(p→leftchild);undnown(p→rightchild);}}该算法的功能是：________________________________五、算法填空，在画有横线的地方填写合适的内容（10分）对顺序存储的有序表进行二分查找的递归算法。intBinsch(ElemTypeA[],intlow,inthigh,KeyTypeK){if(low=high){intmid=○1if(K==A[mid].key)returnmid;elseif(KA[mid].key)return○2elsereturn○3}elsereturn○4六、编写算法（10分）编写算法，将一个结点类型为Lnode的单链表按逆序链接，即若原单链表中存储元素的次序为a1，……an-1，an，则逆序链接后变为,an，an-1，……a1。Voidcontrary(Lnode*&HL)得分评卷人得分评卷人《考研专业课高分资料》之模拟试题6/11专业课研发中心北京邮电大学数据结构模拟试题（一）参考答案所有答案必须做在答案题纸上，做在试题纸上无效！一、单选题（每小题2分，共8分）题号1234答案CDAB二、填空题（每空1分，共32分）1：集合、线性、树、图；2：数据描述、操作声名；3：（38，56，25，60，42，74）；4：HL→next=NULL；HL=HL→next；5：前一个位置；n-1；6：S.stack[S.top];HS→data;7：5318：边结点、邻接点域、权域、链域；9：索引值域、开始位置域；10：10、3、3、B、I和J；11：O（log2n）、O(nlog2n);12：m、m-1三、运算题（每小题6分，共24分）1、划分次序划分结果第一次[382440]46[56809579]第二次24[3840]46[56809579]第三次24384046[56809579]第四次2438404656[809579]第五次243840465679[8095]第六次24384046567980952、78150357452031233612查找成功的平均查找长度：ASLSUCC=14/10=1.43、此二叉树的后序遍历结果是：EDCBIHJGFA4、四、阅读算法，回答问题（每小题8分，共16分）1、该算法的输入结果是：349130456378图深度优先序列广度优先序列邻接矩阵表示时0，1，2，8，3，4，5，6，7，90，1，4，2，7，3，8，6，5，9邻接表表示时0，4，3，8，9，5，6，7，1，20，4，1，3，7，2，8，6，9，5姓名：准考证号：学院：专业：姓名：准考证号：学院：专业：姓名：准考证号：学院：专业：0123456789101112《考研专业课高分资料》之模拟试题7/11专业课研发中心2、该算法的功能是：交换二叉树的左右子树的递归算法。五、算法填空，在画有横线的地方填写合适的内容（10分）1、○1是：（low+high）/2;○2是：Binsch(A,low,mid–1,K);○3是：Binsch(A,mid+1,high,K);○4是：-1；六、编写算法（10分）根据编程情况，酌情给分。{Lnode*P=HL;HL=NULL;While(p!=null){Lnode*q=p;P=p→next;q→next=HL;HL=q;《考研专业课高分资料》之模拟试题8/11专业课研发中心北京邮电大学数据结构模拟试题（二）所有答案必须做在答案题纸上，做在试题纸上无效！一、单选题（每空2分，共10分）1、队列的删除操作是在（）进行。A．队首B．队尾C．队前D．对后2、当利用大小为N的数组顺序存储一个栈时，假定用top==N表示栈空，则退栈时，用（）语句修改top指针。A．top++;B．top=0;C．top--;D．top=N;3、由权值分别为3,6,7,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。A．51B．23C．53D．744、在一棵二叉树中，第4层上的结点数最多为（）。A．31B．8C．15D．165、向堆中插入一个元素的时间复杂度为（）。A．O(log2n)B．O(n)C．O(1)D．16O(nlog2n)二、填空题（每空1分，共20分）1、数据的存储结构被分为____________、___________、____________和___________