图练习

一、选择题 1. 一个有n个顶点的无向图最多有（ ）条边。 A. n B. n(n-1) C.n(n-1)/2 D.2n C

2. 具有6个顶点的无向图至少应有（ ）条边才能确保是一个连通图。 A .5 B.6 C.7 D.8 A

3.具有n个顶点且每一对不同的顶点之间都有一条边的图被称为（ ） A.线性图 B.无向完全图 C.无向图 D.简单图 B

A 4.具有4个顶点的无向完全图有（ ）条边。 A.6 B.12 C.16 D.20

5.G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。 A.6 B.7 C.8 D.9 D

6.存储稀疏图的数据结构常用的是（ ） A.链接矩阵 B.三元组 C.链接表 D.十字链表 C

7.对一个具有n个顶点的图，采用链接矩阵表示则该矩阵的大小为（ ） A.n B.(n-1)2 C.(n+1)2 D.n2 D

8.设连通图G的顶点数为n，则G的生成树的边数为（ ） A.n-1 B.n C.2n D.2n-1 A

9.N个顶点的无向图的链接表中结点总数最多有（ ）个。 A.2n B.n C.n/2 D.n(n-1) D

A G 10.对于一个具有n个顶点和e条边的无向图，若采用链接表表示，则表向量的大小为（ ），所有顶点链接表的结点总数为（ ）。 A.n B.n+1 C.n-1 D.2n E.e/2 F.e G.2e H.n+e A G

B F G 11.从链接矩阵 可以看出，该图共有（ ）个顶点。如果是有向图，该图共有（ ）条弧；如果是有向图，则共有（ ）条边。 11.从链接矩阵 可以看出，该图共有（ ）个顶点。如果是有向图，该图共有（ ）条弧；如果是有向图，则共有（ ）条边。 A.9 B.3 C.6 D.1 E.5 F.4 G.2 H.0 B F G

C 12.在有向图的链接表存储结构中，顶点V在表结点中出现的次数是（ ） A.顶点v的度 B.顶点v的出度 C.顶点v的入度 D.依附于顶点v的边 C

13. 在用链接表表示图的情况下，建立图的算法的时间复杂度为（ ） A.O(n+e) B.O(n2) C.O(n*e) D.O(n3) A

A 14. 用DFS遍历一个无环有向图，并在DFS算法退栈返回时，打印出相应的顶点，则输出的顶点序列是（ ）。 A.逆拓扑有序的 B.拓扑有序的 C.无序的 A

15. 已知一个图如图7-13所示，若从顶点a出发按深度优先搜索法进行遍历，则可能得到的是一种顶点序列为（ ( 1 ) A.abecdf B.acfebd C.acebfd D.acfdeb ( 2 ) A.abcedf B.abcefd C.abedfc D.acfdeb D B a b c e d f 图7-13

B E 16. 采用链接矩阵时，遍历图时的顶点所需时间为（ ），采用链接表时，遍历图的顶点所需时间为（ ）（注：设图有n个顶点，e条边） A.O(n) B.O(n2) C.O(e) D.O(n*e) E.O(n+e)   B E

17. 采用链接表存储的图的深度优先搜索遍历算法类似于二叉树的（ ） A.中序遍历 B. 先序遍历 C. 后序遍历 D.按层遍历 B

18. 采用链接表存储的图的广度优先搜索遍历算法类似于二叉树的（ ） A.中序遍历 B.先序遍历 C. 后序遍历 D.按层遍历 D

C B 19. 已知一有向图的链接表存储结构如图7-14（见下页）所示。 （1）根据有向图的深度优先搜索遍历算法，从顶点V1出发，所得到的顶点序列是（ ）。 A.v1,v2,v3,v5,v4 B.v1,v2,v3,v4,v5 C.v1,v2,v3,v5,v4 D.v1,v4,v3,v5,v2 （2）根据有向图的广度优先搜索遍历算法，从顶点V1出发，所得到的顶点序列是（ ）。 A.v1,v2,v3,v5,v4 B.v1,v3,v2,v4,v5 C.v1,v2,v3,v5,v4 D.v1,v4,v3,v5,v2 C B

v1 v2 ^ v3 v4 ^ v5 2 1 3 ^ 3 4 ^ 3 ^ 4 图7-14

20. 已知有8个顶点值为A，B，C，D，E，F，G，H的无向图，其邻接矩阵的存储结构如图7-15所示（见下页）。由此结构，从A顶点开始深度优先搜索遍历，得到的顶点序列是（ ）。 A. A B C D G H F E B. A B C D G F H E C. A B G H F E C D D. A B F H E G D C E. A B E H F G D C F. A B E H G F C D B

  A B C D E F G H 1 图7-15

