第六章图习题解答 一、选择题
1.某无向图的邻接矩阵A= ，可以看出该图共有（）个顶点
A.3 B.6 C.9 D.以上答案均不正确 【解答】A
2．无向图的邻接矩阵是一个（ ），有向图的邻接矩阵是一个（ ） A 上三角矩阵 B 下三角矩阵 C 对称矩阵 D 无规律 【解答】C，D
3．下列命题正确的是（ ）。
A 一个图的邻接矩阵表示是唯一的，邻接表表示也唯一 B 一个图的邻接矩阵表示是唯一的，邻接表表示不唯一 C 一个图的邻接矩阵表示不唯一的，邻接表表示是唯一 D 一个图的邻接矩阵表示不唯一的，邻接表表示也不唯一 【解答】B
4. 在一个具有n 个顶点的有向完全图中包含有（ ）条边： A n(n-1)/2 B n(n-1) C n(n+1)/2 D n2 【解答】B
5．一个具有n个顶点k条边的无向图是一个森林（n>k），则该森林中必有（ ）棵树。 A k B n C n - k D 1 【解答】C
6．用深度优先遍历方法遍历一个有向无环图，并在深度优先遍历算法中按退栈次序打印出相应的顶点，则输出的顶点序列是（ ）。
A 逆拓扑有序 B 拓扑有序 C 无序 D 深度优先遍历序列 【解答】A
7. 关键路径是AOE网中（ ）。
A 从源点到终点的最长路径 B从源点到终点的最长路径 C 最长的回路 D 最短的回路 【解答】A
二、填空题
1.设无向图G中顶点数为n，则图G至少有（ ）条边，至多有（ ）条边；若G为有向图，则至少有（ ）条边，至多有（ ）条边。 【解答】0，n(n-1)/2，0，n(n-1)
2.任何连通图的连通分量只有一个，即是（ ）。 【解答】其自身
3.图的存储结构主要有两种，分别是（ ）和（ ）。 【解答】邻接矩阵，邻接表
4.已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（ ）。 【解答】Ｏ(n+e)
5.已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（ ）。 【解答】求第j列的所有元素之和
6. 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（ ）。 【解答】出度
7.图的深度优先遍历类似于树的（ ）遍历，它所用到的数据结构是（ ）；图的广度优先遍历类似于树的（ ）遍历，它所用到的数据结构是（ ）。 【解答】前序，栈，层序，队列
8.对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（ ），利用Kruskal算法求最小生成树的时间复杂度为（ ）。 【解答】Ｏ(n2)，Ｏ(elog2e)
9.如果一个有向图不存在（ ），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路
10.在一个有向图中，若存在弧
11．在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。 【解答】 2
12. n个顶点的强连通图至少有（ ）条边，其形状是（ ）。 【解答】 n 环状
13含n 个顶点的连通图中的任意一条简单路径，其长度不可能超过（ ）。 【解答】n-1
14对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（ ）。 【解答】n*n
15.图的生成树（ ），n个顶点的生成树有（ ）条边。 【解答】唯一性不能确定 n-1
16.一个无环子图 ⑺ G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。 【解答】9
三、算法设计题
本章算法题了解即可
《数据结构》吕云翔编著第6章图习题解答
