搜索
习题七图一、单项选择题1.设有无向图G=（V，E）和G’=（V’,E’）,如G’为G的生成树，则下面不正确的说法是（）A．G’为G的子图B．G’为G的连通分量C．G’为G的极小连通子图且V’=VD．G’是G的无环子图2.任何一个带权的无向连通图的最小生成树（）A．只有一棵B．有一棵或多棵C．一定有多棵D．可能不存在3．以下说法正确的是（）A．连通分量是无向图中的极小连通子图。B．强连通分量是有向图中的极大强连通子图。C．在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧a,b。D．对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。4．图中有关路径的定义是（）。A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列C．由不同边所形成的序列D．上述定义都不是5．设无向图的顶点个数为n，则该图最多有（）条边。A．n-1B．n(n-1)/2C．n(n+1)/2D．0E．n26．要连通具有n个顶点的有向图，至少需要（）条边。A．n-lB．nC．n+lD．2n7．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。A．1/2B．2C．1D．48．下列哪一种图的邻接矩阵是对称矩阵？（）A．有向图B．无向图C．AOV网D．AOE网9.下列说法不正确的是（）。A．图的遍历是从给定的源点出发每一个顶点仅被访问一次B．遍历的基本算法有两种：深度遍历和广度遍历C．图的深度遍历不适用于有向图D．图的深度遍历是一个递归过程10．下面哪一方法可以判断出一个有向图是否有环（回路）：A．深度优先遍历B.拓扑排序C.求最短路径D.求关键路径11.在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为()。A.O(n)B.O(n+e)C.O(n2)D.O(n3)12．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={V1,V2,V1,V3,V1,V4,V2,V5,V3,V5,V3,V6,V4,V6,V5,V7,V6,V7},G的拓扑序列是（）。A．V1,V3,V4,V6,V2,V5,V7B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7D．V1,V2,V5,V3,V4,V6,V713.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）。A．G中有弧Vi，VjB．G中有一条从Vi到Vj的路径C．G中没有弧Vi,VjD．G中有一条从Vj到Vi的路径14.关键路径是事件结点网络中（）。A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长回路D．最短回路15．下列关于AOE网的叙述中，不正确的是（）。A．关键活动不按期完成就会影响整个工程的完成时间B．任何一个关键活动提前完成，那么整个工程将会提前完成C．所有的关键活动提前完成，那么整个工程将会提前完成D．某些关键活动提前完成，那么整个工程将会提前完成二、填空题1．具有10个顶点的无向图，边的总数最多为______。2.设无向图G有n个顶点和e条边，每个顶点Vi的度为di（1=i=n），则e=______3.在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要______条弧。4．下图中的强连通分量的个数为______个。5．N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_______个非零元素。6.在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是______。7.对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为______，邻接表的边结点个数为______。8.已知一无向图G=（V，E），其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是______遍历方法。9．构造连通网最小生成树的两个典型算法是______。10.有向图G可拓扑排序的判别条件是______。11.Dijkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按______次序依次产生，该算法弧上的权出现______情况时，不能正确产生最短路径。12.有向图G=(V,E),其中V(G)={0,1,2,3,4,5}，用a,b,d三元组表示弧a,b及弧上的权d.E(G)为{0,5,100,0,2,101,2,50,4,304,5,603,5,102,3,504,3,20}，则从源点0到顶点3的最短路径长度是______，经过的中间顶点是______。13．AOV网中,结点表示______,边表示______。AOE网中,结点表示______,边表示______。14．在AOE网中，从源点到汇点路径上各活动时间总和最长的路径称为______。15．在AOV网中，存在环意味着______，这是______的；对程序的数据流图来说，它表明存在______。16．如下为拓扑排序的C程序，（1）．列出对右图执行该程序后的输出结果。______（2）．在程序空白处填上适当语句。voidtopsort(hdnodesgraph[],intn){inti,j,k,top;node_pointerptr;top=-1;for(i=0;in;i++)if(!graph[i].count){graph[i].count=top;top=i;}for(i=0;in;i++)if(1)____{fprintf(stderr,\ngraphhasacycle\n);exit(1);}else{j=top;(2)_____;printf(v%d,,j);for(ptr=graph[j].link;ptr;ptr=ptr-link){k=ptr-vertex;graph[k].count--;if((3)_____){graph[k].count=top;top=k;}}}}三、应用题1．已知如图所示的有向图，请给出该图的：（1）每个顶点的入度、出度；（2）邻接矩阵；（3）邻接表；（4）逆邻接表；（5）强连通分量。2．已知图的邻接矩阵为：V1V2V3V4V5V6V1V2V3V4V5V6V7V8V9V10V10111000000V20001100000V30001010000V40000011010V50000001000V60000000110V70000000010V80000000001V90000000001V100000000000当用邻接表作为图的存储结构，且邻接表都按序号从大到小排序时，试写出：（1）．以顶点V1为出发点的唯一的深度优先遍历；（2）．以顶点V1为出发点的唯一的广度优先遍历；（3）．该图唯一的拓扑有序序列。3．已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以①为起点，试画出构造过程）。4．已知世界六大城市为:北京(Pe)、纽约(N)、巴黎(Pa)、伦敦(L)、东京(T)、墨西哥(M),下表给定了这六大城市之间的交通里程:世界六大城市交通里程表(单位:百公里)（1）．画出这六大城市的交通网络图;（2）．画出该图的邻接表表示法;（3）．画出该图按权值递增的顺序来构造的最小(代价)生成树.5．下表给出了某工程各工序之间的优先关系和各工序所需时间（1）．画出相应的AOE网（2）．列出各事件的最早发生时间,最迟发生时间（3）．找出关键路径并指明完成该工程所需最短时间.PENPALTMPE109828121124N109585510832PA825839792L815539589T211089795113M1243292891131265432010116618101459工序代号ABCDEFGHIJKLMN所需时间15105081540300151206015302040先驱工作----A,BBC,DBEG,IEIF,IH,J,KLG四、算法设计题1．已知有向图有n个顶点,请写算法,根据用户输入的偶对建立该有向图的邻接表。即接受用户输入的vi,vj(以其中之一为0标志结束),对于每条这样的边,申请一个结点,并插入到的单链表中,如此反复,直到将图中所有边处理完毕。提示：先产生邻接表的n个头结点（其结点数值域从1到n）。2．设已给出图的邻接矩阵，要求将邻接矩阵转换为邻接表。3．已知无向图采用邻接表存储方式，试写出删除边（i，j）的算法。4．假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。（注：图中不存在顶点到自己的弧）5．给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。6．对于一个使用邻接表存储的有向图G，可以利用深度优先遍历方法，对该图中结点进行拓扑排序。其基本思想是：在遍历过程中，每访问一个顶点，就将其邻接到的顶点的入度减一，并对其未访问的、入度为0的邻接到的顶点进行递归。（1）．给出完成上述功能的图的邻接表定义（结构）。（2）．定义在算法中使用的全局辅助数组。（3）．写出在遍历图的同时进行拓扑排序的算法。1256342236104469127第七章图一、单项选择题1.B2.B3．B4．A5．B6．B7．BC8．B9．C10．B11.B12．A13.D14.A15．B二、填空题1．452.略3.n4．35．2（N-1）6.第I列非零元素个数7.n2e8.深度优先9．普里姆（prim）算法和克鲁斯卡尔（Kruskal）算法10.不存在环11.递增负值12.50，经过中间顶点④13.(1)活动（2）活动间的优先关系（3）事件（4）活动边上的权代表活动持续时间14．关键路径15．（1）某项活动以自己为先决条件（2）荒谬（3）死循环16．1）V1V4V3V6V2V5(尽管图以邻接表为存储结构，但因没规定邻接点的排列，所以结果是不唯一的。本答案是按邻接点升序排列给出的。)（2）①top==-1②top=graph[j].count③graph[k].count==0三、应用题1．【解答】（1）顶点入度出度130222312413521623（2）邻接矩阵（3）邻接表（4）逆邻接表（5）强连通分量2．略3．为节省篇幅，这里仅用Kruskal算法，构造最小生成树过程如下：（下图也可选(2,4)代替(3,4),(5,6)代替(1,5)）4．(1)(2)略(3)最小生成树6个顶点5条边：V(G)={Pe,N,Pa,L,T,M}E(G)={(L,Pa,3),(Pe,T,21),(M,N,32),(L,N,55),(L,Pe,81)}5．（1）AOE网图略（2）各事件发生的最早和最晚时间如下表事件123456789101112最早发生时间01510655080200380395425445420最晚发生时间015576538080335380395425445425（3）关键路径为顶点序列：1-2-4-6-8-9-10-11；事件序列：A-C-E-G-H-L-M，完成工程所需的最短时间为445。四、算法设计题1．voidCreatAdjList(AdjListg)//建立有向图的邻接表存储结构{intn;scanf(%d,&n);for(i=1;i=n;j++){scanf(&g[i].vertex);g[i].firstarc=null;}//输入顶点信息scanf(&v1,.&v2);while(v1&&v2)//题目要求两顶点之一为0表示结束{i=GraphLocateVerte