________________; } } }
23.深度优先搜索遍历类似于树的________遍历，它所用到的数据结构是________；广度优先搜索遍历类似于树的________遍历，它所用到的数据结构是________。 24.任何连通图的连通分量只有一个，即________。
25.对具有n个顶点的图其生成树有且仅有________条边，即生成树是图的边数________的连通图。
26.一个图的________的表示法是惟一的，而________表示法是不惟一的。 27.对无向图，其邻接矩阵是一个关于________对称的矩阵。
28.在有向图的邻接矩阵上，由第i行可得到第________个结点的出度，而由第j列可得到第________个结点的入度。
29.________的有向图，其全部顶点有可能排成一个拓扑序列。
30.一个有向图G中若有弧,
1.设有无向图G=（V，E）和G’=（V’,E）’,如G’为G的生成树，则下面不正确的说法是（ ）
①G’为G的子图 ②G’为G的连通分量 ③G’为G的极小连通子图且V’=V ④G’是G的无环子图
2.任何一个带权的无向连通图的最小生成树（ ）
①只有一棵 ②有一棵或多棵 ③一定有多棵 ④可能不存在 3.设图G采用邻接表存储，则拓扑排序算法的时间复杂度为（ ）
36
①O(n) ②O(n+e) ③O(n*n) ④O(n*e)
4.含n个顶点的连通图中的任意一条简单路径，其长度不可能超过 （ ）
①1 ② n/2 ③ n-1 ④n
5．一有向图G的邻接表存储结构如图单项选择5所示。现按深度优先遍历算法，从顶点V1（ ）
①V1,V3, V2 ,V4, V5 ②V1, V3, V4, V2, V5 ③V1,V2, V3, V4, V5 ④V1, V3, V4, V5 , V2 6.在无向图中，所有顶点的度数之和是所有边数的（ ）倍。
①0.5 ②1 ③2 ④4
7.在有向图中，所有顶点的入度之和是所有顶点出度之和的（ ）倍。 （ ）
①0.5 ② 1 ③ 2 ④4
出
发
，
所
得
到
的
顶
点
序
列
是
8．在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的 （ ）
①先根遍历 ② 中根遍历 ③ 后根遍历 ④按层次遍历
9．在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的 （ ）
①先根遍历 ②中根遍历 ③后根遍历 ④按层次遍历
10．判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用 （ ）
37
①求关键路径方法②求最短路径的Dijkstra方法③广度优先遍历方法④深度优先遍历方法
11．在图单项选择中，从顶点V1出发，按广度优先遍历图的顶点序列是 （ ）
①V1 V3 V5 V4 V2 V6 V7 ②V1 V2 V4 V7 V6 V5 V3 ③V1 V5 V3 V4 V2 V7 V6 ④V1 V4 V7 V2 V6 V5 V3
12.在图单项选择中，从顶点V1出发,广度遍历图的顶点序列是 （ ）
①V1 V5 V3 V4 V2 V6 V7 ②V1 V5 V3 V4 V2 V7 V6 ③V1 V7 V2 V6 V4 V5 V3 ④V1 V2 V4 V7 V6 V5 V3
13.设有6个结点的无向图，该图至少应有（ ）条边能确保是一个连通图。 （ ） ① 5 ② 6 ③ 7 ④ 8 14.（ ）
①连通图的生成树，是该连通图的一个极小连通子图。
②无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。 ③任何一个有向图，其全部顶点可以排成一个拓扑序列。 ④有回路的图不能进行拓扑排序。
15以下说法错误的是 （ ） ①用相邻矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。
②邻接表法只能用于有向图的存储，而相邻矩阵法对于有向图和无向图的存储都适用。 ③存储无向图的相邻矩阵是对称的，因此只要存储相邻矩阵的下（或上）三角部分就可以了
38
以下说法正确的是
③用相邻矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查A的第 i行第j列的元素是否为0即可。 16（ ）
①连通分量是无向图中的极小连通子图。 ②强连通分量是有向图中的极大强连通子图。
③在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧。 ④对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。 四、简答及应用
1． 简述图的邻接矩阵表示的类型定义 2． 简述图的邻接表的类型定义。
3． 给出无向图简答题3中g1的邻接矩阵和邻接表。
．
以
下
说
法
正
确
的
是
4．分别给出图简答题3中g2的邻接矩阵、邻接表和逆邻接表。
5．分别给出图简答题3中g3从v5出发按深度优先搜索和广度优先搜索算法遍历得到的顶点序列。
6．求出图简答题6-1的连通分量。
39
7．求出带权图简答题7-1的最小生成树 8．写出有向图简答题8-1的拓扑排序序列。 9．给出网图简答题9-1的邻接矩阵表示。
10．已知连通网的邻接矩阵如下，试画出它所表示的连通网及该连通网的最小生成树。
11．对于图简答题11-1从其邻接表中回答下列问题： （1） 图中有多少条弧？
（2） 图中是否存在从i到j的弧？ （3） 如何求顶点i的出度？
40