第七章 图
一、选择题
1、12、对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（ B ）。
A. n B. n2 C. n-1 D. (n-1)2
2、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ B ）。
A. 完全图 B. 连通图 C. 有回路 D. 一棵树 3、关键路径是事件结点网络中（ A ）。
A. 从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C. 最长的回路 D. 最短的回路
4、下面（ B ）可以判断出一个有向图中是否有环（回路）。
A. 广度优先遍历 B. 拓扑排序
C. 求最短路径 D. 求关键路径
5、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（ B ）。 A. 第i行非无穷的元素之和 B. 第i列非无穷的元素个数之和
C. 第i行非无穷且非0的元素个数
D. 第i行与第i列非无穷且非0的元素之和
6、采用邻接表存储的图，其深度优先遍历类似于二叉树的（ B ）。
A. 中序遍历 B. 先序遍历 C. 后序遍历 D. 按层次遍历 7、无向图的邻接矩阵是一个（ A ）。
A. 对称矩阵 B. 零矩阵 C. 上三角矩阵 D. 对角矩阵
8、当利用大小为N的数组存储循环队列时，该队列的最大长度是（ B ）。
A. N-2 B. N-1 C. N D. N+1 9、邻接表是图的一种（ B ）。
A. 顺序存储结构 B. 链式存储结构 C. 索引存储结构 D. 散列存储结构
10、下面有向图所示的拓扑排序的结果序列是（ B ）。
A. 125634 B. 516234 C. 123456 D. 521643
132564
11、在无向图中定义顶点vi与vj之间的路径为从vi到vj的一个（ A ）。
A. 顶点序列 B. 边序列
31
C. 权值总和 D. 边的条数
12、在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有（ A ）邻接点。
A. 入边 B. 出边 C. 入边和出边 D. 不是出边也不是入边
13、设G1=(V1,E1)和G2=(V2,E2)为两个图，如果V1?V2,E1?E2则称（ A ）。
A. G1是G2的子图 B. G2是G1的子图 C. G1是G2的连通分量 D. G2是G1的连通分量
14、已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应（ B ）。
A. 将邻接矩阵的第i行删除 B. 将邻接矩阵的第i行元素全部置为0 C. 将邻接矩阵的第i列删除 D. 将邻接矩阵的第i列元素全部置为0 15、任一个有向图的拓扑序列（ D ）。
A.不存在 B. 有一个 C. 一定有多个 D. 有一个或多个
16、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ B ）倍。
A. 1/2 B. 1 C. 2 D. 4 17、下列关于图遍历的说法不正确的是（ C ）。
A. 连通图的深度优先搜索是一个递归过程
B. 图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C. 非连通图不能用深度优先搜索法 D. 图的遍历要求每一顶点仅被访问一次
18、带权有向图G用邻接矩阵A存储，则顶点i的入度为A中：（ D ）。
A. 第i行非?的元素之和 B. 第i列非?的元素之和
C. 第i行非?且非0的元素个数 D. 第i列非?且非0的元素个数 19、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（ D ）。
A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层次遍历
20、一个具有n个顶点的有向图最多有（ B ）条边。
A. n×(n-1)/2 B. n×(n-1) C. n×(n+1)/2 D. n2
21、已知一个有向图的邻接表存储结构如图所示，根据深度优先遍历算法，从顶点v1出发，所得到的顶点序列是（ C ）。
123452445324
A. v1,v2,v3,v5,v4
B. v1,v2,v3,v4,v5
32
C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v2 22、关键路径是事件结点网络中（ A ）。
A. 从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C. 最长的回路 D. 最短的回路 23、以下说法正确的是（ B ）。
A. 连通分量是无向图中的极小连通子图
B. 强连通分量是有向图中的极大强连通子图
C. 在一个有向图的拓扑序列中若顶点a在顶点b之前，则图中必有一条弧
D. 对有向图G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图
24、假设有向图含n个顶点及e条弧，则表示该图的邻接表中包含的弧结点个数为（ B ）。
A. n B. e C. 2e D. n*e
?011???25、设图的邻接矩阵为?001?，则该图为（ A ）。
?010???A. 有向图 B. 无向图
C. 强连通图 D. 完全图
26、为便于判别有向图中是否存在回路，可借助于（ D ）。
A. 广度优先搜索算法 B. 最小生成树算法 C. 最短路径算法 D. 拓扑排序算法 27、任何一个无向连通图的最小生成树（ B ）种。
A. 只有一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在
28、已知一有向图的邻接表存储结构如图所示，根据有向图的广度优先遍历算法，从顶点v1出发，所得到的顶点序列是（ B ）。
1 2 ^ 3 4 ^ 5 2 4 4 5 3 2 ^ ^ ^
A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5 C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v2
29、对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中的结点数为（ B ）。
A. k1 B. k2 C. k1+k2 D. k1-k2
30、一个具有8个顶点的有向图中，所有顶点的入度之和与所有顶点的出度之和的差
33
等于（ C ）。
A. 16 B. 4 C. 0 D. 2 31、无向图中一个顶点的度是指图中（ B ）。
A. 通过该顶点的简单路径数 B. 与该顶点相邻接的顶点数 C. 与该顶点连通的顶点数 D. 通过该顶点的回路数
二、填空题
1、n个顶点的连通图至少有 边。 答案：n-1条
2、一个连通图的生成树是一个 ，它包含图中所有顶点，但只有足以构成一棵树的n-1条边。 答案：极小连通子图
3、一个图的 表示法是惟一的。 答案：邻接矩阵
4、遍历图的基本方法有深度优先搜索和广度优先搜索，其中 是一个递归过程。
答案：深度优先搜索
5、在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于 。 答案：1
6、判定一个有向图是否存在回路，可以利用 。 答案：拓扑排序
7、已知一个图的邻接矩阵表示，计算第i个结点的入度的方法是 。
答案：第i列上非无穷元素的个数之和
8、n个顶点的无向图最多有 边。 答案：n*(n-1)/2
9、已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是 。
答案：将邻接矩阵的第i行元素全部置为0.
10、若以邻接矩阵表示有向图，则邻接矩阵上第i行中非零元素的个数即为顶点vi的 。 答案：出度 三、判断题
1、图的连通分量是无向图的极小连通子图。 错 2、一个图的广度优先搜索树是惟一的。错
3、图的深度优先搜索序列和广度优先搜索序列不是惟一的。对
4、邻接表只能用于存储有向图，而邻接矩阵则可存储有向图和无向图。错
5、存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。错
34
6、AOV网是一个带权的有向图。错
7、从源点到终点的最短路径是唯一的。错
8、邻接表只能用于存储有向图，而邻接矩阵则可存储有向图和无向图。dui 9、图的生成树是惟一的。错
四、程序分析题
1、写出下面算法的功能。 typedef struct{
int vexnum,arcnum; char vexs[N]; int arcs[N][N];
}graph;
void funtion(int i,graph *g){ int j;
printf(\ visited[i]=TRUE;
for(j=0;j
答案：实现图的深度优先遍历算法
五、综合题
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算法）
35
数据结构试题集（含答案）
