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

1、第七章 图 试题7、单项选择题）的数目。C. 权D. 权值1. 在无向图中定义顶点的度为与它相关联的（A. 顶点 B. 边2. 在无向图中定义顶点 v i 与 vj 之间的路径为从v i 到达 v j 的一个（ ） 。A. 顶点序列 B. 边序列 C. 权值总和 D. 边的条数3. 图的简单路径是指（A. 权值）不重复的路径。B. 顶点C. 边D. 边与顶点均4. 设无向图的顶点个数为A. n-1n ，则该图最多有（B. n（n-1）/2)条边。C. n(n+1)/2D. n(n-1)5. n 个顶点的连通图至少有（ ）条边。A. n-1B. nC. n+1D. 06. 在一个无向图中，所有顶

2、点的度数之和等于所有边数的 （）A. 3B. 2C. 1倍。D. 1/27. 若采用邻接矩阵法存储一个n 个顶点的无向图，则该邻接矩阵是一个（）A. 上三角矩阵B. 稀疏矩阵8. 图的深度优先搜索类似于树的（A. 先根B. 中根9. 图的广度优先搜索类似于树的（A. 先根B. 中根C. 对角矩阵D. 对称矩阵）次序遍历。C. 后根D. 层次）次序遍历。C. 后根D. 层次10. 在 用 Kruskal 算法求解带权连通图的最小（代价）生成树时，通常采用一个（）辅助结构，判断一条边的两个端点是否在同一个连通分量上。A. 位向量B. 堆C. 并查集D. 生成树顶点集合11. 在 用 Kruskal

3、在图中构成（A. 重边12. 在 用 Dijkstra()。A. 非零算法求解带权连通图的最小（代价）生成树时，选择权值最小的边的原则是该边不能）。B. 有向环C. 回路D. 权值重复的边算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是C. 非整C. 非负 D. 非正13. 在 一个连通图中进行深度优先搜索得到一棵深度优先生成树，树根结点是关节点的充要条件是它至少有（ ）子女。A. 1B. 2C. 3D. 015.设有向图有n个顶点和( )。A. O(nlog 2e)16.设 G1=(V1,E1) 和 G2 = (V2,E2)A. G1 是G2的子图C. G1 是G2的连通分

