第七章图

第七章图一、选择题1．在一个图中所有顶点度之和等于图的边数的（）倍。A.1B.2C.3D.0.52．在一个具有n个顶点的无向图中最多有（）条边。A．n-1B.nC.n(n-1)/2D.n(n-1)3．一个具有n个顶点的连通图的生成树有且仅有（）条边。A．n-1B.nC.n(n-1)/2D.n(n-1)4．一个具有n个结点，e条弧（有向边）的有向图，采用邻接表作为存储结构，邻接表中表结点的个数是（）。A．nB.eC.n+eD.2e5．一个具有n个结点的有向完全图中的边数为()A.n-1B.nC.n(n-1)/2D.n(n-1)6．对图进行广度优先遍历类似于对树进行（）A．先序遍历B.中序遍历C.后序遍历D.按层次遍历7.对图进行深度优先遍历类似于对树进行（）A．先序遍历B.中序遍历C.后序遍历D.按层次遍历8．有向图的邻接矩阵中，j列非0元素之和是（）A．第j个顶点的入度B.第j个顶点的出度C.第j个顶点的度D.第j个顶点的权9．判定一个有向图是否存在回路除了可以利用深度优先遍历算法外，还可以利用（）。A.求关键路径B.求最短路径算法C.广度优先遍历D.拓扑排序方法10．任何一个无向连通图，若各边的权值均不相等，则最小生成树（）。A．只有一棵B.一棵或多棵C．多棵D.棵数取决于生成算法11．任何一个无向连通图，最小生成树（）。A．只有一棵B.一棵或多棵C．多棵D.棵数取决于生成算12．设有一个无向图G＝(V,E),和G＇＝(V＇,E＇)，如果G＇是G的生成树，则下列命题不成立的是（）。A．G＇是G的子图B.G＇是G的极大连通子图C.G＇是G的极小连通子图D.G＇中无回路13．有向图中,所有顶点的入度之和是所有顶点的出度的（）倍。A．1B.2C.3D.4.14.含n个顶点的连通图中任意一条简单回路其长度不会超过（）。A．nB.n-1C.n+1D.2n15．用邻接表表示图，进行广度优先遍历，通常借助（）来实现算法。A．栈B.队列C.广义表D.树二、填空题1．连通分量是指无向图的。连通图中的连通分量有个。2．一个图的表示法是唯一的，而表示法不是唯一的。3．的邻接矩阵一定是对称的，而的邻接矩阵不一定是对称的。4．具有n个顶点，e条边的图，构造它的邻接矩阵的时间复杂度为，构造它的邻接表时间复杂度为。5．如果n个顶点的图是一个环，则它有棵生成树。6．为了节省存储空间，稀疏图通常采用存储，稠密图通常采用存储。7．在有向图的逆邻接表上可方便的求出结点的，但求则须遍历整个表。8．求最小生成树的Kruskal算法时间复杂度为，主要与图中的边数有关，适合于。9．求最小生成出的prim算法时间复杂度为，主要与图中的顶点数有关，适合于。10．具有n个顶点，e条边的图采用的邻接表存储，广度优先遍历的时间复杂度为，深度优先遍历的时间复杂度为。11．具有n个结点的有向图的邻接矩阵，i行j列元素为1说明.12.具有n个结点的有向图的邻接矩阵包含的元素数是个。13．连通图的生成树是图的。还包含了图中的。14．边上带有权值的图称为或。15．拓扑排序就是对一个中的顶点排成一个具有前后次序。三、简答题1.已知图如下图所示，请给出图的邻接矩阵和邻接表。2.对1题所示图，在邻接表上进行遍历操作，给出深度优先遍历序列和广度优先遍历序列。3.有向图如下图所示，写出可能的所有拓扑序列。4.已知网如下图所示按克鲁斯卡尔（Kruskal）算法构成最小生成树5．已知一个无向图的顶点集为｛a,b,c,d,e｝，其邻接矩阵如下所示01001a10010b00011c01101d10110e(1)画出该图的图形；(2)根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。四、程序阅读题1.以邻接表为存储结构，dfs算法如下，在划线处填上适当语句。vioddfs(ALGraph*G,inti){Edgenode*p;print(＂%c＂,G-adjlist[i].vertex);(1)p＝G-adjlist[i].firstedge;while(p){if(!visited[p-adjvex])(2)(3)}}2．已知图的邻接表，构造邻接矩阵的算法如下，请在在划线处填上适当语句。VoidCreatGraph(Mgraph*G,ALGraphG1){Edgenode*p;inti,j,k;for(i＝0;iG-n;i++)(1)for(i＝0;iG-n;i++)for(j＝0;jG-n;j++)(2)for(i＝0;iG-n;i++){(3)while(p){G-edges[i][p-adjvex]＝1;p＝p-next;}}}3.阅读程序，指出程序功能voiddelgraphedge(ALGraph*G,inti,intj){Edgenode*p,*q;p＝G-adjlist[i].firstedge;q＝&G-adjlist[i]while(p&&p-adjvex!＝j){q＝p;;p＝p-next;}if(p){q＝p-next;free(p);}p＝G-adjlist[j].firstedge;q＝&G-adjlist[j]while(p&&p-adjvex!＝i){q＝p;;p＝p-next;}if(p){q＝p-next;free(p);}}4．已知带权图的邻接矩阵表示和邻接表表示的形式说明分别如下：#defineMaxNum50//图的最大顶点数#defineINFINITYINT_MAX//INT_MAX为最大整数，表示∞typedefstruct{charvexs[MaxNum];//字符类型的顶点表intedges[MaxNum][MaxMum];//权值为整型的邻接矩阵intn,e;//图中当前的顶点数和边数}MGraph;//邻接矩阵结构描述typedefstructnode{intadjvex;//邻接点域intweight;//边的权值structnode*next;//链指针域}EdgeNode;//边表结点结构描述typedefstruct{charvertex;//顶点域EdgeNode*firstedge;//边表头指针}VertexNode;//顶点表结点结构描述typedefstruct{VertexNodeadjlist[MaxNum];//邻接表intn,e;//图中当前的顶点数和边数}ALGraph;//邻接表结构描述下列算法是根据一个带权图的邻接矩阵存储结构G1建立该图的邻接表存储结构G2，请填入合适的内容，使其成为一个完整的算法。〖2002〗voidconvertM(MGraph*G1,ALGraph*G2){inti,j;EdgeNode*p;G2-n＝G1-n;G2-e＝G1-e;for(i＝0;iG1-n;i++){G2-adjlist[i].vertex＝G1-vexs[i];G2-adjlist[i].firstedge＝(1);}for(i＝0;iG1-n;i++)for(j＝0;jG1-n;j++)if(G1-edges[i][j]INFINITY){p＝(EdgeNode*)malloc(sizeof(EdgeNode));p-weight＝(2);p-adjvex＝j;p-next＝G2-adjlist[i].firstedge;(3);}}5．下列函数FindCycle(G,i)的功能是，对一个采用邻接表作存储结构的有向图G，利用深度优先搜索策略寻找一条经过顶点vi的简单回路。数组cycle_path用于保存搜索过程中形成的回路，cycle_path[k]＝j(j≥0)表示在回路中顶点vk的下一个顶点是vj。请在空缺处填入合适的内容，使其成为一个完整的算法。已知邻接表的顶点表结点结构为：边表结点EdgeNode结构为：intcycle_path[MaxNum];vertexfirstedgeadjvexnextintFindCycle(ALGraph*G,inti){//若回路存在，则返回1，否则返回0intj;for(j＝0;jG-n;j++)cycle_path[j]＝-1;returnDFSPath(G,i,i);}intDFSPath(ALGraph*G,intj,inti){EdgeNode*p;intcycled＝0;for(p＝G-adjlist[j].firstedge;p&&!cycled;p＝p-next){cycle_path[j]＝p-adjvex;if((1))cycled＝1;//已找到回路elseif(cycle_path[p-adjvex]＝＝-1)cycled＝(2);}return(3)}五、程序设计题1．试在无向图的邻接矩阵和邻接表上实现往图中插入一条边的算法：2．以邻接矩阵为存储结构，写出bfs算法。3．以邻接表为存储结构，写出dfs非递归算法。4.以邻接表为存储结构，写出求各顶点度的算法。5．试以邻接表和邻接矩阵为存储结构，分别写出基于DFS和BFS遍历的算法来判别顶点vi和vj(i≠j)之间是否有路径。6．试分别写出求DFS和BFS生成树（或生成森林）的算法，要求打印出所有的树边。7．写一算法求连通分量的个数并输出各连通分量的顶点集。8．设图中各边上的权值均相等，试以邻接表和邻接矩阵为存储结构，分别写出算法：（1）求顶点vi到vj(i≠j)的最短路径；（2）求源点vi到其余各顶点的最短路径。要求输出路径上的所有顶点（提示：利用BFS遍历的思想）。9．以邻接表为存储结构，写一基于DFS遍历策略的算法，求出图中通过某个顶点vk的简单回路（若存在）。10．利用拓扑排序算法的思想写一算法判别有向图中是否存在有向环，当有向环存在时，输出构成环的顶点。