《数据结构》复习题及参考答案

PAGE《数据结构》复习题及参考答案数据结构包括数据的逻辑结构数据的存储结构和数据的运算这三个方面的内容。数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。数据的存储结构可用四种基本的存储方法表示，它们分别是顺序链式索引散列。数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。非线性结构是数据元素之间存在一种：（B）A、一对多关系B、多对多关系C、多对一关系D、一对一关系数据结构中，与所使用的计算机无关的是数据的（C）结构；A、存储B、物理C、逻辑D、物理和存储算法分析的目的是（C）A、找出数据结构的合理性B、研究算法中的输入和输出的关系C、分析算法的效率以求改进D、分析算法的易懂性和文档性计算机算法指的是（C）A、计算方法B、排序方法C、解决问题的有限运算序列D、调度方法计算机算法必须具备输入、输出和（B）等5个特性。A、可行性、可移植性和可扩充性B、可行性、确定性和有穷性C、确定性、有穷性和稳定性D、易读性、稳定性和安全性数据结构和数据类型两个概念之间有区别吗？简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。分析下面各程序段的时间复杂度：for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;~0020O（m*n）`002101A分析下面各程序段的时间复杂度：s=0;fori=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;~0021O（n2）`002201A2分析下面各程序段的时间复杂度：x=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)x++;~0022因为x++共执行了n-1+n-2+……＋1=n(n-1)/2，所以执行时间为O（n2）`002301A2分析下面各程序段的时间复杂度：i=1;while(i<=n)i=i*3;~0023O（log3n）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。~0025表中一半表长和该元素在表中的位置`002603C1判定一个栈ST（最多元素为m0）为空的条件是BＡ、ST->top<>0Ｂ、ST->top=0Ｃ、ST->top<>m0Ｄ、ST->top=m0`002702B2向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1个元素。`002802B2向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i个元素。`002902B1在顺序表中访问任意一结点的时间复杂度均为，因此，顺序表也称为的数据结构。~0029O(1)随机存取`003102B1在单链表中，除了首元结点外，任一结点的存储位置由指示。~0031其直接前驱结点的链域的值`003202B2在n个结点的单链表中要删除已知结点*p，需找到它的，其时间复杂度为o(n)。~0032前驱结点的地址O（n）线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（x）`003702D1顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（X）`004502C1在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）在第i个结点后插入一个新结点（1≤i≤n）删除第i个结点（1≤i≤n）将n个结点从小到大排序`010609F2从循环单链表中查找出最大值.~0106intsearchmax(linklistl){intmax;int*p;p=l;max=p->data;p=p->next;while(p->next<>nil){if(max<p->data)max=p->data;p=p->next;}returnmax;}`010709F2从循环单链表中查找出最小值.~0107intsearchmin(linklistl){intmin;int*p;p=l;min=p->data;p=p->next;while(p->next<>nil){if(min>p->data)min=p->data;p=p->next;}returnmin;}`011203D1栈和队列都是线性表.()~0112正确`011603B1栈的两个重要应用是___________和_________.~0116在编译系统运行计算机语言程序的过程中,利用栈进行语法检查,实现递归调用.`011703A2栈和队列都是运算受到限制的特殊的线性表,栈和队列有何不同?`011903C1用数组A存放循环队列的元素值,若其头指针为front,尾指针为rear,则循环队列中当前元素个数为(A).A、(rear-front+m)modm B、(rear-front+1)modmC、(rear-front-1+m)modm D、(rear-front)modm~0119A`012003A2设循环队列Q头指针为front,尾指针为rear,队列的最大容量为M,写出循环队列队满和队空的判定条件.~0120队满条件:(q.front+1)modm=q.rear队空条件:q.front=q.rear`012203F2给出循环队列的入队和出队算法.~0122intENQUEUE(sequeue*sq;datatypex){if(sq->front==(sq->rear+1)%maxsize){printf("queueisfull");returnNULL;}else{sq->rear=(sq->rear+1)%maxsize;sq->data[sq->rear]=x;return(TRUE);}}datatypeDEQUEUE(sequeue*sq){if(EMPTY(sq)){printf("queueisempty");}else{sq->front=(sq->front+1)%maxsize;return(sq->data[sq->front];}}`012503F2设计算法判断一个算术表达式的圆括号是否正确配对,(提示:对表达式进行扫描,凡遇'('就进栈,遇')'就退掉栈顶的')',表达式被扫描完毕,栈就为空.)~0125booleanpair(b){stacks;s.top=0;i=1;ch=b[i];while(ch!="@"){if((ch='(')||(ch=')'))switch{'(':push(s,ch);break;')':ifempty(s){pair=false;return;}elsepop(s)}i=i+1;ch=b[i];}ifempty(s)pair=true;elsepair=false;}`012703B2程序段的输出结果是_________（队列中的元素类型QElemType为char）。voidmain(){QueueQ;InitQueue(Q);Charx=’e’;y=’c’;EnQueue(Q,’h’);EnQueue(Q,’r’);EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,’a’);while(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);};Printf(x);}~0127stack`012909E2什么是二叉排序树,按如下关键字的插入次序生成一棵二叉排序树,试画出此二叉排序树25,48,36,16,45,20,18,72~0129二叉排序树或者是一棵空树,或者是具有如下性质的二叉树:(1)若它的左子树不空,则左子树上所有结点的值均小于根结点的值;(2)若它的右子树不空,则右子树上所有结点的值均大于根结点的值;(3)左右子树又各是一棵二义排序树.2516482036721845`013503E1设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有①front=11，rear=19;②front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？~0135用队列长度计算公式：(N＋r－f)%N①L=（40＋19－11）%40=8②L=（40＋11－19）%40=32`013803F2设两个栈共享向量空间V(1:m),它们的栈底分别设在向量的两端,且进栈的每个元素只占一个分量,试写出这两个栈公用的栈操作算法pushi(i,x),popi(i),其中i为0或1,用以指示栈号~0138pushi(i,x){ifs.top0=s.top1-1printf("orerflow");ifi=0{s.top=s.top1+1;s.elem[s.ti\op]=x;}else{s.top1=s.top0-1;s.elem[s.top]=x;}}popi(i){ifi=0{ifs.top0=0printf("underflow");pop=s.elem[s.top0]s.top1=s.top1-1;}elseif{s.top=m+1printf("underflow");pop=s.elem[s.top1];s.top1=s.top1+1;}}`014003F1设HS为一个链栈的栈顶指针,试写出退栈的算法,(回收被删除的结点)~0140linkstack*POPSTACK(top,datap)linkstack*top;datatype*datap;{linkstack*pif(top==NULL){printf("underflow");returnNULL)}else{*data=top->data;p=top;top=top->next;free(p);returntop;}}`014303E3设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序.~0143至少有14种。①全进之后再出情况，只有1种：4，3，2，1②进3个之后再出的情况，有3种，3,4,2,13,2,4,13,2,1,4③进2个之后再出的情况，有5种，2,4,3,12,3,4,12,1,3,42,1,4,32,1,3,4④进1个之后再出的情况，有5种，1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,3`014703E2写出栈的顺序存储结构(即顺序栈)的类型定义.~0147顺序栈的结构:typedefintdatatype;#definemaxsize64typedefstruct{datatypedata[maxsize];inttop}seqstack;seqstack*s;`014803A1写出队列的顺序存储结构(顺序队列)的类型定义.~0148顺序队列的结构:typedefstruct{datatypedata[maxsize]intfrontrear;}sequeue;sequeue*sq;`015003B2带有头结点的链队列q,队头指针front,队尾指针rear,则置空队的算法描述为:q->front=malloc(sizeof(linklist));________________;________________;~0150q->front->next=NULLq->rear=q->front;`015306C2已知完全二叉树有２８个结点，则整个二叉树有()个度为１的结点。A、0;B、1;C、2;D、不确定~0153B`016506E3已知一棵二叉树中序和后序序列为分别为:BDCEAFHG和DECBHGFA画出这棵二叉树`016806D1哈夫曼树的带权路径长度WPL等于叶子结点的权值之和。()~0168对`016906E3已知二叉树的先序、中序、后序序列分别如下,但其中有一些已模糊不清,构造出该二叉树.先序:_23_5_78中序:3_41_789后序:_42__651~0169`017206B3在有N(N>0)个结点的二叉链表中，空链域的个数是：_____。~0172N+1以二叉链表作存贮结构，试写出中序遍历二叉树的算法。~0178INORDER()bitree*t;{if(t){INORDER(t->lchild);printf("|t%c|n",t->data);INORDER(t->rchild);}}`018106B2具有N个结点的完全二叉树的深度为_________。~0181└log2n+1┘+1或┌log2(n+1)┐`018406A2何谓哈夫曼树?何谓完全二叉树,它具有哪些特点?~0184哈夫曼树：带权路径WPL最小的二叉树称最优二叉树或哈夫曼树。完全二叉树：若一棵二叉树至多只有最下面的两层上结点的度数可以小于２，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树为完全二叉树。特点：１只有最下面两层有叶子。２如果一个结点无左子树，那它一定是叶子。３完全二叉树中任一个结点的左子树深度为Ｔ，其右子树深度为Ｔ或Ｔ－１。`019006E3已知二叉树的中序和先序序列分别为:中序序列:DEBAFCHG先序序列:ABDECFGH试构造该二叉树~0190`019106A3度为２的树与二叉树的区别。~0191度为２的树每个结点如度为１子树无左右之分；而二叉树则有。`019206F2试编写算法判断两棵二叉树是否等价,称二叉树T1和T2的根结点的值相同,并且T1的左子树与T2的左子树是等价的，T1的右子树和T2的右子树是等价的.~0192EQUBINTREE(t1,t2)bintree*t1,*t2;{if(t1=NULL&&t1=NULL)returnTRUEelse{if(t1->data=t2->data&&ERUBINTREE(t1->lchild,t2->lchild)&&ERUBINTREE(t1->rchild,t2->rchild))returnTRUE;}elsereturnFALSE;}`019806E2已知一棵度为m的树中有N1个度为1的结点,N2个度为2的结点,问该树中有多少片叶子.~0198N0=1+(i-1)Ni(i=1tom)`020006E3一个深度为L的满K叉树有如下性质:第L层上的结点是叶子结点,其余各层上每个结点都有K棵非空子树,如果按层次顺序从1开始对全部结点编号,问:(1)各层的结点的数目是多少?(2)编号为n的结点的双亲结点(若存在)编号是多少?(3)编号为n的结点的第i个孩子(若存在)编号是多少?(4)编号为n的结点有右兄弟的条件是什么?其右兄弟的编号是多少?~0200K^(I-1)(1<=I<=k)2.(n+k-2)/k3.kn+I-k+14.nki+1(I=0,1,……);n+1`020807B1一个具有n个顶点的连通有向图至多有_________条弧.~0208n(n-1)`020907B1一个具有n个顶点的连通有向图至少有________条弧.~0209n+1`028106E2把如图所示的树转化成二叉树。~0281注意全部兄弟之间都要连线（包括度为2的兄弟）,并注意原有连线结点一律归入左子树，新添连线结点一律归入右子树。ABECKFHDLGIMJ`028206E2画出和下列二叉树相应的森林。~0282注意根右边的子树肯定是森林，而孩子结点的右子树均为兄弟。`029103C1判定一个队列QU（最多元素为m0）为满队列的条件是（）Ａ、QU->rear－QU->front==m0Ｂ、QU->rear－QU->front－1==m0Ｃ、QU->front==QU->rearＤ、QU->front==QU->rear+1~0291A`032108E2用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么?如果要求时间复杂度更小,你采用什么方法？此方法的时间复杂度是多少?~0321查找某个元素的时间复杂度下限，如果理解为最短查找时间，则当关键字值与表头元素相同时，比较1次即可。要想降低时间复杂度，可以改用Hash查找法。此方法对表内每个元素的比较次数都是O（1）。`035607C1用邻接表表示图进行广度优先遍历时，通常是采用(B)来实现算法的。A、栈B、队列C、树D、图`035707C1用邻接表表示图进行深度优先遍历时，通常是采用(A)来实现算法的。A、栈B、队列C、树D、图`035807C2A．0243156B.0136542C.04231650361542A．0243156B.0136542C.04231650361542建议：0134256`035907C2已知图的邻接矩阵,根据算法，则从顶点0出发，按深度优先遍历的结点序列是(C)A、0243156B、0135642C、0423165D、0134256`036007C2已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是()A、0243651B、0136425C、0423156D、0134256（建议：0123456）~0360B`036107C2已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是()A、0243165B、0135642C、0123465D、0123456~0361C`036207C2已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是()A．0132B.A．0132B.0231C.0321D.0123~0362D`036307C2已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是()A、0321BA、0321B、0123C、0132D、0312~0363A`036407C1深度优先遍历类似于二叉树的(A)A、先序遍历B、中序遍历C、后序遍历D、层次遍历`036507C1广度优先遍历类似于二叉树的(D)A、先序遍历B、中序遍历C、后序遍历D、层次遍历`037007B1n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为O(n2)。n个顶点e条边的图，若采用邻接表存储，则空间复杂度为O(n+e)。`037207B1设有一稀疏图G，则G采用邻接表存储较省空间。设有一稠密图G，则G采用邻接矩阵存储较省空间。图的逆邻接表存储结构只适用于有向图。已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的方法是将邻接矩阵的第i行全部置0。图的深度优先遍历序列不是惟一的。n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为O(n2)；若采用邻接表存储时，该算法的时间复杂度为O(n+e)。n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为O(n2)；若采用邻接表存储，该算法的时间复杂度为O(n+e)。图的BFS生成树的树高比DFS生成树的树高小或相等。用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为O(n2)；用克鲁斯卡尔(Kruskal)算法的时间复杂度是O(elog2e)。若要求一个稀疏图G的最小生成树，最好用克鲁斯卡尔(Kruskal)算法来求解。若要求一个稠密图G的最小生成树，最好用普里姆(Prim)算法来求解。拓扑排序算法是通过重复选择具有0个前驱顶点的过程来完成的。`038507E3已知如图所示的有向图，请给出该图的:每个顶点的入/出度；邻接矩阵；邻接表；逆邻接表。顶点123456入度出度~0385