4、量为两个图，如果 V1 V2 , E1 E2 ,则称(B. G2 是G1的子图D. G2是G1的连通分量14.设有向图有n个顶点和e条边，采用邻接表作为其存储表示，在进行拓扑排序时，总的计算时间为 ( )。A.O(nlog2e)B.O(n+e)C.O(ne)D.O(n 2)e条边，采用邻接矩阵作为其存储表示，在进行拓扑排序时，总的计算时间为B.O(n+e)C.O(ne)D.O(n 2)。B.出度D.(入度+出度)/217. 有向图的一个顶点的度为该顶点的(A.入度C.入度与出度之和18. 一个连通图的生成树是包含图中所有顶点的一个()子图。A.极小B.连通C.极小连通D.无环19. n (n

5、1)个顶点的强连通图中至少含有()条有向边。A. n-1B. nn(n-1)/2D. n(n-1)20. 在一个带权连通图 G中，权值最小的边一定包含在6的()生成树中。A.某个最小B.任何最小C.广度优先D.深度优先21. 对于具有e条边的无向图，它的邻接表中有()个边结点。A.e-1B. eC.2(e-1)D. 2e22. 对于如图所示的带权有向图，从顶点 1到顶点5的最短路径为()。A.1,4,5B.1,2,3,5C.1,4,3,5D. 1,2,4, 3,523. 具有n个顶点的有向无环图最多可包含()条有向边。A.n-1B. nC.n(n-1)/2D.n(n-1)24. 一个有n个顶点

6、和n条边的无向图一定是()。A.连通的 B.不连通的C.无环的D.有环的25. 在n个顶点的有向无环图的邻接矩阵中至少有()个零元素。A. nB.n(n-1)/2C. n(n+1)/2D. n(n-1)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

7、. 设 一个有 n 个顶点和 e 条边的有向图采用邻接矩阵表示，要计算某个顶点的出度所耗费的时间是()。A. O(n)B. O(e)C. O(n+e)D. O(n 2)30. 为 了实现图的广度优先遍历， BFS 算法使用的一个辅助数据结构是( ) 。A.栈B. 队列C. 二叉树D. 树参考答案：1. B2. A3. B4. B5. A6. B7. D8. A9. D10. C11.C12. C13. B14. B15. D16. A17. C18. C19. B20. A21. D22. D23. C24. D25. C26. A27. A28. C29. A30. B二、填空题1. 图的定

8、义包含一个顶点集合和一个边集合。其中，顶点集合是一个有穷 集合。2. 用邻接矩阵存储图，占用存储空间数与图中顶点个数 关，与边数 关。3. n (n 0)个顶点的无向图最多有 条边，最少有 条边。4. n (n 0)个顶点的连通无向图最少有 条边。0101005. 若3个顶点的图G的邻接矩阵为 01 0 ,则图G一定是 向图。6. n (n 0)个顶点的连通无向图各顶点的度之和最少为 。7. 设图 G = (V, E) ， V = V0, V1, V2, V3, E = (V0, V1), (V0, V2), (V0, V3), (V1,V3) ，则从顶点 V0 开始的图 G 的不同深度优先序

9、列有 种，例如 8. 设图 G = (V, E) ， V = P, Q, R, S, T, E = , , , 从顶点 P 出发，对图 G 进行广度优先搜索所得的所有序列为 和9. n (n 0)个顶点的无向图中顶点的度的最大值为 。10. 在 重连通图中每个顶点的度至少为 。11. 在 非重连通图中进行深度优先搜索，则深度优先生成树的根为关节点的充要条件是它至少有 个子女。12. (n0)个顶点的连通无向图的生成树至少有 条边。13. 1 01 个顶点的连通网络N 有 100 条边，其中权值为 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 的边各10 条，则网络N 的最小生成树

10、各边的权值之和为 。14. 在 使用 Kruskal算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个 上，才有可能加入到生成树中。15. 深 度优先生成树的高度比广度优先生成树的高度 。16. 求 解带权连通图最小生成树的 Prim 算法适合于 图的情形，而Kruskal 算法适合于 图的情形。17. 求解最短路径的 Dijkstra 算法适用于各边上的权值 的情形。若设图的顶点数为 n ，则该算法的时间复杂度为 。18. 若 对一个有向无环图进行拓扑排序，再对排在拓扑有序序列中的所有顶点按其先后次序重新编号，则在相应的邻接矩阵中所有 元素将集中到对角线以上。参考答案： 1

11、. 非空2. 有, 无3. n(n-1)/2, 04. n-15. 有6. 2(n-1)7. 4 ， V0V1V3V2 (或 V0V2V1V3, V0V2V3V1, V0V3V1V2 )8. PQRST 和 PRQTS11. 214. 连通分量17. 非负， O(n2)9. n-110. 212. n-113. 55015. 高16. 稠密，稀疏18. 非零(或值为 1 的)三、判断题1. 一个图的子图可以是空图，顶点个数为 0 。2. 存储图的邻接矩阵中，矩阵元素个数不但与图的顶点个数有关，而且与图的边数也有关。3. 一个有 1000 个顶点和 1000 条边的有向图的邻接矩阵是一个稀疏矩阵

12、。)可以遍访图中的所有顶点。4. 对一个连通图进行一次深度优先搜索( depth first search5. 有n（n 1）个顶点的无向连通图最少有n-1条边。6. 有n（n 1）个顶点的有向强连通图最少有n条边。7. 图中各个顶点的编号是人为的，不是它本身固有的，因此可以因为某种需要改变顶点的编号。8. 如果无向图中各个顶点的度都大于2 ，则该图中必有回路。9. 如果有向图中各个顶点的度都大于2 ，则该图中必有回路。10. 图 的深度优先搜索（ depth first search ）是一种典型的回溯搜索的例子，可以通过递归算法求 解。）算法不是递归算法。11. 图 的广度优先搜索（ br

13、eadth first searchn 个顶点和 n-1 条边组成。算法可以求一个顶点到其它各个顶点的最短路） ，一定可以将图的所有顶点按其关键码大小12. 有 n 个顶点、 e 条边的带权有向图的最小生成树一般由13. 对 于一个边上权值任意的带权有向图，使用 Dijkstra径。14. 对 一个有向图进行拓扑排序（topological sorting排列到一个拓扑有序的序列中。15. 有 回路的有向图不能完成拓扑排序。16. 对任何用顶点表示活动的网络（ AOV 网）进行拓扑排序的结果都是唯一的。17. 用 边表示活动的网络（ AOE 网）的关键路径是指从源点到终点的路径长度最长的路径。

14、18. 对 于 AOE 网络，加速任一关键活动就能使整个工程提前完成。19. 对 于 AOE 网络，任一关键活动延迟将导致整个工程延迟完成。20. 在 AOE 网络中，可能同时存在几条关键路径，称所有关键路径都需通过的有向边为桥。如果加速这样的桥上的关键活动就能使整个工程提前完成。21. 用 邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。22. 邻 接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。23. 邻 接矩阵只适用于稠密图 （边数接近于顶点数的平方） ， 邻接表适用于稀疏图 （边数远小于顶点数的平 方）24

15、. 存 储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的下（上）三角部分就可以了。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.否四、运算题1.设连通图G如图所示。试画出该图对应的邻接矩阵表示，并给出对它执行从顶点V0开始的广度优先搜索的结果。2.设连通图G如图所示。试画出该图及其对应的邻接表表示，并给出

16、对它执行从V0开始的深度优先搜索的结果。3.设连通图G如图所示。试画出从顶点V0出发的深度优先生成树,指出图G中哪几个顶点是关节点(即万一它失效则通信网络将发生故障)28. 连通图G如图所示，(1)如果有关节点，请找出所有的关节点。(2)如果想把该连通图变成重连通图，至少在图中加几条边？如何加?29. 于如图所示的有向图，试写出：(1)从顶点出发进行深度优先搜索所得到的深度优先生成树;(2)从顶点出发进行广度优先搜索所得到的广度优先生成树2830. 有向图G如图所示。试画出从顶点 V0开始进行深度优先搜索和广度优先搜索得到的DFS生成森林和BFS生成森林。7.表示图的另一种方法是使用关联矩阵

17、因此，如果边j依附于顶点i ,则 是关联矩阵，试说明在什么条件下将有INCINCij=1ADJ = INCO其中，一行对应于一个顶点，一列对应于一条边。如果ADJ是图G= (V,E )的邻接矩阵，INC INCT I ,其中，INCT是矩阵INC的转置矩阵，I是单位矩阵。两个 n n的矩阵的乘积 C = A B定义为 n 1Cijaik bkjk 0公式中的 定义为按位加，定义为按位乘。设无向图G如图所示。试画出该图的邻接矩阵和关联矩阵。算法给出在构造最小生成树过程中顺序8.设有一个连通网络如图所示。试按如下格式，应用 Kruskal 选出的各条边。3 5)42权值）（始顶点号，终顶点号，（，

18、）（，）（，）（，）（，）9.设有一个连通网络如图所示。试采用prim算法从顶点。开始构造最小生成树。（写出加入生成树顶点 集合S和选择边Edge的顺序）S顶点号Edge（顶点，顶点，权值）0(,)0(,)0(,)0(,)0(,)010.计算连通网的最小生成树的Dijkstra算法可简述如下：将连通网所有的边以方便的次序逐条加入到初始为空的生成树的边集合 T中。每次选择并加入一条边时，需要判断它是否会与先前加入 T中的边 构成回路。如果构成了回路，则从这个回路中将权值最大的边退选。如果以邻接矩阵作为连通网的存储结构（仅使用矩阵的上三角部分），并在邻接矩阵的下三角部分记录最小生成树的边信息。试以

19、如下所示的图G为例，画出构造出最小生成树及其邻接矩阵，并在括号内填入每次选择的边和可能去掉的边。0 160Edge14 215919060 18 110260选择的边掉的（顶点, 顶权值）（顶点,顶权值）与 八、,与 八、,(,)(,)(,)(,)(,)(,)(,)(,)(,)(,)(,)(,)(,)(,)(,)(,)(,)(,)(,)(,)11 .有八项活动，每项活动要求的前驱如下活动A0A1A2A3A4A5A6A7前驱无前 驱A0A0A0,A2A1A2,A4A3A5, A6(1) 试画出相应的AOV网络，并给出一个拓扑排序序列。(2)试改变某些结点的编号，使得用邻接矩阵表示该网络时所有对角

20、线以下的元素全为0。12 .试对下图所示的AOE网络(1) 这个工程最早可能在什么时间结束。(2)确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前 完成。13.设带权有向图如图所示。试采用Dijkstra算法求从顶点0到其他各顶点的最短路径和最短路径长度。14 . 一项工程由六个子工程p1, p2, p6 组成。这些子工程之间有下列关系：p1 p2, p3 p6,p4 p3, p2 p6, p4 p5, p1 p3, p5 p6。符号 表示领先于的关系。例如，p2 p6 表示p2完成后p6才能开始。试给出该工程的三种可能的施工顺序。15 .设一有向图如下所示

21、，请问该有向图是否为强连通图，并画出该有向图所有的强连通分量。参考答案1.图G对应的邻接矩阵为G.Edge0 1 11 0 01 0 01 1 10 1 00 0 10 0 00 0 00 0 01 0 01 1 01 0 10 0 00 0 00 0 01 0 01 0 00 0 00 0 00 0 00 0 01 1 00 0 00 0 00 1 11 0 01 0 0执行广度优先搜索的结果为V0V1V3V2V4V7V6V5V8 ,搜索结果不唯一。2 .图G对应的邻接表为:012345678执行深度优先搜索的结果为：V0V1V4V3V6V7V8V2V5 ,搜索结果不唯一。3 .图G中，从V

22、0出发的深度优先生成树为:图G中的关节点为:。从的子孙结点到的祖先结引一条边，并将的子孙结点、与4 . (1)关节点为，(2)至少加四条边(1, 10), (3, 4), (4, 5), (5, 6)点引一条边，从的子孙结点到根的另一分支结点连结起来，可使其变为重连通图。(解答不唯一)5.以顶点 为根的深度优先生成树（不唯一）6 .深度优先生成森林为：广度优先生成森林为：7 .当图中的顶点个数等于边 图G对应的邻接矩阵为：ADJ（2） qVoV2yQo V1 V4（o-oV 5V6V 7V2/%1V4foo6V5V6V7的条数时，ADJ = INC*INCT-I成立。0123456701100

23、0000100110001100001102010000013010000014001000015001000016000111107以顶点为根的广度优先生成树:对应的关联矩阵为:0 12 3110 010 110INC 00010001000100011000100010000000010001023450 10 0 0 100 11118.应用Kruskal算法顺序选出最小生成树的各条边为:权值）(0,3,1 )(2,5,2 )(1,4,3 )(3,5,4 )(3,4,5 )始顶点号，终顶点号,(9.采用prim算法从顶点0开始构造最小生成树的过程:10.最小生成树及其邻接矩阵如图所示16

24、0161421160591950660181114026110EdgeS顶点号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选择的边去掉的边（顶点，顶 权值） （顶点，顶 权值）(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)(

25、3 ,2 ,5)(,)(4 ,6)(4 ,2 ,9)3 ,选择顺序不唯一。11.相应的AOV网络为:一个拓扑排序序列为：A0,A1,A4,A2,A5,A3,A6,A7。 注意：拓扑排序结果不唯一。按拓扑有序的次序对所有顶点从新编号：原编号A0A1A4A2A5A3A6A7新编号A0A1A2A3A4A5A6A7相应邻接矩阵为:Edge0 12 3 40 10 100 0 10 00 0 0 0 1567100000010002010500 1600 07各顶点(事件)的最早可能开始时间Ve(i)和最迟允许开始时间Vl(i)参看下表:顶点123456Ve01915293843Vl0191537384

26、3各边(活动)的最早可能开始时间Ee(k)和最迟允许开始时间El(k)参看下表：边Ee00151915192938El170151927273738如果活动k的最早可能开始时间 Ee(k)与最迟允许开始时间El(k)相等，则该活动是关键活动。本题的关键活动为, , , ,它们组成关键路径。这些关键活动中任一个提前完成，整个工程就能提前完成。整个工程最早在43天完成。由关键活动组成的AOV网络如图所示。13.带权有向图如图所示:应用Dijkstra算法求从顶点V0到其他各顶点的最短路径Path和最短路径长度Len的步骤如下:步 骤V0V1V2V3V4动作PatherLIPatheL nPathe

27、iL1PatheL n1V0V14一ooV0V37一oo选 V0V1V0V14V0V1V28V0V37一oo参照V1调 整2V0V14V0V1V28V0V37一oo选 V0V3V0V14V0V1V28V0V37V0V3V412参照V3调 整3V0V14V0V1V28V0V37V0V3V412选 V0V1V2V0V14V0V1V28V0V37V0V1V2V410参照V2调 整4V0V14V0V1V28V0V37V0V1V2V410选V0V1V2V414 .图G为p2可能的施工顺序有：p1, p2, p4, p3, p5, p6p1, p4, p2, p3, p5, p6p4, p5, p1, p

28、3, p2, p615 .该图的强连通分量分别为:五、算法分析题1 .已知有向图的邻接矩阵表示及其一个算法描述如下:01111、001000001111000*00110，A =/图的邻接矩阵表示有向图邻接距阵/有向图当前结点数/当前边数const 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 ( Edg

29、e皿!= 0 ) d+;if ( Edgeji != 0 ) d+;return d;(1)若定义图的一个对象Graph G ,则执行操作 G.unknown (3)后的返回值是多少?(2)试说明该算法的功能及时间复杂度。2 .已知有向图的邻接矩阵表示及其一个操作算法描述如下:0 10 0A = 0 01 110 01 0 1、0 0 00 1 10 0 00 1 0 )const int MaxVertices = 5;/图的邻接矩阵表示有向图邻接距阵/有向图当前结点数/当前边数struct Graph int EdgeMaxVerticesMaxVertices; /int Current

30、Node;int CurrentEdges; void unknown ( int i ) int d, j;d = 0;for ( j = 0; j CurrentNode; j+ ) if ( Edgeij ) d+; Edge皿=0; if ( Edgeji ) d+; Edge皿=0; CurrentEdges -= d;后该图的邻接矩阵，并说明该算若定义图的一个对象Graph G，试写出执行操作 G.unknown法的功能。3 .已知有向图的邻接表类的表示的形式描述如下:4.struct Edge int dest; float cost;Edge * link;template s

31、truct Vertex Type data;Edge *adj;template struct Graph Vertex * NodeTable;int NumVertices;int NumEdges;int DegreeMaxVertices; / 邻接表中边结点的定义/ 邻接的结点/ 边的权值/ 邻接表中顶点的定义/ 邻接表/ 顶点表/ 当前顶点个数/ 当前边数/ 各个顶点的度的记录数组/ 下列算法是计算有向图中各个顶点的度，并保存在数组 Degree 中。请在处/ 填入合适的内容，使其成为一个完整的算法。void FindDegree ( ) int i; Edge * p = NU

32、LL;for ( i = 0; i NumVertices; i+ ) Degreei =(1);for ( i = 0; i link ) (2) ;(3) ; ;已知有向图的邻接表类的表示的形式描述如下:struct Edge int dest; float cost;/ 邻接表中边结点的定义/ 邻接的结点/ 边的权值;Edge * link;template struct Vertex / 邻接表中顶点的定义Type data;Edge *adj;template struct Graph / 邻接表Vertex * NodeTable; int NumVertices;int NumE

33、dges;/ 顶点表/ 当前顶点个数/ 当前边数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);return deg;处填入合适的内容，5. 已知有向图的邻接表类的表示的形式描述如下：struct Edge int dest; float co

