第7章图一、选择题1.一个有n 个顶点的无向图最多有（）条边。

A、nB、n(n-1)C、n(n-1)/2D、2n2.具有6 个顶点的无向图至少有（）条边才能保证是一个连通图。

A、5B、6C、7D、83.具有n 个顶点且每一对不同的顶点之间都有一条边的图被称为（）。

A、线性图B、无向完全图C、无向图D、简单图4.具有4个顶点的无向完全图有（）条边。

A、6B、12C、16D、205.G是一个非连通无向图，共有28 条边，则该图至少有（）个顶点。

A、6B、7C、8D、96.存储稀疏图的数据结构常用的是（）。

A、邻接矩阵B、三元组C、邻接表D、十字链表7.对一个具有n个顶点的图，采用邻接矩阵表示则该矩阵的大小为（）。

A、nB、(n-1)2C、(n+1)2D、n28.设连通图G的顶点数为n，则G 的生成树的边数为（）。

A、n-1B、nC、2nD、2n-19.对于一个具有N个顶点和E条边的无向图，若采用邻接表表示，则表头向量的大小为（（1））；所有邻接表中的结点总数是（（2））。

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

A、nB、n+1C、n-1D、2nE、e/2F、eG、2eH、n+e11.在有向图的邻接表存储结构中，顶点v在表结点中出现的次数是（）。

A、顶点v 的度B、顶点v 的出度C、顶点v 的入度D、依附于顶点v 的边数12.已知一个图，若从顶点a出发进行深度和广度优先搜索遍历，则可能得到的顶点序列分别为（）和（）（1） A、abecdf B、acfebd C、acebfd D、acfdeb（2） A、abcedf B、abcefd C、abedfc D、acfdeb13.采用邻接表存储的图的深度和广度优先搜索遍历算法类似于二叉树的（）和（）。

A、中序遍历B、先序遍历C、后序遍历D、层次遍历14.已知一有向图的邻接表存储结构如下图所示，分别根据图的深度和广度优先搜索遍历算法，从顶点v1出发，得到的顶点序列分别为（ ）和（ ）。

A 、v1,v2,v3,v4,v5B 、v1,v3,v2,v4,v5C 、v1,v3,v4,v5,v2D 、v1,v4,v3,v5,v2 V10 V21V32V43213V544V 13V 3V V V15. 已知有8个顶点为A ，B ，C ，D ，E ，F ，G ，H 的无向图，其邻接矩阵存储结构如下，由此结构，从A 点开始深度遍历，得到的顶点序列为（ ）。

A B C D E F G HA 01010000B 10101110C 01010000D 10100010E 01000001F 01000011G 01010101H 00001110A 、ABCDGHFEB 、ABCDGFHEC 、ABGHFECD D 、ABFHEGDCE 、ABEHFGDCF 、ABEHGFCD16. 已知一个图如下，在该图的最小生成树中各边上权值之和为（ ），在该图的最小生成树中，从v1到v6的路径为（ ）。

A 、31B 、38C 、36D 、43E 、v1,v3,v6F 、v1,v4,v6G 、v1,v5,v4,v6H 、v1,v4,v3,v6 v1v2v4v6v3v5586481012209选择题1617. 关键路径是事件结点网络中的（ ）。

A 、从源点到汇点的最长路径B 、从源点到汇点的最短路径C 、最长的回路D 、最短的回路18. 正确的AOE 网必须是（ ），AOE 网中某边权值应当是（ ）。

（1）A 、完全图 B 、哈密尔顿图 C 、无环图 D 、强连通图（2）A 、实数 B 、正整数 C 、正数 D 、非负数19. 已知一个图如下，则由该图得到的一种拓扑序列为（ ）。

A 、v1,v4,v6,v2,v5,v3B 、v1,v2,v3,v4,v5,v6C 、v1,v4,v2,v3,v6,v5D 、v1,v2,v4,v6,v3,v520. 下面结论中正确的是（ ）。

A 、在无向图中，边的条数是顶点度数之和。

B、在图结构中，顶点可以没有任何前驱和后继。

C、在n 个顶点的无向图中，若边数大于n-1，则该图必定是连通图D、图的邻接矩阵必定是对称矩阵。

21.下面结论中正确的是（）。

A、若有向图的邻接矩阵中对角线以下元素均为0，则该图的拓扑排序序列必定存在。

B、网络的最小代价生成树是唯一的。

C、在拓扑排序序列中，任意两个相继顶点vi 和vj 都存在从vi 到vj 的路径。

D、在有向图中，从一个顶点到另一个顶点的最短路径是唯一的。

22.下面结论不正确的是（）。

A、无向图的连通分量是该图的极大连通子图。

B、有向图用邻接矩阵表示容易实现求顶点度数的操作。

C、无向图用邻接矩阵表示，图中的边数等于邻接矩阵元素之和的一半。

D、有向图的邻接矩阵必定不是对称矩阵。

23.下面结论中正确的是（）。

A、按深度优先搜索遍历图时，与始点相邻的顶点先于不与始点相邻的顶点访问。

B、一个图按深度优先搜索遍历的结果是唯一的。

C、若有向图G中包含一个环，则G的顶点间不存在拓扑排序。

D、图的拓扑排序序列是唯一的。

24.下面结论中不正确的是（）。

