?011???
25、设图的邻接矩阵为?001?,则该图为( )。
?010???
A. 有向图 B. 无向图 C. 强连通图 D. 完全图 27、任何一个无向连通图的最小生成树( )种。
A. 只有一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在
29、对于一个有向图,若一个顶点的入度为k1,、出度为k2,则对应邻接表中该顶点单链表中的结点数为( )。
A. k1 B. k2 C. k1+k2 D. k1-k2 30、一个具有8个顶点的有向图中,所有顶点的入度之和与所有顶点的出度之和的差等于( )。
A. 16 B. 4 C. 0 D. 2 31、无向图中一个顶点的度是指图中( )。
A. 通过该顶点的简单路径数 B. 与该顶点相邻接的顶点数 C. 与该顶点连通的顶点数 D. 通过该顶点的回路数
二、填空题
1、n个顶点的连通图至少有 边。 答案:n-1条
2、一个连通图的生成树是一个 ,它包含图中所有顶点,但只有足以构成一棵树的n-1条边。
答案:极小连通子图
4、遍历图的基本方法有深度优先搜索和广度优先搜索,其中 是一个递归过程。 答案:深度优先搜索
5、在无向图G的邻接矩阵A中,若A[i][j]等于1,则A[j][i]等于 。 答案:1
6、判定一个有向图是否存在回路,可以利用 。 答案:拓扑排序
7、已知一个图的邻接矩阵表示,计算第i个结点的入度的方法是 。 答案:邻接矩阵中第i列非0元素的个数
8、n个顶点的无向图最多有 边。 答案:n*(n-1)/2
9、已知一个图的邻接矩阵表示,删除所有从第i个结点出发的边的方法是 。 答案:将邻接矩阵中第i行所有元素的值置为0
10、若以邻接矩阵表示有向图,则邻接矩阵上第i行中非零元素的个数即为顶点vi的 。 答案:第i个结点的出度
三、判断题
1、图的连通分量是无向图的极小连通子图。 ? 2、一个图的广度优先生成树是惟一的。?
3、图的深度优先遍历序列和广度优先遍历序列不是惟一的。?
4、邻接表只能用于存储有向图,而邻接矩阵则可存储有向图和无向图。?
5、存储图的邻接矩阵中,邻接矩阵的大小不但与图的顶点个数有关,而且与图的边数也有关。? 7、从源点到终点的最短路径是唯一的。? 9、图的生成树是惟一的。?
17
四、综合题
1、已知图G的邻接矩阵如下所示:
(1)求从顶点1出发的广度优先遍历序列;
(2)根据prim算法,求图G从顶点1出发的最小生成树,要求表示出其每一步生成过程。(用图或者表的方式均可)。
???615????6?5?3??????15?564???5?5??2? ????36??6?????426????答案:(1)广度优先遍历序列:1; 2, 3, 4; 5; 6 (2)最小生成树(prim算法)
11111111121233335353544446426426426
2、设一个无向图的邻接矩阵如下图所示: (1)画出该图;
(2)画出从顶点0出发的深度优先生成树;
??011100??101000???110110???101011?
???001101???000110???答案: (1)图形态 (2)深度优先搜索树
010132325454
3、写出下图中全部可能的拓扑排序序列。 123456答案:1,5,2,3,6,4 1,5,6,2,3,4 5,1,2 ,3,6,4
5,1,6,2,3,4 5,6,1,2,3,4
18
4、AOE网G如下所示,求关键路径。(要求标明每个顶点的最早发生时间和最迟发生时间,每条边的最早发生时间和最迟发生时间并画出关键路径)
3v1v43222v0v3v524v2 答案:(1)顶点的最早发生时间和最迟发生时间: (3)关键路径:
顶点v0v1v2v3v4v5ve032668vl032668v02v3v2432v13v42v53
(2)边的最早发生时间和最迟发生时间 e l e==l 边 ? V0-v1 0 0 ? V0-v2 0 0 V1-v3 3 1 ? V1-v4 3 3 ? V2-v3 2 2 V2-v5 2 5 ? V3-v5 6 6 ? V4-v5 6 6
5、已知图G如下所示,根据Prim算法,构造最小生成树。(要求给出生成过程)
v08v2242v6v3756v448v17v58v7
答案:prim算法求最小生成树如下:
v0v06v44v57v6v22v06v44v57v6v22v06v44v5v32 v06v47v6v224v5v32v67v06v45v7v224v5v327v6v06v45v74v17v56v4
6、已知有向图如下所示,请写出该图所有的拓扑序列。
19
v2v3v1v4v5v8v6v7
答案:拓扑排序如下:
v1, v2, v4, v6, v5, v3, v7, v8 v1, v2, v4, v6, v5, v7, v3, v8 v1, v2, v6, v4, v5, v3, v7, v8 v1, v2, v6, v4, v5, v7, v3, v8 v1, v6, v2, v4, v5, v3, v7, v8 v1, v6, v2, v4, v5, v7, v3, v8 7、如下图所示的AOE网,求:
(1)求事件的最早开始时间ve和最迟开始时间vl,并求边的最早时间和最迟时间;
事件 1 2 3 4 5 6 7 8 9 Ve Vl (2)求出关键路径; V2a1a416a24a35V4a62V6V3a94a51V5a79a87V8a114V9汇点V7a102 V1源点
答案:(1)求ve和vl (2)关键路径
事件vevl100*266*346458577*671071616*81414*91818*v16v21v57v849v72v9
(1)边的最早发生时间和最迟发生时间 e l e==l ? 0 0 0 2 0 3 ? 6 6 4 6 5 8 ? 7 7 ? 7 7 7 10 ? 16 16 ? 14 14 边 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11
8、如下所示的有向图,回答下面问题:
20