数据结构基本复习 第七章 图
一、单选题（共25题）
1. 在一个图G中，所有顶点的度数之和等于所有边数之和的（C）倍。
A．1/2
B．1
C．2
D．4
2. 一个具有n个顶点的无向完全图包含（C）条边。
A．n（n-1）
B．n（n+1）
C． n（n-1）/2
D． n（n+1）/2
3. 一个具有n个顶点的有向完全图包含（A）条边。
A．n（n-1）
B．n（n+1）
C． n（n-1）/2
D． n（n+1）/2
4. 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（D）。
A．n
B．e
C．2n
D．2e
5. 在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（B）邻接点。
A．入边
B．出边
C．入边和出边
D．不是入边也不是出边
6. 邻接表是图的一种（B）。
A．顺序存储结构
B．链式存储结构
C．索引存储结构
D．散列存储结构
解析：邻接表由顶点数组+边链表组成。
每个顶点的邻接点用链表存储，因此整体属于链式存储结构。
7. 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，
则该图一定是（B）。
A. 完全图
B．连通图
C．有回路
D. 一棵树
8.下列有关图遍历的说法不正确的是（C）。
A．连通图的深度优先搜索是一个递归过程
B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征
C．非连通图不能用深度优先搜索法
D．图的遍历要求每一顶点仅被访问一次
解析：非连通图也能用深度优先搜索，只需对每个未被访问的顶点依次调用深度优先搜索，即可遍历所有连通分量。
9. 无向图的邻接矩阵是一个（A）。
A．对称矩阵
B．零矩阵
C．上三角矩阵
D．对角矩阵
10. 图的深度优先遍历算法类似于二叉树的（A）遍历。
A．先序
B．中序
C．后序
D．层次
11. G是一个非连通无向图，共28条边，则该图至少有（D）个顶点。
A. 6
B. 7
C. 8
D. 9
解析：为了在给定的边数下顶点数最少，应让其中一个连通分量边数尽量多，其余顶点孤立（无边）。假如有8个顶点构造无向完全图，则边数为8*(8-1)/2=28,为了构成非连通图，至少还要一个孤立的顶点，所以至少要9个顶点。
12. 在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为（B）。
A．k
B．k+1
C．k+2
D. 2k
解析：路径长度通常定义为路径上边的数目。一条由k条边构成的路径，经过的顶点数为k+1。
13. n个顶点的强连通图中至少含有(B)。
A．n-1条有向边
B．n条有向边
C．n(n-1)／2条有向边
D．n(n-1)条有向边
解析：强连通图要求：任意两个顶点之间互相可达（有路径）。最少边数情况：将n个顶点排成一个有向环（例如1→2→3→…→n→1），每个顶点有一条出边、一条入边，总边数=n。此时图是强连通的（沿环可以到达任意顶点）。
注意：强连通图要求是任意两个顶点之间互相可达，而不是直接可达。
14. 已知如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（C）。
A．abecdf
B．acfebd
C．aedfcb
D．aebcfd
15. 关键路径是事件结点网络中（A）。
A. 从源点到汇点的最长路径
B. 从源点到汇点的最短路径
C. 最长的回路
D. 最短的回路
解析：
源点：工程开始（时间0）
汇点：工程结束
为什么找“最长路径”？
工程中有多条路径（工序并行）。
所有路径都必须在汇点完成。
只有最长的那条路径上的所有活动都完成了，工程才算结束。
所以最长路径决定了工程的最短完成时间。
16. 下面（B）可以判断出一个有向图中是否有环（回路）。
A. 广度优先遍历
B. 拓扑排序
C. 求最短路径
D. 求关键路径
解析：拓扑排序：对DAG（有向无环图）进行拓扑排序时，如果所有顶点都能输出，则无环；如果存在环，则一定会有顶点无法输出（入度不为0但已无入度为0的顶点）。
因此，拓扑排序可以用来检测有向图是否存在环。
17. 采用邻接表存储的图，其深度优先遍历类似于二叉树的（B）。
A. 中序遍历
B. 先序遍历
C. 后序遍历
D. 按层次遍历
18. 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（C）。
A. O(n2)
B. O(n*e)
C. O(n+e)
D. O(2n)
解析
邻接表存储无向图时：
顶点表：长度为n，空间O(n)
边表：每条无向边对应2个边结点，边结点总数为2e，空间O(e)
因此，总空间复杂度为：O(n+e)
19. 已知一个图如下图所示，若从顶点a出发按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（D）。
A. acfdeb
B. acfebd
C. acbdef
D. abecdf
20. 在无向图中定义顶点vi与vj之间的路径为从vi到vj的一个（A）。
A. 顶点序列
B. 边序列
C. 权值总和
D. 边的条数
解析：在无向图中，路径通常定义为顶点序列
21. 在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有（A）邻接点。
A. 入边
B. 出边
C. 入边和出边
D. 不是出边也不是入边
22. 设G1=(V1,E1)和G2=(V2,E2)为两个图，如果V1ÍV2,E1ÍE2则称（A）。
A. G1是G2的子图
B. G2是G1的子图
C. G1是G2的连通分量
D. G2是G1的连通分量
23. 已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应（B）。
A. 将邻接矩阵的第i行删除
B. 将邻接矩阵的第i行元素全部置为0
C. 将邻接矩阵的第i列删除
D. 将邻接矩阵的第i列元素全部置为0
解析：在有向图的邻接矩阵中：
行：表示从该顶点出发的边（出边）
列：表示进入该顶点的边（入边）
比如说顶点1到顶点3有通路，则第1行第3列值为1；如果顶点3到顶点1也有通路，则第3行第1列的值为1。
二、判断题
1. 图的深度优先搜索序列和广度优先搜索序列不是惟一的。（√）
2. 邻接表只能用于存储有向图，而邻接矩阵则可存储有向图和无向图。（×）
3. 存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。（×）
4. AOV网是一个带权的有向图。（×）
5. 从源点到终点的最短路径是唯一的。（×）
6. 图的生成树是惟一的。（×）
7. 对连通图进行深度优先遍历可以访问到该图中的所有顶点。（√）
8. 有n个结点的无向图中，若边数大于n-1，则该图是连通的。（×）
解析：边数e>n−1只是说明图可能连通，但不能保证一定连通。
比如有8个结点，其中7个结点构成无向完全图（即边数=7*(7-1)/2=21）,另一个结点完全孤立。21>(8-1)，但该图并不连通。
9. 若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑有序序列必定存在。（√）
解析
邻接矩阵对角线以下元素均为零，意味着所有边⟨i,j⟩⟨i,j⟩都满足i<ji<j（即顶点编号小的指向编号大的）。
这种矩阵对应的是无环有向图（DAG）。
对DAG进行拓扑排序时，按顶点编号从小到大的顺序输出，就是一个拓扑有序序列。
因此，拓扑有序序列必定存在。
10. AOV网拓扑排序的结果是惟一的。（×）
11. 图的广度优先搜索序列是惟一的。（×）
12. 具有n个顶点的无向图采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半。（√）
13. 若连通图上各边权值均不相同，则该图的最小生成树是惟一的。（√）
解析
在连通图中，若所有边的权值均不相同，则使用Kruskal或Prim算法构造最小生成树时，每一步选择的边都是唯一确定的。
因此，该图的最小生成树是唯一的。
14. 无向图的邻接矩阵一定是对称的。（√）
15. 有向图的邻接矩阵一定是非对称的。（×）
16. 用邻接矩阵存储图的时候，占用空间大小不但与图的结点个数有关还与图的边数有关。（×）
17. 图的连通分量是无向图的极小连通子图。（×）
解析
连通分量定义为无向图的极大连通子图（再增加一个顶点就会破坏连通性）。
极小连通子图通常指生成树（边数最少的连通子图），不是连通分量的定义。
18. 图的强连通分量是无向图的极大连通子图。（×）
解析
强连通分量定义在有向图中，不是无向图。
无向图没有“强连通分量”这个概念，只能说“连通分量”。
强连通分量是有向图的极大强连通子图（任意两点互相可达）。
19. 对任意一个图从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。（×）
20. 一个有向图的邻接表和逆邻接表中的节点个数一定相等。（√）
21. 有向图用邻接矩阵表示后，顶点i的出度等于第i行中非0且非无穷的元素个数。（√）
22. 图G的某一最小生成树的代价一定小于其他生成树的代价。（×）
解析：如果图G的最小生成树是唯一的，则最小生成树的代价一定小于其他生成树的代价。如果图G有多个不同的最小生成树，则它和其他最小生成树的代价是相等的，不是“小于”。
23. 任一个有向图的拓扑序列只有一个。（×）
24. 一个无向连通图的生成树是含有该连通图的全部顶点的极小连通子图。（√）
25. 采用邻接表存储的图的广度优先遍历算法类似于二叉树的按层次遍历。（√）
三、程序填空题（2题，附加题）
1.已知图G的邻接矩阵如下所示：
从顶点1出发的广度优先搜索序列为（A）。
A. 1；2，3， 4；5；6
B. 2；1，3，5；4；6
C. 3；1，2，4；5；6
D. 4；2，3，6；1；5
解析：无权图和带权图在邻接矩阵的不同表示方法：
无权图：邻接矩阵中的值是0或1，1表示有边，0表示无边
带权图：邻接矩阵中的值是权值或∞，具体数值表示边的权值，∞（或一个大数）表示无边。
2.对于一个无向图，假定采用邻接矩阵表示，试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列。（C）
注：每一种序列都是唯一的，因为都是在存储结构上得到的。
A. 0，2，3，4，5，1，6
B. 0，2，3，5，1，6，4
C. 0，2，3，5，6，1，4
D. 0，2，3，4，5，1，6