`038607E3请对下图的无向带权图：写出它的邻接矩阵;写出它的邻接表。~0386(1)a→b4→c3b→a4→c5→d5→e9^c→a3→b5→d5→h5^d→b5→c5→e7→f6→g5→h4^e→b9→d7→f3^f→d6→e3→g2^g→d5→f2→h6^h→c5→d4→g6^`038707E3已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

`038907E3给定下列网G:(1)试着找出网G的最小生成树，画出其逻辑结构图；(2)用两种不同的表示法画出网G的存储结构图；(3)用C语言（或其他算法语言）定义其中一种表示法（存储结构）的数据类型。AB———————AB———————CE————FG————D解：(1)最小生成树可直接画出，如右图所示。(2)可用邻接矩阵和邻接表来描述：a→b12→e4^b→a12→c20→e8→f9^c→b20→d15→g12^d→c15→g10^e→a4→b8→f6^f→b9→e6^g→c12→d10邻接表为：(3)注：用两个数组分别存储顶点表和邻接矩阵#defineINFINITYINT_MAX//最大值∞#defineMAX_VERTEX_NUM20//假设的最大顶点数（可取为7）Typedefenum{DG,DN,AG,AN}GraphKind;//有向/无向图，有向/无向网TypedefstructArcCell{//弧（边）结点的定义VRTypeadj;//顶点间关系，无权图取1或0；有权图取权值类型InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];Typedefstruct{//图的定义VertexTypevexs[MAX_VERTEX_NUM];//顶点表，用一维向量即可AdjMatrixarcs;//邻接矩阵IntVernum,arcnum;//顶点总数（7），弧（边）总数（9）GraphKindkind;//图的种类标志}Mgraph;`039007F3编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。~0390解：StatusBuild_AdjList(ALGraph&G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表{InitALGraph(G);scanf("%d",&v);if(v<0)returnERROR;//顶点数不能为负G.vexnum=v;scanf("%d",&a);if(a<0)returnERROR;//边数不能为负G.arcnum=a;for(m=0;m<v;m++)G.vertices[m].data=getchar();//输入各顶点的符号for(m=1;m<=a;m++){t=getchar();h=getchar();//t为弧尾,h为弧头if((i=LocateVex(G,t))<0)returnERROR;if((j=LocateVex(G,h))<0)returnERROR;//顶点未找到p=(ArcNode*)malloc(sizeof(ArcNode));if(!G.vertices.[i].firstarc)G.vertices[i].firstarc=p;else{for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc);q->nextarc=p;}p->adjvex=j;p->nextarc=NULL;}//whilereturnOK;}//Build_AdjList`039107F3试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w)，即删除一条边的操作。（如果要删除所有从第i个顶点出发的边呢？提示：将邻接矩阵的第i行全部置0）~0391解：//本题中的图G均为有向无权图。StatusDelete_Arc(MGraph&G,charv,charw)//在邻接矩阵表示的图G上删除边(v,w){if((i=LocateVex(G,v))<0)returnERROR;if((j=LocateVex(G,w))<0)returnERROR;if(G.arcs[i][j].adj){G.arcs[i][j].adj=0;G.arcnum--;}returnOK;}//Delete_Arc`039207F3试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。~0392intvisited[MAXSIZE];//指示顶点是否在当前路径上intlevel＝1;//递归进行的层数intexist_path_DFS(ALGraphG,inti,intj)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0{if(i==j)return1;//i就是jelse{visited[i]=1;for(p=G.vertices[i].firstarc;p;p=p->nextarc，level--){level++;k=p->adjvex;if(!visited[k]&&exist_path(k,j))return1;//i下游的顶点到j有路径}//for}//els