第七章图习题-数据结构.doc

Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date第七章图习题-数据结构习题七 图习题七 图一、单项选择题1.设有无向图G=（V，E）和G=（V,E）,如G为G的生成树，则下面不正确的说法是（ ）AG为G的子图 BG为G的连通分量 CG为G的极小连通子图且V=V DG是G的无环子图2.任何一个带权的无向连通图的最小生成树（ ）A只有一棵 B有一棵或多棵 C一定有多棵 D可能不存在3以下说法正确的是（ ）A连通分量是无向图中的极小连通子图。B强连通分量是有向图中的极大强连通子图。C在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧<a,b>。D对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。4图中有关路径的定义是（ ）。A由顶点和相邻顶点序偶构成的边所形成的序列 B由不同顶点所形成的序列C由不同边所形成的序列 D上述定义都不是5设无向图的顶点个数为n，则该图最多有（ ）条边。An-1 Bn(n-1)/2 C n(n+1)/2 D0 En26要连通具有n个顶点的有向图，至少需要（ ）条边。An-l Bn Cn+l D2n7在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。A1/2 B2 C1 D48下列哪一种图的邻接矩阵是对称矩阵？（ ）A有向图 B无向图 CAOV网 DAOE网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的拓扑序列是（ ）。AV1,V3,V4,V6,V2,V5,V7 BV1,V3,V2,V6,V4,V5,V7CV1,V3,V4,V5,V2,V6,V7 DV1,V2,V5,V3,V4,V6,V713. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。 AG中有弧<Vi，Vj> BG中有一条从Vi到Vj的路径 CG中没有弧<Vi,Vj> DG中有一条从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下图中的强连通分量的个数为_个。5N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_个非零元素。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,10><1,2,5><0,4,30><4,5,60><3,5,10><2,3,50><4,3,20>，则从源点0到顶点3的最短路径长度是_，经过的中间顶点是_ _。13AOV网中,结点表示_,边表示_。AOE网中,结点表示_,边表示_。14在AOE网中，从源点到汇点路径上各活动时间总和最长的路径称为_ _。15在 AOV网 中，存在环意味着_ _，这是_ _的；对程序的数据流图来说，它表明存在_ _。V1V2V3V4V5V616如下为拓扑排序的C程序，（1）列出对右图执行该程序后的输出结果。_ _（2）在程序空白处填上适当语句。void topsort(hdnodes graph ,int n)int i,j,k,top; node_pointer ptr ; top=-1; for (i=0; i<n; i+) if (!graphi.count)graphi.count=top; top=i; for (i=0; i<n; i+) if(1)_ _ fprintf(stderr, "ngraph has a cycle n"); exit(1); else j=top;(2)_ _; printf( "v%d, " ,j) ;for (ptr=graphj.link; ptr; ptr=ptr->link)k=ptr->vertex; graphk.count-; if(3)_ _) graphk.count=top; top=k; 三、应用题1已知如图所示的有向图，请给出该图的： （1）       每个顶点的入度、出度；（2）       邻接矩阵；（3）       邻接表；（4）       逆邻接表；（5）       强连通分量。2已知图的邻接矩阵为： V1V2V3V4V5V6V7V8V9V10V10111000000V20001100000V30001010000V40000011010V50000001000V60000000110V70000000010V80000000001V90000000001V100000000000当用邻接表作为图的存储结构，且邻接表都按序号从大到小排序时，试写出：（1）以顶点V1为出发点的唯一的深度优先遍历；（2）以顶点V1为出发点的唯一的广度优先遍历；（3）该图唯一的拓扑有序序列。3已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以为起点，试画出构造过程）。1265432010116618101459    4已知世界六大城市为:北京(Pe)、纽约(N)、巴黎(Pa)、 伦敦(L) 、 东京(T) 、 墨西哥(M),下表给定了这六大城市之间的交通里程: 世界六大城市交通里程表(单位:百公里) PENPALTMPE 109828121124N109 585510832PA8258 39792L81553 9589T211089795 113M124329289113 （1）画出这六大城市的交通网络图;（2）画出该图的邻接表表示法;（3）画出该图按权值递增的顺序来构造的最小(代价)生成树.5下表给出了某工程各工序之间的优先关系和各工序所需时间（1）画出相应的AOE网 （2）列出各事件的最早发生时间,最迟发生时间（3）找出关键路径并指明完成该工程所需最短时间. 工序代号 A B C D E F G H I J K L M N 所需时间 15 10 50 8 15 40 300 15 120 60 15 30 20 40 先驱工作 - - A,B B C,D B E G,I E I F,I H,J,K L G 四、算法设计题1已知有向图有n个顶点,请写算法,根据用户输入的偶对建立该有向图的邻接表。即接受用户输入的<vi,vj>(以其中之一为0标志结束),对于每条这样的边,申请一个结点,并插入到的单链表中,如此反复,直到将图中所有边处理完毕。提示：先产生邻接表的n个头结点（其结点数值域从1到n）。2设已给出图的邻接矩阵，要求将邻接矩阵转换为邻接表。3已知无向图采用邻接表存储方式，试写出删除边（i，j）的算法。4假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。（注：图中不存在顶点到自己的弧）5给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。1256342236104469127       6对于一个使用邻接表存储的有向图G，可以利用深度优先遍历方法，对该图中结点进行拓扑排序。其基本思想是：在遍历过程中，每访问一个顶点，就将其邻接到的顶点的入度减一，并对其未访问的、入度为0的邻接到的顶点进行递归。（1）给出完成上述功能的图的邻接表定义（结构）。（2）定义在算法中使用的全局辅助数组。（3）写出在遍历图的同时进行拓扑排序的算法。 第七章 图一、单项选择题1.B2.B3B4A5B6B7B C8B9C10B11. B12A13. D14. A15B二、填空题1452. 略3. n4352（N-1）6. 第I列非零元素个数7. n 2e8. 深度优先9普里姆（prim）算法和克鲁斯卡尔（Kruskal）算法10. 不存在环11. 递增 负值12. 50，经过中间顶点13.(1)活动 （2）活动间的优先关系 （3）事件 （4）活动 边上的权代表活动持续时间14关键路径15（1）某项活动以自己为先决条件 （2）荒谬 （3）死循环161）V1 V4 V3 V6 V2 V5(尽管图以邻接表为存储结构，但因没规定邻接点的排列，所以结果是不唯一的。本答案是按邻接点升序排列给出的。)（2） top=-1 top=graphj.count graphk.count=0三、应用题1【解答】 （1）顶点 入度 出度 1 3 0 2 2 2 3 1 2 4 1 3 5 2 1 6 2 3（2）      邻接矩阵  （3）邻接表（4）逆邻接表（5）强连通分量2略3为节省篇幅，这里仅用Kruskal算法，构造最小生成树过程如下：（下图也可选(2,4)代替(3,4),(5,6)代替(1,5)）52391611621015643   即6101552346 PePaNTML4(1)          (2)略(3)最小生成树6个顶点5条边：V(G)=Pe,N,Pa,L,T,ME(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  void CreatAdjList(AdjList g)/建立有向图的邻接表存储结构int n;scanf("%d",&n);for (i=1;i<=n;j+)scanf(&gi.vertex); gi.firstarc=null;/输入顶点信息scanf(&v1,.&v2); while(v1 && v2)/题目要求两顶点之一为0表示结束 i=GraphLocateVertex(g2,v1); p=(ArcNode*)malloc(sizeof(ArcNode); p->adjvex=j;p->next=gi.firstarc;gi.firstarc=p;scanf(&v1,&v2); 2void AdjMatrixToAdjList( AdjMatrix gm, AdjList gl )/将图的邻接矩阵表示法转换为邻接表表示法。for (i=1;i<=n;i+) /邻接表表头向量初始化。 scanf(&gli.vertex); gli.firstarc=null; for (i=1;i<=n;i+) for (j=1;j<=n;j+) if (gmij=1) p=(ArcNode *)malloc(sizeof(ArcNode) ;/申请结点空间。p->adjvex=j;/顶点I的邻接点是jp->next=gli.firstarc; gli.firstarc=p; /链入顶点i的邻接点链表中 /end算法讨论 算法中邻接表中顶点在向量表中的下标与其在邻接矩阵中的行号相同。3void DeletEdge(AdjList g,int i,j) /在用邻接表方式存储的无向图g中，删除边(i,j)p=gi.firstarc; pre=null; /删顶点i 的边结点(i,j),pre是前驱指针while (p) if (p->adjvex=j) if(pre=null)gi.firstarc=p->next;else pre->next=p->next;free(p);/释放结点空间。 else pre=p; p=p->next; /沿链表继续查找p=gj.firstarc; pre=null; /删顶点j 的边结点(j,i)while (p) if (p->adjvex=i) if(pre=null)gj.firstarc=p->next;else pre->next=p->next;free(p);/释放结点空间。 else pre=p; p=p->next; /沿链表继续查找 / DeletEdge算法讨论 算法中假定给的i，j 均存在，否则应检查其合法性。若未给顶点编号，而给出顶点信息，则先用顶点定位函数求出其在邻接表顶点向量中的下标i和j。4题目分析有向图判断回路要比无向图复杂。利用深度优先遍历，将顶点分成三类：未访问；已访问但其邻接点未访问完;已访问且其邻接点已访问完。下面用0，1，2表示这三种状态。前面已提到，若dfs（v）结束前出现顶点u到v的回边，则图中必有包含顶点v和u的回路。对应程序中v的状态为1，而u是正访问的顶点，若我们找出u的下一邻接点的状态为1，就可以输出回路了。void Print(int v,int start ) /输出从顶点start开始的回路。for(i=1;i<=n;i+) if(gvi!=0 && visitedi=1 ) /若存在边（v,i），且顶点i的状态为1。 printf(“%d”,v); if(i=start) printf(“n”); else Print(i,start);break;/if /Printvoid dfs(int v) visitedv=1;for(j=1;j<=n;j+ ) if (gvj!=0) /存在边(v,j) if (visitedj!=1) if (!visitedj) dfs(j); /if else cycle=1; Print(j,j); visitedv=2;/dfsvoid find_cycle() /判断是否有回路，有则输出邻接矩阵。visited数组为全局变量。 for (i=1;i<=n;i+) visitedi=0; for (i=1;i<=n;i+ ) if (!visitedi) dfs(i);/find_cycle5题目分析 该题可用求每对顶点间最短路径的FLOYD算法求解。求出每一顶点（村庄）到其它顶点（村庄）的最短路径。在每个顶点到其它顶点的最短路径中，选出最长的一条。因为有n个顶点，所以有n条, 在这n条最长路径中找出最短一条，它的出发点（村庄）就是医院应建立的村庄。 void Hospital(AdjMatrix w,int n) /在以邻接带权矩阵表示的n个村庄中，求医院建在何处，使离医院最远的村庄到医院的路径最短。 for (k=1;k<=n;k+) /求任意两顶点间的最短路径 for (i=1;i<=n;i+) for (j=1;j<=n;j+) if (wik+wkj<wij) wij=wik+wkj; m=MAXINT; /设定m为机器内最大整数。 for (i=1;i<=n;i+) /求最长路径中最短的一条。 s=0; for (j=1;j<=n;j+) /求从某村庄i（1<=i<=n）到其它村庄的最长路径。 if (wij>s) s=wij; if (s<=m) m=s; k=i;/在最长路径中，取最短的一条。m记最长路径，k记出发顶点的下标。 Printf(“医院应建在%d村庄，到医院距离为%dn”,i,m); /for/算法结束对以上实例模拟的过程略。在A(6)矩阵中（见下图），各行中最大数依次是9，9，6，7，9，9。这几个最大数中最小者为6，故医院应建在第三个村庄中,离医院最远的村庄到医院的距离是6。6题目分析 对有向图进行深度优先遍历可以判定图中是否有回路。若从有向图某个顶点v出发遍历，在dfs(v)结束之前，出现从顶点u到顶点v的回边，图中必存在环。这里设定visited访问数组和finished数组为全局变量，若finishedi=1,表示顶点i的邻接点已搜索完毕。由于dfs产生的是逆拓扑排序，故设一类型是指向邻接表的边结点的全局指针变量final，在dfs函数退出时，把顶点v插入到final所指的链表中，链表中的结点就是一个正常的拓扑序列。邻接表的定义与本书相同，这里只写出拓扑排序算法。 int visited=0; finished=0; flag=1; /flag测试拓扑排序是否成功 ArcNode *final=null; /final是指向顶点链表的指针，初始化为0 void dfs(AdjList g,vertype v) /以顶点v开始深度优先遍历有向图g，顶点信息就是顶点编号. ArcNode *t; /指向边结点的临时变量 printf("%d",v); visitedv=1; p=gv.firstarc; while(p!=null) j=p->adjvex; if (visitedj=1 && finishedj=0) flag=0 /dfs结束前出现回边 else if(visitedj=0) dfs(g,j); finishedj=1; /if p=p->next; /whilet=(ArcNode *)malloc(sizeof(ArcNode);/申请边结点 t->adjvex=v; t->next=final; final=t; /将该顶点插入链表 /dfs结束 int dfs-Topsort(Adjlist g) /对以邻接表为存储结构的有向图进行拓扑排序，拓扑排序成功返回1，否则返回0 i=1; while (flag && i <=n) if (visitedi=0) dfs(g,i); finishedi=1; /if return(flag); / dfs-Topsort-