单元练习8
一．判断题（下列各题，正确的请在前面的括号打√；错误的打╳）
（√）（1）图可以没有边，但不能没有顶点。
（ㄨ）（2）在无向图中，（V1，V2）与（V2，V1）是两条不同的边。
（ㄨ）（3）邻接表只能用于有向图的存储。
（√）（4）一个图的邻接矩阵表示是唯一的。
（ㄨ）（5）用邻接矩阵法存储一个图时，所占用的存储空间大小与图中顶点个数无关，而只与图的边数有关。
（ㄨ）（6）有向图不能进行广度优先遍历。
（√）（7）若一个无向图的以顶点V1为起点进行深度优先遍历，所得的遍历序列唯一，则可以唯一确定该图。
（√）（8）存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角）部分就可以了。
（ㄨ）（9）用邻接表法存储图时，占用的存储空间大小只与图中的边数有关，而与结点的个数无关。（√）（10）若一个无向图中任一顶点出发，进行一次深度优先遍历，就可以访问图中所有的顶点，则该图一定是连通的。
二．填空题
（1）图常用的存储方式有邻接矩阵和邻接表等。
（2）图的遍历有：深度优先搜和广度优先搜等方法。
（3）有n条边的无向图邻接矩阵中，1的个数是 _2n____。
（4）有向图的边也称为 _ 弧___ 。
（5）图的邻接矩阵表示法是表示 __顶点____之间相邻关系的矩阵。
（6）有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的 __出度____。
（7）n个顶点e条边的图若采用邻接矩阵存储，则空间复杂度为：O（n2）。
（8）n个顶点e条边的图若采用邻接表存储，则空间复杂度为：O（n+e）。
（9）设有一稀疏图G，则G采用 _邻接表____存储比较节省空间。
（10）设有一稠密图G，则G采用 _邻接矩阵____存储比较节省空间。
（11）图的逆邻接表存储结构只适用于 __有向____图。
（12） n个顶点的完全无向图有 n(n-1)/2_ 条边。
（13）有向图的邻接表表示适于求顶点的出度。
（14）有向图的邻接矩阵表示中，第i列上非0元素的个数为顶点V i的入度。
（15）对于具有n个顶点的图，其生成树有且仅有n-1 条边。
（16）对n个顶点，e条弧的有向图，其邻接表表示中，需要n+e 个结点。
（17）从图中某一顶点出发，访遍图中其余顶点，且使每一顶点仅被访问一次，称这一过程为图的遍历。
（18）无向图的邻接矩阵一定是对称矩阵。
（19）一个连通网的最小生成树是该图所有生成树中权最小的生成树。
（20）若要求一个稠密图G的最小生成树，最好用Prim 算法来求解。
三．选择题
（1）在一个图中，所有顶点的度数之和等于图的边数的( C )倍。
A．1/2 B. 1 C. 2 D. 4
（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的( B )倍。
A．1/2 B. 1 C. 2 D. 4
（3）对于一个具有n个顶点的有向图的边数最多有（ B ）。
A．n B．n(n-1) C．n(n-1)/2 D．2n
（4）在一个具有n个顶点的无向图中，要连通全部顶点至少需要（ C ）条边。
A．n B．n+1 C． n-1 D．n/2
（5）有8个结点的有向完全图有( C )条边。
A．14 B. 28 C. 56 D. 112
（6）深度优先遍历类似于二叉树的( A )。
A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历
（7）广度优先遍历类似于二叉树的( D )。
A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历
（8）任何一个无向连通图的最小生成树( A )。
A．只有一棵 B．一棵或多棵 C．一定有多棵 D．可能不存在
（9）无向图顶点v的度是关联于该顶点（ B ）的数目。
A．顶点 B．边 C．序号 D．下标
（10）有n个顶点的无向图的邻接矩阵是用（ B ）数组存储。
A．一维B．n行n列C．任意行n列 D．n行任意列
（11）对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头向量大小为（ C ）。 A．n-1 B．n+1 C．n D．n+e
（12）在图的表示法中，表示形式唯一的是（ A ）。
A．邻接矩阵表示法 B．邻接表表示法
C．逆邻接表表示法 D．邻接表和逆邻接表表示法
（13）在一个具有n个顶点e条边的图中，所有顶点的度数之和等于（ C ）。
A．n B．e C． 2n D．2e
（14）下列图中，度为3的结点是（ B ）。
A ．V 1 B. V 2 C. V 3 D. V 4 （15）下列图是（ A ）。
A ．连通图 B. 强连通图 C. 生成树 D. 无环图
（16）如下图所示，从顶点a 出发，按深度优先进行遍历，则可能得到的一种顶点序列为（ D ）。
A ． a ，b ，e ，c ，d ，f
B ． a ，c ，f ，e ，b ，d C. a ，e ，b ，c ，f ，d D. a ，e ，d ，f ，c ，b
（17）如下图所示，从顶点a 出发，按广度优先进行遍历，则可能得到的一种顶点序列为（ A ）。
A. a ，b ，e ，c ，d ，f
B. a ，b ，e ，c ，f ，d
C. a ，e ，b ，c ，f ，d
D. a ，e ，d ，f ，c ，b
（18）最小生成树的构造可使用（ A ）算法。 A ．prim 算法
B ．卡尔算法
C ．哈夫曼算法
D ．迪杰斯特拉算法
（19）下面关于图的存储结构的叙述中正确的是（ A ）。
A ． 用邻接矩阵存储图，占用空间大小只与图中顶点数有关，而与边数无关
B ． 用邻接矩阵存储图，占用空间大小只与图中边数有关，而与顶点数无关
C ． 用邻接表存储图，占用空间大小只与图中顶点数有关，而与边数无关
D ． 用邻接表存储图，占用空间大小只与图中边数有关，而与顶点数无关 （20）连通分量是（ C ）的极通子图。 A ．树
B ．图
C ．无向图
D ．有向图
四．应用题（30分）