21. 已知一个图如图7-16（见下页）所示，在该图的最小生成树中各条边上权值之和为（ 21. 已知一个图如图7-16（见下页）所示，在该图的最小生成树中各条边上权值之和为（ ），在该图的最小生成树中，从顶点V1到顶点V6的路径为（ ）  A.31 B.38 C.36 D.43 E.v1,v3.v6 F.v1,v4,v6 G.v1,v5,v4,v6 H.v1,v4,v3,v6 C G

图7-16 3 1 2 5 4 6 12 15 20 10 9 8

B 22. 已知一个图如图7-17所示，则依据迪杰斯特拉算法将按照（ ）顶点次序依次求出从顶点V1到其余各顶点的最短路径。 A.v2,v5,v4,v6,v3 B.v2,v5,v4,v3,v6 C.v2,v3,v5,v4,v1 D.v5,v4,v6,v3,v2 B 图7-17 3 1 2 5 4 6 12 7 15 10

B 23. 在一个有n个顶点的无向网中，有 条边，则应该选用 ( )算法来求这个网的最小生成树，从而使计算时间较少。 A.Prim B.Kruskal B

A 24.关键路径是事件结点网络中的（ ） A.从源点到汇点的最长路径 B.从源点到汇点的最短路径 C.最长回路 D.最短回路

C D B 25. 正确的AOE网而言，必须是（ ），AOE中，某边权值应当是（ ）权值为零的边表示（ ） （1） A.完全图 B.哈密尔顿图 C.无环图 D.强连通图 （2） A.实数 B正整数 C.正数 D.非负数 （3） A.为决策而增加的活动 B.为计算方便而增加的活动 C.表示活动间的时间顺序关系 D.该活动为关键活动 D B

A 26. 当各边上权值（ ）时，BFS算法可以用解决单源点最短路径的问题。 A.均相等 B.均不相等 C.不一定相等

27. 已知一个图如图7-18所示，则由该图得到的一种拓扑序列为（. ）A. v1,v4,v6,v2,v5,v3 B 27.已知一个图如图7-18所示，则由该图得到的一种拓扑序列为（ ）A.v1,v4,v6,v2,v5,v3 B.v1,v2,v3,v4,v5,v6 C.v1,v4,v2,v3,v6,v5 D.v1,v2,v4,v6,v3,v5 A 图7-18 3 1 2 5 4 6

C 28. 判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用 （ ） 。 A.求关键路径的方法 （ ） 。 A.求关键路径的方法 　　 B.求最短路径的Dijksra方法　 C.深度优先搜索遍历算法 　　 D.广度优先搜索遍历算法 C

B 29. 下面结论中正确的是（ ） A.在无向图中，边的条数是结点度数之和。 B.在图结构中，结点可以没有任何前趋和后继.。 29. 下面结论中正确的是（ ） A.在无向图中，边的条数是结点度数之和。 B.在图结构中，结点可以没有任何前趋和后继.。 C.在n个结点的无向图中，若边数大于n-1，则该图必是连通图。 D.图的链接矩阵必定是对称矩阵

A 30.下面结论中正确的是（ ） A.若有向图的链接矩阵中对角线以下元素均为零，则该图的拓扑排序必定存在 B.网络的最小代价生成树是惟一的 30.下面结论中正确的是（ ） A.若有向图的链接矩阵中对角线以下元素均为零，则该图的拓扑排序必定存在 B.网络的最小代价生成树是惟一的 C.在拓扑排序序列中，任意两个相继结点vi 和vj 都存在从vi到 vj的路径 D.在有向图中，从一个结点到另一个结点的最短路径是惟一的

D 31.下面结论中不正确的是（ ） A. 无向图的连通分量是该图的极大连通子图 B. 有向图用链接矩阵表示，容易实现求结点度数的操作。 31.下面结论中不正确的是（ ） A.     无向图的连通分量是该图的极大连通子图 B.      有向图用链接矩阵表示，容易实现求结点度数的操作。 C.     无向图用邻接矩阵表示，图中的边数等于邻接矩阵元素之和的一半 D.     有向图的邻接矩阵必定不是对称矩阵

C 32.下面结论中正确的是（ ） A. 按深度优先搜索遍历图时，与始点相连的结点先于不在始点相连的结点访问。 32.下面结论中正确的是（ ） A.  按深度优先搜索遍历图时，与始点相连的结点先于不在始点相连的结点访问。 B.   一个图按深度优先搜索法遍历的结果是唯一的。 C.  若有向图G中包含一个环，则G的结点间不存在在拓扑序列。 D.   图的拓扑排序序列是唯一的。

