第7章
习题
一、填空题
1、若连通图G的顶点个数为n，则G的生成树的边数为 。如果G的一个子图G’的边数 ，则G’中一定有环。相反，如果G’的边数 ，则G’一定不连通。
2、对于无向图的邻接矩阵，顶点vi的度是 。对于有向图的邻接矩阵，顶点vi的出度为 ，顶点vi的入度为 。
3、对无向图，若它有n个顶点e条边，则其邻接链表中需要 个结点。其中， 个结点构成邻接表， 个结点构成顶点表。
4、 的有向图，其全部顶点有可能排成一个拓扑序列。
5、对于无向图，其邻接矩阵是一个关于 对称的矩阵。
6、若以图中的顶点来表示活动，有向边表示活动之间的优先关系，则这样的有向图为 网。
7、按权值递增的次序来构造最小生成树的方法，是由 提出的。
8、在一个有n个顶点的无向完全图中，包含 条边，在一个有n个顶点的有向完全图中，包含 条弧。
二、选择题
1、设有无向图G=（V，E）和G’=（V’，E’），如G’为G的生成树，则下面不正确的说法是（ ）。
A．G’为G的子图 B．G’为G的连通分量
C．G’为G的极小连通子图且V’=V D．G’是G的无环子图
2、在一个图中，所有顶点的度数之和等于所有边数的( )倍。
A．1/2 B．1 C．2 D．3
3、在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的( )倍。
A．1/2 B．1 C．2 D．3
4、在有向图G的拓扑序列中，如果顶点vi在vj之前，则在下列情况中一定不可能出现的是( )。
A．G中有弧<vi,vj> B．G中有一条从vi到vj的路径
C．G中没有弧<vi,vj> D．G中有一条从vj到vi的路径
5、下面关于图的存储叙述中正确的是( )。
A．用邻接矩阵存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关。
B．用邻接矩阵存储图，占用的存储空间大小只与图的边数有关，而与结点个数无关。
C．用邻接链表存储图，占用存储空间的大小只与图中结点个数有关，而与边数无关。
D．用邻接链表存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。
6、任何一个带权的无向连通图的最小生成树有( )。
A．只有一棵 B．一棵或多棵 C．一定有多棵 D．可能不存在
7、在有n个顶点的连通图中的任意一条简单路径，其长度不可能超过( )。
A．1 B．n/2 C．n-1 D．n
8、采用邻接表存储的图的深度优先遍历算法类似于二叉树的( )。
A．先根遍历算法 B．中根遍历算法 C．后根遍历算法 D．层次遍历算法
三、判断题
1、所有AOV网的拓扑序列都是不唯一的。 （ ）
2、线性结构和树形结构都可以看成是简单的图形结构。 （ ）
3、生成树是图的边数最少的连通图。 （ ）
4、若无向图有n个顶点，e条边，则邻接链表需n个表头结点和e个表结点。 （ ）
5、无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。 （ ）
6、在一个具有n个顶点的有向图中，最多可能有n(n-1)/2条弧。 （ ）
7、用邻接链表表示图，很容易确定图中任意两个顶点是否有边相连。 （ ）
8、广度优先搜索遍历类似于树的按层次遍历。 （ ）
9、连通图中任意两顶点间都是有路径可达的。 （ ）
10、在广度优先搜索中，若对顶点vi的访问先于顶点vj，则对顶点vi邻接点的访问也先于对顶点vj邻接点的访问。 （ ）
四、应用题
1、分别给出图7.26所示无向图G1和图7.27所示有向图G2的邻接矩阵和邻接链表。
图7.26 无向图G1 图7.27 有向图G2
2、对于图7.26和图7.27，分别求：
（1）从顶点1开始进行深度优先搜索的遍历序列及其生成树或生成森林。
（2）从顶点1开始进行广度优先搜索的遍历序列及其生成树或生成森林。
3、按图7.28所示的邻接链表写出：
（1）从顶点A开始进行广度优先搜索和深度优先搜索的序列。
（2）从顶点B开始进行广度优先搜索和深度优先搜索的序列。
图7.28 邻接链表
4、对于图7.29所示无向连通网G3分别使用Prim算法和Kruskal算法求最小生成树，并列出其构造过程。
图7.29 无向连通网G3 图7.30 有向图G4
5、对于图7.30所示有向图G4，写出两种拓扑排序序列。
6、对于图7.31所示有向网G5，按迪杰斯特拉算法求从顶点1到其余各顶点的最短路径，要求给出给出辅助数组中值的变化过程。
图7.31有向网G5
五、算法设计题
1、用邻接矩阵存储一个有向图，写一算法计算出度为0的顶点个数。
2、有向图G以邻接链表存储，写一算法利用深度优先搜索判断图G中，从顶点i到顶点j是否有路径存在。
评论0