34、st; Edge * link;/ 邻接表中边结点的定义/ 邻接的结点/ 边的权值;template struct Vertex Type data;Edge *adj;template struct Graph Vertex * NodeTable;int NumVertices;/ 邻接表中顶点的定义/ 邻接表/ 顶点表/ 当前顶点个数int NumEdges;/ 当前边数int DegreeMaxVertices;/ 各个顶点的度的记录数组/ 下列算法是从有向图 G 中删除所有以 vi 为弧头的有向边。请在处填入合适/ 的内容，使其成为一个完整的算法。void DeletEdge ( i

35、nt i ) int de = 0, j; Edge *p, *q;if ( i = NumVertices ) cout 错误输入 endl; exit (1); for ( j = 0; j link; if ( p != NULL ) if ( p != NodeTablej.adj ) q-link = p-link;else (2);delete p; de+;NumEdges = NumEdges - de;6.已知带权图的邻接矩阵表示和邻接表类表示的形式描述分别如下:(1) 邻接矩阵的定义#define INFINITY INT_MAXconst int MaxVertices

36、= 20;template struct AdjMatrix Type * NodeTable;float arrMaxverticesMaxVertices;int NumVertices;int NumEdges;(2) 邻接表定义struct Edge int dest;float cost;Edge * link;template struct Vertex Type data;Edge *adj;template struct AdjTable Vertex * NodeTable;int NumVertices;/INT_MAX 为最大整数，表示8/ 顶点表定义/ 邻接矩阵定义/

37、当前顶点个数/ 当前边数/ 邻接表中边结点的定义/ 邻接的结点/ 边的权值/ 邻接表中顶点的定义/ 邻接表/ 顶点表/ 当前顶点个数/ 当前边数处填入合适int NumEdges; / 下列算法是根据一个图的邻接矩阵建立该图的邻接表，请在/ 的内容，使其成为一个完整的算法。AdjTable * convertM ( ) / 将图的邻接矩阵(用 this 指针指示)转换为邻接表，函数返回邻接表的地址。AdjTable * A; Edge *e;A-NodeTable = new VertexNumVertices;A-NumEdges = NumEdges;A-NumVertices = Num

38、Vertices;for ( int i = 0; i NodeTablei.data = NodeTablei;A-NodeTablei.adj =(1);for ( int j = 0; j dest = j;e-cost= (2);e-link = A-NodeTablei.adj;(3);return A;7. 已知带权图的邻接矩阵表示和邻接表类表示的形式描述分别如下：(1) 邻接矩阵的定义#define INFINITY INT_MAXconst int MaxVertices = 20;template struct AdjMatrix Type * NodeTable;float

39、 arrMaxverticesMaxVertices;int NumVertices;int NumEdges;(2) 邻接表定义struct Edge int dest;float cost;Edge * link;template struct Vertex Type data;Edge *adj;template struct AdjTable Vertex * NodeTable;int NumVertices;int NumEdges;/INT_MAX 为最大整数，表示8/ 顶点表定义/ 邻接矩阵定义/ 当前顶点个数/ 当前边数/ 邻接表中边结点的定义/ 邻接的结点/ 边的权值/ 邻

40、接表中顶点的定义/ 邻接表/ 顶点表/ 当前顶点个数/ 当前边数/ 下列算法是根据一个图的邻接表存储结构建立该图的邻接矩阵存储结构，/ 请在处填入合适的内容，使其成为一个完整的算法AdjMatrix * convertAL( ) / 将图的邻接表(用 this 指针指示)转换为邻接矩阵，函数返回邻接矩阵的地址。AdjMatrix * A; int i, j;Edge *p;A-NodeTable = new VertexNumVertices;A-arr = new float MaxverticesMaxVertices;A-NumEdges = NumEdges;A-NumVertices

41、 = NumVertices;for ( i = 0; i NumVertices; i+ ) for ( j = 0; j arrij = INFINITY;A-NodeTablei = (1);for ( i = 0; i arrip-dest = (2);(3);8. 已知图的邻接表和逆邻接表的形式描述如下：struct Edge int dest;float cost;Edge * link;template struct Vertex Type data;Edge *adj;template struct Graph Vertex * NodeTable;Vertex * Oppos

42、itNodeTable;int NumVertices;int NumEdges;/ 结点定义/ 邻接结点/ 边的权值/ 顶点定义/ 邻接表与逆邻接表定义/ 邻接表顶点表/ 逆邻接表顶点表/ 当前顶点个数/ 当前边数/ 下列算法是根据一个图的邻接表存储结构建立该图的逆邻接表存储结构，请/ 在处填入合适的内容，使其成为一个完整的算法。void convertM ( ) int i; Edge *p, *q;OppositNodeTable = new VertexNumVertices;for ( i = 0; i NumVertices; i+ ) OppositNodeTablei.data

43、 = NodeTablei.data; OppositNodeTablei.adj = NULL;for ( i = 0; i dest = i;q-cost = p-cost;OppositNodeTablep-dest.adj = q;参考答案：1 . (1)执行操作后的返回值是5。/2 分(2)算法的功能是计算有向图中一个顶点的度。/2分算法的时间复杂度是 O(n) , n为图的顶点个数。/2 分2 .执行操作G.unknown (3) 后，图的邻接矩阵为：/3分10 110 1、00000000010000000000 J算法的功能是从图中删除所有与某个顶点相关的边。/3分3 .填空结果8.填空结果30 0/2(2) Degreep-dest+(3) Degreei+4 .填空结果(1) p != NULL & p-dest