A、按广度优先搜索遍历图时，与始点相邻的顶点先于不与始点相邻的顶点访问。

B、一个图按广度优先搜索遍历的结果是唯一的。

C、无向图的邻接表表示法中，表中结点的数目是图中边的条数的2倍。

D、图的多重邻接表表示法中，表中结点数目是图中边的条数。

25.在一个图中，所有顶点的度数之和等于所有边数的（）倍。

A、1/2B、1C、2D、426.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。

A、1/2B、1C、2D、427.判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（）。

A、求关键路径的方法B、求最短路径的DIJKSTRA 方法C、广度优先遍历算法D、深度优先遍历算法28.任何一个带权的无向连通图的最小生成树（）。

A、只有一棵B、有一棵或多棵C、一定有多棵D、可能不存在29.以下说法正确的是（）。

A、连通图的生成树，是该连通图的一个极小连通子图。

B、无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。

C、任何一个有向图，其全部顶点可以排成一个拓扑序列。

D、有回路的图不能进行拓扑排序。

30.以下说法错误的是（）。

A、用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。

B、邻接表法只能用于有向图的存储，而邻接矩阵法对于有向图和无向图的存储都适用。

C、存储无向图的邻接矩阵是对称的，因此也可以只要存储邻接矩阵的下（或上）三角部分。

D、用邻接矩阵A 表示图，判定任意两个结点V i和V j之间是否有长度为m 的路径相连，则只要检查A m的第i行第j列的元素是否为0 即可。

31.以下说法正确的是（）。

A、连通分量是无向图中的极小连通子图。

B、强连通分量是有向图中的极大强连通子图。

C、在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧<a,b>。

D、对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。

二、判断题1.用邻接矩阵法存储一个图时，所占用的存储空间大小仅与图中结点个数有关。

2.对任意一个图，从它的某个顶点出发，进行一次深度优先或广度优先搜索，即可访问图的每个顶点。

3.任何有向网拓扑排序的结果是唯一的。

4.有回路的图不能进行拓扑排序。

5.存储有向图的邻接矩阵是对称的。

6.一个有向图G中若有弧<v i,v j>、<v j,v k>和<v i,v k>, 则在图G的拓扑序列中，顶点v i,v j和v k的相对位置为v i,v j,v k。

7.在AOE网中一定有一条关键路径。

8.含有10个顶点的无向连通图其生成树含有9 条边。

9.十字链表是图的一种顺序表示法。

三、填空题1.对具有n个顶点的图，其生成树有且仅有（）条边，即生成树是图的边数（）的连通图。

2.一个无向图有n个顶点和e条边，则所有顶点的度数之和为（），其邻接矩阵是一个关于（）对称的矩阵。

3.在图形结构中，每个结点的前驱结点和后继结点可以有（）。

4.设无向图G的顶点数为n，图G最少有（）边，最多有（）条边。

若G为有向图，有n个顶点，则图G最少有（）条边，最多有（）条边。

具有n个顶点的无向完全图，边的总数为（）条，而有n个顶点的有向完全图，边的总数为（）条。

5.在无权图G的邻接矩阵A中，若(v i,v j)或<v i,v j>属于G的边/弧的集合，则对应元素A[i][j]等于（），否则等于（）。

6.在无向图G的邻接矩阵A中，若A[i][j]=1，则A[j][i]等于（）。

7.已知一个图的邻接矩阵表示，计算第I个顶点的入度方法为（）。

8.在一个图G的邻接表表示中，每个顶点的邻接表中所含的结点数，对于有向图而言等于该顶点的（），而对于无向图而言等于该顶点的（）。

9.已知图G的邻接表如图7.4所示，其从顶点V1出发的深度优先搜索序列为（），其从顶点V1出发的广度优先搜索序列为（）。

10.n个顶点的弱连通有向图G最多有（）条弧，最少有（）条弧。

11.在n个顶点e条边的连通图中，连通分量个数为（）。

12.任何（）的有向图，其所有结点都可以排在一个拓扑序列中，拓扑排序的方法是先从图中选一个（）为0的结点且输出，然后从图中删除该结点及其（），反复执行，直到所有结点都输出为止。

13.一个连通图的（）是一个极小连通子图。

14.在AOE网中，从源点到汇点各活动时间总和最长的路径为（）。

15.在有向图的邻接矩阵上，由第i行可得到第（）个结点的出度，而由第j列可得到第（）个结点的入度。

16.对无向图，设有n个结点，e条边，则其邻接表表示中需要（）个表结点，对有向图，设有n个顶点，e条弧，则其邻接表表示需要（）个表结点。

17.在无权图G的邻接矩阵A中，若(V i,V j)或<V i,V j>属于图G的边集,则对应元素A[i,j]等于（），否则等于（）。

18.已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是（）。

删除所有从第i个结点出发的边的方法是（）。

19.设无向图G中顶点数为n，则图G最少有（）条边，最多有（）条边。

若G为有向图，有n个顶点，则图至少有（）条边，最多有（）条边。

20.某作业工程表示成网络图，如图7.5所示。

事件5的最早完成时间是（）。

事件4的最迟开始时间是（）。

事件5 的迟缓时间是（）。

关键路径是（）。

21.设x,y∈V，若<x,y>∈E,则<x,y>表示有向图G中从x到y的一条（），x称为（）点，y称为（）点。