2015暨南大学考研数据结构真题

需要暨南大学考研数据结构历年真题+参考答案+复习资料，请加QQ:32673676515级师兄2015年全国硕士研究生统一入学考试自命题试题（B卷）********************************************************************************************学科、专业名称：计算机科学与技术、软件工程研究方向：计算机系统结构081201，计算机软件与理论081202，计算机应用技术081203，软件工程083500，计算机技术(专业学位)085211，软件工程(专业学位)085212考试科目名称及代码：数据结构830考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。一.单项选择题(每题2分，共30分)1．线性表采用链式存储时,其地址()。A．必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续与否均可以2．若有一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n,则第i个输出元素是（）。A.n-iB.n-i-1C.n-i+1D.不确定3.已知单链表上一结点的指针为p，则删除该结点后继的正确操作语句是（）。A.s=p-next;p=p-next;free(s);B．p=p-next;free(p);C.s=p-next;p-next=s-next;free(s);D．p=p-next;free(p-next);4.若使用邻接矩阵表示某有向图，则矩阵中非零元素的个数等于（）。A.图中顶点的数目B.图中边的数目C.图中边的数目的两倍D.无法确定5.下列哪种排序需要的附加存储开销最大()。A．快速排序B.堆排序C.归并排序D.插入排序6.下面哪一方法可以判断出一个有向图是否有环（即回路）（）。A．拓扑排序B.求最短路径C.求最小生成树D.广度优先遍历7.具有n个顶点的无向图至少应有（）条边才能确保是一个连通图.A．n-1B．nC．n+1D．2n8.对线性表进行折半查找时,要求线性表必须()。A.以顺序方式存储B.以顺序方式存储,且结点按关键字有序排序C.以链接方式存储D.以链接方式存储,且结点按关键字有序排序9．若使用二叉链表作为树的存储结构，在有n个结点的二叉链表中非空的链域的个数为()。A.n-1B.2n-1C.n+1D.2n+110．在内部排序中,排序时不稳定的有()。A.插入排序B.冒泡排序C.快速排序D.归并排序11.一个具有500个结点的完全二叉树具有一个孩子的结点个数最多为（）。A．1B．250C．0D．249考试科目：数据结构共5页，第1页12.从未排序序列中取出一个元素，并将其依次插入已排序序列的方法，称为（）。Ａ.希尔排序Ｂ.归并排序Ｃ.插入排序Ｄ.选择排序13.如果希望对二叉排序树遍历的结果是升序的，应采用（）遍历方法。A．先序B．中序C．后序D．层次14.队列操作的原则是（）A．先进先出B．后进先出C．只能进行插入D．只能进行删除15.在用邻接表表示有向图的情况下,假设n为图的顶点数目,e为图的边数目,建立图的算法的时间复杂度为()。A．O(n+e)B．O(n2)C．O(n×e)D．O(n3)二．填空题(每空2分，共20分)1．循环链表的主要优点是。2．根据数据元素之间关系的不同特性,基本逻辑结构分为、线性结构、树形结构和四种。3．对一棵完全二叉树中按照从上到下、从左到右的顺序从1开始顺序编号，则编号为11双亲结点的编号为，编号为10的结点的左孩子结点（若存在）的编号为。4．下面程序段的时间复杂度是。S=0;for(i=0;iN;i++)for(j=0;j2N+1;j++)S++;5．深度为h的满二叉树共有个结点。6．一棵m阶非空B-树，每个结点最多有棵子树，除根之外的所有非终端结点至少有棵子树。7．在单链表中，若要在指针p所指结点后插入指针s所指结点，则需要执行下列两条语句：。三．判断题（每题1分，共10分，正确的选t，错误的选f）1．数据元素是数据的基本单位。（）2．线性表中的每一个元素都有一个前驱和后继元素。（）3．当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（）4．带权无向图的最小生成树是唯一的。()5．设有序的关键字序列是（2，5，8，9，12，14，16，18，20，22，25），当用折半查找方法查找关键字22时，需经3次比较运算。（）6．一棵m阶B+树中每个结点最多有m个关键码，最少有2个关键码。()7．根据拓扑排序结果可以判断一个有向图中是否存在环路。（）8．图的深度优先搜索中可以采用栈来暂存刚访问过的顶点。（）9．已知一颗树的先序序列和后序序列，一定能构造出该树。（）考试科目：数据结构共5页，第2页10．存储图的邻接表中，邻接表的大小不但与图的顶点个数有关，而且与图的边数也有关。（）四.简答题（45分）1.简述下列算法的功能。（6分）typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;voidProcess(BiTreeT){IniStack(S);P=T;while(P||!StackEmpty(S)){if(P){push(&S,P);P=P-lchild;}else{pop(&S,P);printf(P-data);P=P-rchild;}}}2.假设表中关键字序列为（7,6,9,10，14,8），将关键字依次插入一棵初始为空的二叉排序树。画出二叉排序树的生成过程。（10分）3.关键字序列T=(63，55，48，37，20，90，84，32），对其从小到大排序，以第一个关键字为枢轴（支点），写出快速排序具体实现过程（10分）。4.一个有六个顶点{v1,v2,v3,v4,v5,v6}的网的邻接矩阵如图1所示，解答下列问题：（1）画出该网（2分）（2）能否写出一种拓扑排序序列，若可以，写出一种拓扑排序序列（2分）（3）求出从顶点v1到其他各顶点之间的最短路径，并写出计算过程。（8）∞∞∞∞∞∞20∞4∞∞∞15∞∞∞∞∞∞∞∞∞154∞10∞∞∞10∞3010∞∞∞G.arcs=图1.考试科目：数据结构共5页，第3页5.设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成，它们在电文中出现的频度分别为{0.34,0.12,0.10,0.08,0.13,0.20,0.03},如何为这7个字母设计二进制前缀编码使得电文总长最短，写出编码过程。（7分）五．算法填空，（每空2分,共20分）1.以下算法功能是:插入元素e到队列Q中,完成算法的空格部分。typedefstructQnode{QElemTypedata;structQnode*next;}Qnode,*QueuePtr;typedefstruct{QueuePtrfront;//队头QueuePtrrear;//队尾}LinkQueue;statusEnQueue(LinkQueue&Q,QElemTypee){P=(QueuePtr)malloc(sizeof(Qnode));if(①)exit(OVERFLOW);P-data=②P-next=③④=P;Q.rear=⑤;ReturnOK;}2.以下程序为图的深度优先遍历算法，完成算法的空格部分。Booleanvisited[Max];//访问标志数组Status(*VisitFunc)(intv);//访问函数变量voidDFStraverse(GraphG,Status(*visit)(intv)){vistFunc=visit;for(v=0;vG.vexnum;++v)visited[v]=False;for(v=0;⑥；++v)if(⑦)DFS(G,v);}voidDFS(GraphG,intv){visited[v]=⑧;VisitFunc(V);for(w=FirstAdjvex(G,v);⑨;w=NextAdjVex(G,v,w))if(!visited[w])⑩;}考试科目：数据结构共5页，第4页六．编写算法（25分）1．已知线性表中的元素按值递增有序排列，并以带头结点的单链表作存储结构。试编写算法，删除表中所有值大于x且小于y的元素（若表中存在这样的元素）,同时释放被删除结点空间。（10分）2．设计一个算法，求不带权无向连通图G中距离顶点v的最远顶点。（15分）考试科目：数据结构共5页，第5页