《数据结构》习题汇编07-第七章-图-试题.doc

第七章 图 试题一、单项选择题1. 在无向图中定义顶点得度为与它相关联得( )得数目。A、 顶点B、 边C、 权D、 权值2. 在无向图中定义顶点 vi与vj之间得路径为从vi到达vj得一个( )。A、 顶点序列B、 边序列C、 权值总与D、 边得条数3. 图得简单路径就是指( )不重复得路径。A、 权值B、 顶点C、 边D、 边与顶点均4. 设无向图得顶点个数为n,则该图最多有( )条边。A、 n1 B、 n(n1)/2C、 n(n+1)/2 D、 n(n1)5. n个顶点得连通图至少有( )条边。A、 n1 B、 nC、 n+1D、 06. 在一个无向图中,所有顶点得度数之与等于所有边数得 ( ) 倍。A、 3B、 2C、 1D、 1/27. 若采用邻接矩阵法存储一个n个顶点得无向图,则该邻接矩阵就是一个 ( )。A、 上三角矩阵B、 稀疏矩阵C、 对角矩阵D、 对称矩阵8. 图得深度优先搜索类似于树得( )次序遍历。A、 先根B、 中根C、 后根D、 层次9. 图得广度优先搜索类似于树得( )次序遍历。A、 先根B、 中根C、 后根D、 层次10. 在用Kruskal算法求解带权连通图得最小(代价)生成树时,通常采用一个( )辅助结构,判断一条边得两个端点就是否在同一个连通分量上。A、 位向量B、 堆C、 并查集D、 生成树顶点集合11. 在用Kruskal算法求解带权连通图得最小(代价)生成树时,选择权值最小得边得原则就是该边不能在图中构成( )。A、 重边B、 有向环C、 回路D、 权值重复得边12. 在用Dijkstra算法求解带权有向图得最短路径问题时,要求图中每条边所带得权值必须就是( )。A、 非零B、 非整C、 非负D、 非正13. 在一个连通图中进行深度优先搜索得到一棵深度优先生成树,树根结点就是关节点得充要条件就是它至少有( )子女。A、 1B、 2C、 3D、 014. 设有向图有n个顶点与e条边,采用邻接表作为其存储表示,在进行拓扑排序时,总得计算时间为( )。A、 O(nlog2e)B、 O(n+e)C、 O(ne)D、 O(n2)15. 设有向图有n个顶点与e条边,采用邻接矩阵作为其存储表示,在进行拓扑排序时,总得计算时间为( )。A、 O(nlog2e)B、 O(n+e)C、 O(ne)D、 O(n2)16. 设G1 = (V1, E1) 与G2 = (V2, E2) 为两个图,如果V1 V2,E1 E2,则称( )。 A、 G1就是G2得子图 B、 G2就是G1得子图 C、 G1就是G2得连通分量 D、 G2就是G1得连通分量17. 有向图得一个顶点得度为该顶点得( )。 A、 入度 B、 出度C、 入度与出度之与 D、 (入度出度)218. 一个连通图得生成树就是包含图中所有顶点得一个( )子图。 A、 极小B、 连通C、 极小连通D、 无环19. n (n1) 个顶点得强连通图中至少含有( )条有向边。 A、 n1 B、 nn(n1)/2D、 n(n1)20. 在一个带权连通图G中,权值最小得边一定包含在G得( )生成树中。 A、 某个最小B、 任何最小C、 广度优先D、深度优先21. 对于具有e条边得无向图,它得邻接表中有( )个边结点。 A、 e1B、 e C、 2(e1) D、 2e22. 对于如图所示得带权有向图,从顶点1到顶点5得最短路径为( )。 A、1, 4, 5B、 1, 2, 3, 5C、 1, 4, 3, 5D、 1, 2, 4, 3, 51261381955412323. 具有n个顶点得有向无环图最多可包含( )条有向边。 A、 n1B、 n C、 n(n1)/2 D、n(n1)24. 一个有n个顶点与n条边得无向图一定就是( )。 A、 连通得 B、 不连通得 C、 无环得 D、 有环得25. 在n个顶点得有向无环图得邻接矩阵中至少有( )个零元素。 A、 nB、 n(n1)/2 C、 n(n+1)/2D、 n(n1)26. 对于有向图,其邻接矩阵表示比邻接表表示更易于( )。 A、 求一个顶点得度 B、 求一个顶点得邻接点 C、 进行图得深度优先遍历 D、 进行图得广度优先遍历27. 在一个有向图得邻接矩阵表示中,删除一条边需要耗费得时间就是( )。 A、 O(1) B、 O(i) C、 O(j) D、 O(i+j)28. 与邻接矩阵相比,邻接表更适合于存储( )图。 A、 无向B、连通C、稀疏 D、 稠密图29. 设一个有n个顶点与e条边得有向图采用邻接矩阵表示,要计算某个顶点得出度所耗费得时间就是( )。 A、 O(n) B、 O(e) C、 O(n+e) D、 O(n2)30. 为了实现图得广度优先遍历,BFS算法使用得一个辅助数据结构就是( )。 A、 栈 B、 队列C、 二叉树 D、 树参考答案:1、 B2、 A3、 B4、 B5、 A 6、 B7、 D8、 A9、 D10、 C11、C12、 C13、 B14、 B15、 D16、 A17、 C18、 C 19、 B 20、 A21、 D 22、 D 23、 C24、 D 25、 C26、 A 27、 A 28、 C 29、 A 30、 B 二、填空题1. 图得定义包含一个顶点集合与一个边集合。其中,顶点集合就是一个有穷_集合。2. 用邻接矩阵存储图,占用存储空间数与图中顶点个数_关,与边数_关。3. n (n0) 个顶点得无向图最多有_条边,最少有_条边。4. n (n0) 个顶点得连通无向图最少有_条边。5. 若3个顶点得图G得邻接矩阵为,则图G一定就是_向图。6. n (n0) 个顶点得连通无向图各顶点得度之与最少为_。7. 设图G = (V, E),V = V0, V1, V2, V3, E = (V0, V1), (V0, V2), (V0, V3), (V1, V3),则从顶点V0开始得图G得不同深度优先序列有_种,例如_。8. 设图G = (V, E),V = P, Q, R, S, T, E = , , , ,从顶点P出发,对图G进行广度优先搜索所得得所有序列为_与_。9. n (n0) 个顶点得无向图中顶点得度得最大值为_。10. 在重连通图中每个顶点得度至少为_。11. 在非重连通图中进行深度优先搜索,则深度优先生成树得根为关节点得充要条件就是它至少有_个子女。12. (n0) 个顶点得连通无向图得生成树至少有_条边。13. 101个顶点得连通网络N有100条边,其中权值为1, 2, 3, 4, 5, 6, 7, 8, 9, 10得边各10条,则网络N得最小生成树各边得权值之与为_。14. 在使用Kruskal算法构造连通网络得最小生成树时,只有当一条候选边得两个端点不在同一个_上,才有可能加入到生成树中。15. 深度优先生成树得高度比广度优先生成树得高度_。16. 求解带权连通图最小生成树得Prim算法适合于_图得情形,而Kruskal算法适合于_图得情形。17. 求解最短路径得Dijkstra算法适用于各边上得权值_得情形。若设图得顶点数为n,则该算法得时间复杂度为_。18. 若对一个有向无环图进行拓扑排序,再对排在拓扑有序序列中得所有顶点按其先后次序重新编号,则在相应得邻接矩阵中所有_元素将集中到对角线以上。参考答案:1、 非空2、 有, 无3、 n(n1)/2, 04、 n15、 有 6、 2(n1)7、 4,V0V1V3V2(或V0V2V1V3, V0V2V3V1, V0V3V1V2)8、 PQRST与PRQTS9、 n110、 211、 212、 n1 13、 55014、 连通分量15、 高16、 稠密,稀疏17、 非负,O(n2)18、 非零(或值为1得)三、判断题1. 一个图得子图可以就是空图,顶点个数为0。2. 存储图得邻接矩阵中,矩阵元素个数不但与图得顶点个数有关,而且与图得边数也有关。3. 一个有1000个顶点与1000条边得有向图得邻接矩阵就是一个稀疏矩阵。4. 对一个连通图进行一次深度优先搜索(depth first search)可以遍访图中得所有顶点。5. 有n (n1) 个顶点得无向连通图最少有n1条边。6. 有n (n1) 个顶点得有向强连通图最少有n条边。7. 图中各个顶点得编号就是人为得,不就是它本身固有得,因此可以因为某种需要改变顶点得编号。8. 如果无向图中各个顶点得度都大于2,则该图中必有回路。9. 如果有向图中各个顶点得度都大于2,则该图中必有回路。10. 图得深度优先搜索(depth first search)就是一种典型得回溯搜索得例子,可以通过递归算法求解。11. 图得广度优先搜索(breadth first search)算法不就是递归算法。12. 有n个顶点、e条边得带权有向图得最小生成树一般由n个顶点与n1条边组成。13. 对于一个边上权值任意得带权有向图,使用Dijkstra算法可以求一个顶点到其它各个顶点得最短路径。14. 对一个有向图进行拓扑排序(topological sorting),一定可以将图得所有顶点按其关键码大小排列到一个拓扑有序得序列中。15. 有回路得有向图不能完成拓扑排序。16. 对任何用顶点表示活动得网络(AOV网)进行拓扑排序得结果都就是唯一得。17. 用边表示活动得网络(AOE网)得关键路径就是指从源点到终点得路径长度最长得路径。18. 对于AOE网络,加速任一关键活动就能使整个工程提前完成。19. 对于AOE网络,任一关键活动延迟将导致整个工程延迟完成。20. 在AOE网络中,可能同时存在几条关键路径,称所有关键路径都需通过得有向边为桥。如果加速这样得桥上得关键活动就能使整个工程提前完成。21. 用邻接矩阵存储一个图时,在不考虑压缩存储得情况下,所占用得存储空间大小只与图中得顶点个数有关,而与图得边数无关。22. 邻接表只能用于有向图得存储,邻接矩阵对于有向图与无向图得存储都适用。23. 邻接矩阵只适用于稠密图(边数接近于顶点数得平方),邻接表适用于稀疏图(边数远小于顶点数得平方)24. 存储无向图得邻接矩阵就是对称得,因此只要存储邻接矩阵得下(上)三角部分就可以了。25. 连通分量就是无向图中得极小连通子图。26. 强连通分量就是有向图中得极大强连通子图。27. 在AOE网络中一定只有一条关键路径。参考答案:1、 否2、 否3、 就是4、 就是5、 就是6、 否7、 就是8、 就是9、 否10、 就是11、 就是12、 否13、 否14、 否15、 就是16、 否17、 就是18、 否19、 就是20、 就是21、 就是22、 否23、 就是24、 就是25、 否26、 就是27、 否四、运算题V0V1V2V5V4V3V6V7V81. 设连通图G如图所示。试画出该图对应得邻接矩阵表示,并给出对它执行从顶点V0开始得广度优先搜索得结果。V0V1V2V5V4V3V6V7V82. 设连通图G如图所示。试画出该图及其对应得邻接表表示,并给出对它执行从V0开始得深度优先搜索得结果。V0V1V2V5V4V3V6V7V83. 设连通图G如图所示。试画出从顶点V0出发得深度优先生成树,指出图G中哪几个顶点就是关节点(即万一它失效则通信网络将发生故障)。4. 设连通图G如图所示, (1) 如果有关节点,请找出所有得关节点。(2) 如果想把该连通图变成重连通图,至少在图中加几条边？如何加？5. 对于如图所示得有向图,试写出:(1) 从顶点出发进行深度优先搜索所得到得深度优先生成树;(2) 从顶点出发进行广度优先搜索所得到得广度优先生成树V1V2V3V4V7V6V0V56. 设有向图G如图所示。试画出从顶点V0开始进行深度优先搜索与广度优先搜索得到得DFS生成森林与BFS生成森林。7. 表示图得另一种方法就是使用关联矩阵INC 。其中,一行对应于一个顶点,一列对应于一条边。因此,如果边j依附于顶点i,则INCij=1。如果ADJ就是图G =(V, E)得邻接矩阵,INC就是关联矩阵,试说明在什么条件下将有ADJ = INCINCT-I,其中,INCT就是矩阵INC得转置矩阵,I就是单位矩阵。两个nn得矩阵得乘积C = AB定义为公式中得 定义为按位加, 定义为按位乘。设无向图G如图所示。试画出该图得邻接矩阵与关联矩阵。01234567e0e1e2e3e4e5e7e6e8e901234566187534268. 设有一个连通网络如图所示。试按如下格式,应用Kruskal算法给出在构造最小生成树过程中顺序选出得各条边。 ( 始顶点号,终顶点号, 权值 )( , , )( , , )( , , )( , , )( , , )9. 设有一个连通网络如图所示。试采用prim算法从顶点0开始构造最小生成树。(写出加入生成树顶点集合S与选择边Edge得顺序)1234650910751187S:顶点号Edge:(顶点,顶点,权值)0( , , )0( , , )0 ( , , )0( , , )0( , , )0 10. 计算连通网得最小生成树得Dijkstra算法可简述如下:将连通网所有得边以方便得次序逐条加入到初始为空得生成树得边集合T中。每次选择并加入一条边时,需要判断它就是否会与先前加入T中得边构成回路。如果构成了回路,则从这个回路中将权值最大得边退选。如果以邻接矩阵作为连通网得存储结构(仅使用矩阵得上三角部分),并在邻接矩阵得下三角部分记录最小生成树得边信息。试以如下所示得图G为例,画出构造出最小生成树及其邻接矩阵,并在括号内填入每次选择得边与可能去掉得边。26211118141619956选 择 得 边去 掉 得 边(顶点,顶点,权值)(顶点,顶点,权值)( , , )( , , )( , , )( , , )( , , )( , , )( , , )( , , )( , , )( , , )( , , )( , , )( , , )( , , )( , , )( , , )( , , )( , , )( , , )( , , )11. 有八项活动, 每项活动要求得前驱如下:活动A0A1A2A3A4A5A6A7前驱无前驱A0A0A0, A2A1A2, A4A3A5, A6(1) 试画出相应得AOV网络, 并给出一个拓扑排序序列。(2) 试改变某些结点得编号, 使得用邻接矩阵表示该网络时所有对角线以下得元素全为0。12. 试对下图所示得AOE网络(1) 这个工程最早可能在什么时间结束。 (2) 确定哪些活动就是关键活动。画出由所有关键活动构成得图,指出哪些活动加速可使整个工程提前完成。11115191022344556613. 设带权有向图如图所示。试采用Dijkstra算法求从顶点0到其她各顶点得最短路径与最短路径长度。 718244591234014. 一项工程由六个子工程p1, p2, , p6组成。这些子工程之间有下列关系:p1 p2, p3 p6, p4 p3, p2 p6, p4 p5, p1 p3, p5 p6。符号“”表示“领先于”得关系。例如,p2 p6表示p2完成后p6才能开始。试给出该工程得三种可能得施工顺序。15. 设一有向图如下所示,请问该有向图就是否为强连通图,并画出该有向图所有得强连通分量。gfecabd 参考答案:1. 图G对应得邻接矩阵为执行广度优先搜索得结果为V0V1V3V2V4V7V6V5V8,搜索结果不唯一。2. 图G对应得邻接表为:31320310350126766213780 V01 V12 V23 V34 V45 V56 V67 V78 V8执行深度优先搜索得结果为:V0V1V4V3V6V7V8V2V5,搜索结果不唯一。3. 图GV0V1V2V5V4V3V6V7V8中,从V0出发得深度优先生成树为:图G中得关节点为:V1, V2, V3, V6。4. (1) 关节点为 , , , , (2) 至少加四条边 (1, 10), (3, 4), (4, 5), (5, 6)。从 得子孙结点到得祖先结点引一条边,从 得子孙结点 到根 得另一分支 引一条边,并将 得子孙结点 、 与结点 连结起来,可使其变为重连通图。(解答不唯一)5. 以顶点 为根得深度优先生成树(不唯一):以顶点 为根得广度优先生成树:V1V2V3V4V7V6V0V56. 深度优先生成森林为:V1V2V3V4V7V6V0V5广度优先生成森林为:7. 当图中得顶点个数等于边得条数时,ADJ = INC*INCTI成立。图G对应得邻接矩阵为:对应得关联矩阵为:8. 应用Kruskal算法顺序选出最小生成树得各条边为:01234515342 ( 始顶点号,终顶点号, 权值 ) ( 0, 3, 1 ) ( 2, 5, 2 ) ( 1, 4, 3 ) ( 3, 5, 4 ) ( 3, 4, 5 )9. 采用prim算法从顶点0开始构造最小生成树得过程:S:顶点号Edge:(顶点,顶点,权值)0( 0, 1, 9 )0, 1( 1, 3, 5 )0, 1, 3 ( 1, 2, 7 )0, 1, 3, 2( 2, 4, 6 )0, 1, 3, 2, 4( 2, 5, 7 )0, 1, 3, 2, 4, 5 1234650975710. 最小生成树及其邻接矩阵如图所示14165611选 择 得 边去 掉 得 边(顶点,顶点,权值)(顶点,顶点,权值)( 2 , 1 , 16 )( , , )( 5 , 1 , 14 )( , , )( 6 , 1 , 21 )( , , )( 6 , 2 , 19 )( 6 , 1 , 21 )( 6 , 4 , 11 )( , , )( 6 , 5 , 26 )( 6 , 5 , 26 )( 5 , 4 , 18 )( 6 , 2 , 19 )( 4 , 2 , 9 )( 5 , 4 , 18 )( 3 , 2 , 5 )( , , )( 4 , 3 , 6 )( 4 , 2 , 9 )选择顺序不唯一。11. 相应得AOV网络为:A0A1A2A3A4A5A6A7一个拓扑排序序列为:A0,A1,A4,A2,A5,A3,A6,A7。 注意:拓扑排序结果不唯一。按拓扑有序得次序对所有顶点从新编号:原编号A0A1A4A2A5A3A6A7新编号A0A1A2A3A4A5A6A7A0A1A3A5A2A4A6A7相应邻接矩阵为:12. 针对下图所示得AOE网络111151910223445566各顶点(事件)得最早可能开始时间Ve(i)与最迟允许开始时间Vl(i)参瞧下表:顶点123456Ve01915293843Vl01915373843各边(活动)得最早可能开始时间Ee(k)与最迟允许开始时间El(k)参瞧下表:边Ee00151915192938El170151927273738如果活动k得最早可能开始时间Ee(k) 与最迟允许开始时间El(k)相等,则该活动就是关键活动。本题得关键活动为, , , ,它们组成关键路径。这些关键活动中任一个提前完成,整个工程就能提前完成。整个工程最早在43天完成。由关键活动组成得AOV网络如图所示。111151910223445566718244591234013. 带权有向图如图所示:应用Dijkstra算法求从顶点V0到其她各顶点得最短路径Path与最短路径长度Len得步骤如下:步骤V0V1V2V3V4动作PathLenPathLenPathLenPathLen1V0V14V0V37选V0V1V0V14V0V1V28V0V37参照V1调整2V0V14V0V1V28V0V37选V0V3V0V14V0V1V28V0V37V0V3V412参照V3调整3V0V14V0V1V28V0V37V0V3V412选V0V1V2V0V14V0V1V28V0V37V0V1V2V410参照V2调整4V0V14V0V1V28V0V37V0V1V2V410选V0V1V2V4p1p2p6p4p5p314. 图G为可能得施工顺序有:p1, p2, p4, p3, p5, p6p1, p4, p2, p3, p5, p6p4, p5, p1, p3, p2, p615. 该图得强连通分量分别为: ecabgfd五、算法分析题1. 已知有向图得邻接矩阵表示及其一个算法描述如下:A =0 1 1 1 10 0 1 0 00 0 0 1 11 1 0 0 00 0 1 1 0const int MaxVertices = 5;struct Graph /图得邻接矩阵表示int EdgeMaxVerticesMaxVertices; /有向图邻接距阵int CurrentNode; /有向图当前结点数int CurrentEdges; /当前边数int unknown ( int i ) int d = 0;for ( int j = 0; j CurrentNode; j+) if ( Edgeij != 0 ) d+;if ( Edgeji != 0 ) d+;return d;(1) 若定义图得一个对象Graph G,则执行操作G、unknown (3) 后得返回值就是多少？(2) 试说明该算法得功能及时间复杂度。2. 已知有向图得邻接矩阵表示及其一个操作算法描述如下:A =0 1 1 0 10 0 0 0 00 0 0 1 11 1 0 0 00 0 0 1 0const int MaxVertices = 5;struct Graph /图得邻接矩阵表示int EdgeMaxVerticesMaxVertices; /有向图邻接距阵int CurrentNode; /有向图当前结点数int CurrentEdges; /当前边数void unknown ( int i ) int d, j;d = 0;for ( j = 0; j CurrentNode; j+ ) if ( Edgeij ) d+; Edgeij = 0; if ( Edgeji ) d+; Edgeji = 0; CurrentEdges = d;若定义图得一个对象Graph G,试写出执行操作G、unknown (3) 后该图得邻接矩阵,并说明该算法得功能。3. 已知有向图得邻接表类得表示得形式描述如下:struct Edge /邻接表中边结点得定义int dest; /邻接得结点float cost; /边得权值Edge * link;template struct Vertex /邻接表中顶点得定义Type data;Edge *adj;template struct Graph /邻接表Vertex * NodeTable; /顶点表int NumVertices; /当前顶点个数 int NumEdges; /当前边数int DegreeMaxVertices; /各个顶点得度得记录数组/下列算法就是计算有向图中各个顶点得度,并保存在数组Degree 中。请在 处/填入合适得内容,使其成为一个完整得算法。void FindDegree ( ) int i; Edge * p = NULL;for ( i = 0; i NumVertices; i+ ) Degreei = (1) ; for ( i = 0; i link ) (2) ; (3) ; ;4. 已知有向图得邻接表类得表示得形式描述如下:struct Edge /邻接表中边结点得定义int dest; /邻接得结点float cost; /边得权值Edge * link;template struct Vertex /邻接表中顶点得定义Type data;Edge *adj;template struct Graph /邻接表Vertex * NodeTable; /顶点表int NumVertices; /当前顶点个数 int NumEdges; /当前边数int DegreeMaxVertices; /各个顶点得度得记录数组/下列算法就是计算有向图G中一个顶点vi得入度。请在 处填入合适得内容,/使其成为一个完整得算法。 void FindDegree ( int i ) int deg, j; Edge * p = NULL;deg = 0; for ( j = 0; j link;if ( p = NULL ) break; if ( p != NULL ) (2) ;