《数据结构》期末复习题及参考答案 - 第7章 图【HSH2013级】给学生

1《数据结构》期末复习题及参考答案-第7章图一、选择题1、以下数据结构中，哪种具有非线性结构？A．栈B．队列C．双向链表D．十字链表2、下面关于图的存储的叙述中正确的是（）。A.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。B.用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关。C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。D.用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关3、在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的（）A.先根遍历B.中根遍历C.后根遍历D.按层次遍历4、图的广度优先遍历算法类似于树的（）。A.中根遍历B.先根遍历C.后根遍历D.按层次遍历5、设无向图的顶点个数为n，则该图最多有（）条边。A．n-1B．n(n-1)/2C．n(n+1)/2D．06、设有n个结点的无向图，该图至少应有()条边才能确保是一个连通图。A．n-1B．nC．n+1D．nlogn；7、一个含有n个顶点的非连通图，则（）：A．它的边一定不大于n-1B．它的边一定不大于nC．它的边一定小于n-1D．它的边一定大于08、要连通具有n个顶点的有向图，至少需要（）条边。A．n-lB．nC．n+lD．2n9、下列说法不正确的是（）。A．图的遍历是从给定的源点出发每一个顶点仅被访问一次B．遍历的基本算法有两种：深度遍历和广度遍历C．图的深度遍历不适用于有向图D．图的深度遍历是一个递归过程10、无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。A．a,b,e,c,d,fB．a,c,f,e,b,dC．a,e,b,c,f,dD．a,e,d,f,c,b11、若一个连通图有n个顶点,则它的生成树有（）条边。A.nB.n-1C.n+1D.n(n-1)/22二、填空题1、邻接多重表适于表示稀疏无向图，邻接表、逆邻接表和十字链表适于表示稀疏有向图。2、设有向图的顶点个数为n，则该图最多有n(n-1)条弧。3、右图中顶点D的出度是3。4、8层完全二叉树至少有_128(第七层满，加第八层１个)_个结点，拥有100个结点的完全二叉树的最大层数为__7__。5、求图的最小生成树有两种算法：_普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。其中，_克鲁斯卡尔____算法适合于求_边稀疏___的稀疏图的最小生成树。普里姆算法适用于求边稠密的网的最小生成树。6、对于含n个顶点e条边的无向连通图，利用普里姆算法生成最小代价生成树其时间复杂度为__O(n2）_，利用克鲁斯卡尔算法生成最小代价生成树其时间复杂度为_O(eloge)__。6、在无向图的深度优先遍历算法中，DFS（从某个顶点出发深度优先遍历图的算法）被调用了几次就说明该图有几个联通分量。7、一个有n个结点的图，最少有1个连通分量，最多有n个连通分量。8、判断一个无向图是一棵树的条件是_有n个顶点，n-1条边的无向连通图。9、有向图G的强连通分量是指__有向图的极大强连通子图____。10、右图中的强连通分量的个数为3个。ACBDEF311、一个连通图的__生成树____是一个极小连通子图。12、若用n表示图中顶点数目，则有___n(n-1)/2___条边的无向图成为完全图。13、已知一无向图G=（V，E），其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是__深度优先_遍历方法。14、为实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需_队列__存放被访问的结点以实现遍历。15、设无向图G有n个顶点，m条边。阅读下面用邻接表存储该图的算法。（设顶点值用1～n或0～n-1编号），并在画线处完成填空。voidCreatGraph(AdjListg)//建立有n个顶点和m条边的无向图的邻接表存储结构{intn,m;scanf(%d%d,&n,&m);for(i=1,i=n;i++)//输入顶点信息,建立顶点向量{scanf(&g[i].vertex);g[i].firstarc=null;}for(k=1;k=m;k++)//输入边信息{scanf(&v1,&v2);//输入两个顶点i=GraphLocateVertex(g,v1);j=GraphLocateVertex(g,v2);//顶点定位p=(ArcNode*)malloc(sizeof(ArcNode));//申请边结点p-adjvex=j;p-next=g[i].firstarc;g[i].firstarc=p;//将边结点链入p=(ArcNode*)malloc(sizeof(ArcNode));p-adjvex=i;p-next=g[j].firstarc;g[j].frstarc=p;}}三、简答题1、已知一个无向网的顶点集为{a,b,c,d,e}，其邻接矩阵如下所示(1)画出该无向网图形；(2)根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。答案：(1)该无向网图形如下：563453262141edcba4(2)深度优先序列为：abcde；广度优先序列为：abdce2、已知一个无向网如下图所示，要求分别用普里姆算法和克鲁斯卡尔算法法构造最小生成树。假设以V1为起点，试画出构造过程。答案：（1）普里姆算法构造最小生成树的过程如下：（2）克鲁斯卡尔算法构造最小生成树的过程如下：d1aebc5436253、试评述邻接矩阵表示法、邻接表表示法、十字链表表示法、邻接多重表表示法这四种图的存储结构表示法的优、缺点。答案：(1)邻接矩阵表示法，有n个顶点的图占用n2个元素的存储单元，与边的个数无关，当边数较少时，存储效率较低。这种结构下，对查找结点的度、第一邻接点和下一邻接点、两结点间是否有边的操作有利，对插入和删除顶点的操作不利。(2)邻接表表示法是顶点的向量结构与顶点的邻接点的链式存储结构相结合的结构，顶点的向量结构含有n（n≥0）个顶点和指向各顶点第一邻接点的指针，其顶点的邻接点的链式存储结构是根据顶点的邻接点的实际设计的。这种结构适合查找顶点及邻接点的信息，查顶点的度，增加或删除顶点和边（弧）也很方便，但因指针多占用了存储空间，另外，某两顶点间是否有边（弧）也不如邻接矩阵那么清楚。对有向图的邻接表，查顶点出度容易，而查顶点入度却困难，要遍历整个邻接表。要想查入度象查出度那样容易，就要建立逆邻接表。无向图邻接表中边结点是边数的二倍也增加了存储量。(3)十字链表是有向图的另一种存储结构，将邻接表和逆邻接表结合到一起，弧结点也增加了信息（至少弧尾，弧头顶点在向量中的下标及从弧尾顶点发出及再入到弧头顶点的下一条弧的四个信息）。这种结构下，查询顶点的出度、入度、邻接点等信息非常方便。(4)邻接多重表是无向图的另一种存储结构，边结点至少包括5个域：连接边的两个顶点在顶点向量中的下标，指向与该边相连接的两顶点的下一条边的指针，以及该边的标记信息（如该边是否被访问）。边结点的个数与边的个数相同，这是邻接多重表比邻接表优越之处。6四、算法分析1、阅读下面的深度优先算法的代码，并完成填空。Booleanvisited[MAX]；//访问标志数组Status(*VisitFunc)(intv)；//指向函数的指针变量voidunknow(GraphG,intv){//从第v个顶点出发递归地深度优先遍历包含v的连通图Gvisited[v]=TRUE;VisitFunc(v);//访问第v个顶点for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w))if(!visited[w])unknow(G,w);/*查找其邻接点，对v的尚未访问的邻接点w递归调用unknown进行深度优先遍历。*/}2、有一个用于n个顶点连通带权无向图的算法描述如下：（1）．设集合T1与T2，初始均为空；（2）．在连通图上任选一点加入T1；（3）．以下步骤重复n-1次：a.在i属于T1，j不属于T1的边中选最小权的边；b.该边加入T2。则上述算法完成后，T2中共有___n-1___条边，该算法称___普里姆___算法，T2中的边构成图的___最小生成树___。3、设有n个顶点e条边的图的顶点是编号1~n，边的信息是有（用1表示）或无（用0表示），这时可用邻接矩阵表示图的存储结构。阅读下面的建立无向图的邻接矩阵的存储结构算法的代码，并完成填空。voidcreatgraph(intM[][],intn,inte){∥本算法建立n个顶点e条边的无向图的邻接矩阵的存储结构（设下标从1开始）inti,j;for(i=1;i=n;i++)for(j=1;j=n;j++)M[i][j]=0;for(i=1;i=e;i++){scanf(&i,&j);M[i][j]=1;M[j][i]=1;}}五、算法描述1、已知有向图有n个顶点，请写算法，根据用户输入的偶对建立该有向图的邻接表。即接受用户输入的vi,vj(以其中之一为0标志结束)，对于每条这样的边，申请一个结点，并插入到的单链表中，如此反复,直到将图中所有边处理完毕。提示：先产生邻接表的n个头结点（其结点数值域从1到n）。【答案】voidCreatAdjList(AdjListg)//建立有向图的邻接表存储结构{intn;scanf(%d,&n);for(i=1;i=n;j++){scanf(&g[i].vertex);g[i].firstarc=null;}//输入顶点信息scanf(&v1,.&v2);7while(v1&&v2)//题目要求两顶点之一为0表示结束{i=GraphLocateVertex(g2,v1);p=(ArcNode*)malloc(sizeof(ArcNode));p-adjvex=j;p-next=g[i].firstarc;g[i].firstarc=p;scanf(&v1,&v2);}}