《数据结构及其应用》笔记含答案第六章图.doc

第6章 图一、填空题1、用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网（AOV-网）。2、有n(n-1)/2条边的无向图称为_无向完全图_；有n(n-1)条边的有向图称为_有向完全图。3、一个含n个结点的完全无向图中，其最大边数为_ n(n-1)/2_。4、顶点表示事件，弧表示活动，权表示活动持续时间的有向图称为AOE-网。二、判断题1、任何无向图都存在生成树。（ ）2、连通分量是无向图中的极小连通子图。（ ）3、强连通分量是有向图中的极大强连通子图。（ ）4、用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。（ ）5、邻接表法只用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（） 6、求最小生成树的Prim算法在边较少、结点较多时效率较高。（ ）7、图的最小生成树的形状可能不唯一。（ ） 8、一个AOV网的拓扑序列一定是唯一的。 （ ）9、若AOV网中存在环，则不能求它的拓扑排序序列。（ ） 10、若AOV网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。（）11、缩短关键路径上活动的工期一定能够缩短整个工程的工期。（ ） 12、AOE网中一定只有一条关键路径。（ ）三、单项选择题1、在一个图中，所有顶点的度数之和等于图的边数的（ C ）倍。A1/2 B1 C2 D4 2、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ B ）倍。A1/2 B1 C2 D4 解释：有向图所有顶点入度之和等于所有顶点出度之和。3、具有n个顶点的有向图最多有（ B ）条边。 An Bn(n-1) Cn(n+1) Dn2 解释：有向图的边有方向之分，即为从n个顶点中选取2个顶点有序排列，结果为n(n-1)。4、n个顶点的连通图用邻接距阵表示时，该距阵至少有（ B ）个非零元素。An B2(n-1) Cn/2 Dn2 5、G是一个非连通无向图，共有28条边，则该图至少有（ C ）个顶点。A7 B8 C9 D10 解释：8个顶点的无向图最多有8*7/2=28条边，再添加一个点即构成非连通无向图，故至少有9个顶点。6、若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（ B ）图。A非连通 B连通 C强连通 D有向解释：即从该无向图任意一个顶点出发有到各个顶点的路径，所以该无向图是连通图。7、下面（A）算法适合构造一个稠密图G的最小生成树。A Prim算法 BKruskal算法 CFloyd算法 DDijkstra算法解释：Prim算法适合构造一个稠密图G的最小生成树，Kruskal算法适合构造一个稀疏图G的最小生成树。8、用邻接表表示图进行广度优先遍历时，通常借助（ B ）来实现算法。A栈 B. 队列 C. 树 D图 解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。9、用邻接表表示图进行深度优先遍历时，通常借助（ A ）来实现算法。A栈 B. 队列 C. 树 D图 解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。10、深度优先遍历类似于二叉树的（ A ）。A先序遍历 B中序遍历 C后序遍历 D层次遍历11、广度优先遍历类似于二叉树的（ D ）。A先序遍历 B中序遍历 C后序遍历 D层次遍历12、图的BFS生成树的树高比DFS生成树的树高（ C ）。A小 B相等 C小或相等 D大或相等解释：对于一些特殊的图，比如只有一个顶点的图，其BFS生成树的树高和DFS生成树的树高相等。一般的图，根据图的BFS生成树和DFS树的算法思想，BFS生成树的树高比DFS生成树的树高小。13、已知图的邻接矩阵如图6.30所示，则从顶点v0出发按深度优先遍历的结果是（ ）。 图6.30 邻接矩阵14、已知图的邻接表如图6.31所示，则从顶点v0出发按广度优先遍历的结果是（ D ），按深度优先遍历的结果是（ D ）。图6.31 邻接表A0 1 3 2B0 2 3 1C0 3 2 1D0 1 2 315、下面（ B ）方法可以判断出一个有向图是否有环。A深度优先遍历 B拓扑排序 C求最短路径 D求关键路径四、应用题1、已知图6.32所示的有向图，请给出：1）每个顶点的入度和出度； 2）邻接矩阵；3）邻接表；4）逆邻接表。 图6.32 有向图图6.33 无向网答案：2、已知如图6.33所示的无向网，请给出：1）邻接矩阵； 2）邻接表；3）最小生成树答案： ab4c3ba4c5d5e9ca3b5d5h5db5c5e7f6g5h4eb9d7f3fd6e3g2gd5f2h63、已知图的邻接矩阵如图6.34所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。图6.34 邻接矩阵答案：4、有向网如图6.35所示，试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径，完成表6.9。图6.35 有向网表6.9D终点i=1i=2i=3i=4i=5i=6b15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)c2(a,c)d12(a,d)12(a,d)11(a,c,f,d)11(a,c,f,d)e10(a,c,e)10(a,c,e)f6(a,c,f)g16(a,c,f,g)16(a,c,f,g)14(a,c,f,d,g)S终点集a,ca,c,fa,c,f,ea,c,f,e,da,c,f,e,d,ga,c,f,e,d,g,b5、试对图6.36所示的AOE-网：1）求这个工程最早可能在什么时间结束； 2）求每个活动的最早开始时间和最迟开始时间；3）确定哪些活动是关键活动图6.36 AOE-网答案：按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l，根据l - e = 0? 来确定关键活动，从而确定关键路径。1 2 3 4 5 6 Ve019152938 43Vl01915373843e00151919152938l170152719273738-e1700801280此工程最早完成时间为43。关键路径为6、对于下图所示的有向图，试给出：1）每个顶点的入度和出度； 2）邻接矩阵； 3）邻接表；答案：1）顶点出度入度1122223314035326212）0001001000000010001100001010100110003）7、一个无向图的邻接表如下图所示：1） 从顶点V0出发进行深度优先搜索，经历的结点顺序为。V0、V1、V2、V32）从顶点V0出发进行广度优先搜索，经历的结点顺序为。V0、V1、V3、V28、分别用PRIM 算法和Kruskal算法求下图的最小生成树。图1：PRIM:(1) （2） （3）U=1 U=1，5 U=1,5,4(4) (5) U=1,5,4,3 U=1,5,4,3,2(6) (7) U=1,5,4,3,2,7 U=1,5,4,3,2,7,6Kruskal:将权值从小到大排列，初始状态仅为含有7个顶点的非连通图顶点顶点权值3432352474582512151457161718121946216727（1）初始状态（2）（3）（4）（5）（6）（7）图2：PRIM：u=V1u=V1、V3u=V1、V3、V6u=V1、V3、V6、V4u=V1、V3、V6、V4、V2u=V1、V3、V6、V4、V2、V5Kruskal顶点顶点权值131462253364145345235126356566（1）初始状态（2）（3）（4）（5）（6）9、计算下列有向图的拓扑有序序列，并画出每个结点的输出过程。图1：（1）输出C1（2）输出C2（3）输出C3（4）输出C5（5）输出C8（6）输出C9（7）输出C4（8）输出C6最后得到拓扑有序序列为：C2、C3、C5、C8、C9、C4、C6、C7图2：（1）输出V6（2）输出V1（3）输出V4（4）输出V3（5）输出V2最后得到拓扑有序序列为：V6、V1、V4、V3、V2、V510、有向图G如下所示，写出两个拓扑序列。第一种：（1）输出V1（2）输出V2（3）输出V3（4）输出V6（4）输出V5最后得到的拓扑有序序列为：V1、V2、V3、V6、V5、V4第二种：（1）输出V1（2）输出V3（3）输出V2（4）输出V6（4）输出V5最后得到的拓扑有序序列为：V1、V3、V3、V6、V5、V411、如下图所示AOE网：1）列出各事件的最早、最迟发生时间；2）列出各活动的最早、最迟发生时间；3）找出该AOE网中的关键路径，并回答完成该工程需要的最短时间。图1：事件最早发生时间最迟发生时间Ave(A)=0vl(A)= min(vl(B) 3, vl(C) 5)= 0Bve(B)= ve(A)+3=3vl(B)= vl(D) 6=6Cve(C)= ve(A)+5=5vl(C)= vl(D) 7=5Dve(D)=max(ve(B)+6, ve(C)+7)=12vl(D)= min(vl(E) 9, vl(F) 10, vl(G) 8)=12Eve(E)= ve(D)+9=21vl(E)= vl(H) 5=24Fve(F)= max(ve(D)+10, ve(G)+6)=26vl(F)= vl(H) 3=26Gve(G)=ve(D)+8=20vl(G)= min(vl(H) 2, vl(F) 6)=20Hve(H)= max(ve(E)+E, ve(G)+2, ve(F)+3)=29vl(H)=29活动最早发生时间最迟发生时间a1e(a1)= ve(A)=0l(a1)= vl(B)-3=3a2e(a2)= ve(A)=0l(a2)= vl(C)-5=0a3e(a3)=ve(B) =3l(a3)= vl(D)-6=6a4e(a4)= ve(C)= 5l(a4)= vl(D)-7=5a5e(a5)= ve(D) =12l(a5)= vl(E)-9=15a6e(a6)= ve(D) =12l(a6)= vl(F)-10=16a7e(a7)= ve(D) =12l(a7)= vl(G)-8=12a8e(a8)= ve(G)=20l(a8)= vl(G)-6=14a9e(a9)= ve(E)= 21l(a9)= vl(H)-5=24a10e(a10)= ve(F)= 26l(a10)= vl(H)-3=26a11e(a11)= ve(G)=20l(a11)= vl(H)-2=27关键路径如下图，完成该工程需要的最短时间=5+7+6+8+3=29 图2：事件最早发生时间最迟发生时间V0ve(V0)=0vl(V0)= Minvl(1)-W0,1, vl(2)-W0,2, vl(3)-W0,3=0V1ve(V1)=Maxve(0)+W0,1=6vl(V1)= Minvl(4)-W1,4=6V2ve(V2)=Maxve(0)+W0,2=4vl(V2)= Minvl(4)-W2,4=6V3ve(V3)=Maxve(0)+W0,3=5vl(V3)= Minvl(5)-W3,5=8V4ve(V4)=Maxve(1)+W1,4,ve2+W2,4=7vl(V4)= Minvl(6)-W4,6, vl(7)-W4,7=7V5ve(V5)=Maxve(3)+W3,5=7vl(V5)= Minvl(7)-W5,7=10V6ve(V6)=Maxve(4)+W4,6=16vl(V6)= Minvl(8)-W6,8=16V7ve(V7)=Maxve(4)+W4,7, ve(5)+W5,7=14vl(V7)= Minvl(8)-W7,8=14V8ve(V8)=Maxve(6)+W6,8, ve(7)+W7,8=18vl(V8)=ve(V8)=18活动最早发生时间最迟发生时间a1e(a1)= ve(V0)=0l(a1)= vl(V1)- W0,1=0a2e(a2)= ve(V0)=0l(a2)= vl(V2)- W0,2=2a3e(a3)= ve(V0)=0l(a3)= vl(V3)- W0,3=3a4e(a4)= ve(V1)= 6l(a4)= vl(V4)- W1,4=6a5e(a5)= ve(V2) =4l(a5)= vl(V4)- W2,4=6a6e(a6)= ve(V3) =5l(a6)= vl(V5)- W3,5=8a7e(a7)= ve(V4) =7l(a7)= vl(V6)- W4,6=7a8e(a8)= ve(V4)=7l(a8)= vl(V7)- W4,7=7a9e(a9)= ve(V5)= 7l(a9)= vl(V7)- W5,7=10a10e(a10)= ve(V5)=16l(a10)= vl(V8)- W6,8=16a11e(a11)= ve(V7)=14l(a11)= vl(V8)- W7,8=14关键路径如下图，完成该工程需要的最短时间=6+1+9+2=18五、算法设计题1、请在下划线中填写语句，完成采用邻接矩阵表示法创建无向网的算法程序。#define MaxInt 32767 #define MVNum 100 typedef char VerTexType; typedef int ArcType; typedef struct VerTexType vexsMVNum; ArcType ar