B 33.下面结论中不正确的是（ ） A． 按广度优先搜索遍历图时，与始点相连的结点先于不于始点相连的结点访问。 33.下面结论中不正确的是（ ） A． 按广度优先搜索遍历图时，与始点相连的结点先于不于始点相连的结点访问。 B． 一个图按广度优先搜索法遍历的结果是唯一的。 C． 无向图的链接表表示法中，表中结点的数目是图中边的条数2倍。 D． 图的多重链接表表示法中，表中结点的数目是图中边的条数。

C 34.下面结论中正确的是（ ） A. 在无向图中，边的条数是结点度数之和。 34.下面结论中正确的是（ ） A. 在无向图中，边的条数是结点度数之和。 B． 用Prim算法和Kruskal算法求得的图最小生成树相同。 C． 在图的连接多重表表示中，任意一条边， 只用一个表目表示。 D． 在拓扑排序序列中，任意两个相距结点Vi和Vj之间都存在一条路径。

二、填空题 1. N个顶点的连通图至少_____条边。 n-1

2.一个无向图有n个顶点和e条边，则所有顶点的度数之和即Σdi（di表示顶点I的度）=_____。

3.在图形结构中，每个结点的前趋结点数和后续结点数可以_______________ 。 任意多个

4.若无向图G的顶点度数的最小值大于或等于____时，G至少有一条回路。 2

5.设无向图G的顶点数为n ,图G最少有_____边，最多有_________条边，若G为有向图，有n个顶点，则图G最少______条边 ，最多有_________条边。具有n个顶点的无向完全图，边的总数为_____________条，而具有n个顶点的有向完全图中，边数有__________条。 n(n-1)/2 n(n-1) n(n-1)/2 n(n-1)

6.在无权图G的链接矩阵A中，若（Vi,Vj）或<Vi,Vj>属于图G的边集合，则对应元素A[i][j]等于_____，否则等于_____。 1

7.在无向图G的链接矩阵A中，若A[i][j]等于1，则A[j][i]等于_____。

8.已知一个图的链接矩阵表示，计算第i个结点的入度的方法是_____。

9.在一个图G的链接表表示中，每个顶点的链接表中所含的结点数，对于有向图而言等于该顶点的_____，而对于无向图而言等于该顶点的_____。 出度数 度数

10.假定一个无向图，有n个顶点e条边，则在链接矩阵表示中，求任一个顶点度数的时间复杂度为_____；用链接表表示中，访问一个顶点的所有链接点的时间复杂度为________。 O(n) O(e*n)

11.已知图G的链接表如图7-19(见下页)所示，其从顶点 V1出发的深度优先搜索序列为___________________________，其从顶点V1出发的广度优先搜索序列为________________________________。 v1,v2,v3,v6,v5,v4 v1,v2,v5,v4,v3,v6

图7-19 v1 v2 v3 v4 ^ v5 v6 ^ 1 4 3 ^ 2 4 ^ 3 5 5 ^ 2 ^

12.设图G有n个顶点和e条边，以链接表作存储结构时，进行深度优先搜索遍历的时间复杂度为_________ ；以链接矩阵作存储结构时，进行广度优先搜索遍历的时间复杂度为_____。 O(n+e) O(n2)

13.对用链接矩阵表示的图进行深度优先或广度优先搜索遍历的时间复杂度为_____，对用链接表表示的图进行深度优先或广度优先搜索遍历时是时间复杂度为_________，图的深度优先或广度优先搜索遍历的空间复杂度为_____。 O(n2) O(n+e) O(n)

14.n个顶点的弱连通有向图G，最多有________条边，最少有_____条边。 n(n-1) n-1

15.在n个顶点、e条边的连通图中，连通分量个数是_____。

16.任何_____的有向图，其所有结点都可以排在一个拓扑序列中。拓扑排序的方法是先从图中选一个_____为0的结点且输出，然后从图中删除此结点及其_________________________。反复执行，直至所有结点都输出为止。 无环 前趋 所有以它为尾的弧

17.一个连通图的_________是一个极小连通子图。 生成树

18.在AOE网中，从源点到汇点各活动时间总和最长的路径称为_______________。 关键路径

19. Kruskal算法的时间复杂度__________，它对__________图较为合适。 O(elog2e) 边稀疏

20.对于含有n个顶点e条边的无向连通图，利用普里姆算法生成最小生成树的时间复杂度为_____，利用克鲁斯卡算法生成最小生成树的时间复杂度为_______________，在具有n个顶点的图的生成树中，含有_____条边。 O(n2) O(elog2e) n-1

21.设有向图G有n个顶点e条边，进行拓扑排序时的总的计算时间为__________。 O(n+e)

22.已知一个图如图7-20所示，则从v1到v2，v5，v6的最短路径长度分别为_____，_____和_____，从v1到图中每个顶点的最短路径长度之和为_____。 15 12 5 40 图7-20 2 1 5 3 4 6 8 15 10 12

OK