第6章 图习题参考答案

《第6章 图习题参考答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题六参考答案一、选择题1.在一个有个顶点的有向图中，若所有顶点的出度之和为，则所有顶点的入度之和为（A）。A.　　　　B.　　　　C.　　　　D.2.一个有向图有个顶点，则每个顶点的度可能的最大值是（B）。A.　　　　B.　　　　C.　　　　D.3.具有6个顶点的无向图至少应有（　A　）条边才能确保是一个连通图。A.5　　　　B.6　　　　C.7　　　　D.84.一个有n个顶点的无向图最多有（　C　）条边。A.　　　　B.　　　　C.　　　　D.5.对某个无向图的邻接矩阵来说，下列叙述正确的是（A）。A.第行上的非零元素个数和第列上的非零元素个数一定相等B.矩阵中的

2、非零元素个数等于图中的边数C.第行与第列上的非零元素的总数等于顶点的度数D.矩阵中非全零行的行数等于图中的顶点数6.已知一个有向图的邻接矩阵，要删除所有以第个顶点为孤尾的边，应该（B）。A.将邻接矩阵的第行删除　　　　B.将邻接矩阵的第行元素全部置为0C.将邻接矩阵的第列删除　　　　D.将邻接矩阵的第列元素全部置为07.下面关于图的存储的叙述中，哪一个是正确的？……（A）A．用邻接矩阵存储图，占用的存储空间只与图中顶点数有关，而与边数无关B．用邻接矩阵存储图，占用的存储空间只与图中边数有关，而与顶点数无关C．用邻接表存储图，占用的存储空间只与图中顶点数有关，而与边数无

3、关D．用邻接表存储图，占用的存储空间只与图中边数有关，而与顶点数无关8.对图的深度优先遍历，类似于对树的哪种遍历？……（A）A.先根遍历　　　　B.中根遍历　　　　C．后根遍历　　　　D．层次遍历9.任何一个无向连通图的最小生成树（B）。A.只有一棵　　　B.有一棵或多棵　　　C.一定有多棵　　　D.可能不存在10.下面是三个关于有向图运算的叙述：（1）求两个指向结点间的最短路径，其结果必定是唯一的（2）求有向图结点的拓扑序列，其结果必定是唯一的（3）求AOE网的关键路径，其结果必定是唯一的其中哪个（些）是正确的？……（　D　）A.只有（1）　　　　B.（1）和（2）

4、　　　　C.都正确　　　　D.都不正确二、填空题1.若用表示图中顶点数，则有　　条边的无向图称为完全图。2.若一个无向图有100条边，则其顶点总数最少为　15　个。3.个顶点的连通无向图至少有　　条边，至多有　　条边。4.若有向图的邻接矩阵为：则顶点的入度是　3　。5.对于一个有向图，若一个顶点的度为，出度为，则对应逆邻接表中该顶点单链表中的边结点数为　　。6.图的遍历算法BFS中用到辅助队列，每个顶点最多进队　1　次。7.在求最小生成树的两种算法中，　克鲁斯卡尔　算法适合于稀疏图。8.数据结构中的迪杰斯特拉算法是用来求　某个源点到其余各顶点的最短路径　。9.除了使用

5、拓扑排序的方法，还有　深度优先搜索　方法可以判断出一个有向图是否有回路。10.在用邻接表表示图时，拓扑排序算法的时间复杂度为　　。三、应用题1.已知如图6.28所示的有向图，请给出该图的123456图6.28　有向图　(1)每个顶点的出/入度；　(2)邻接矩阵；　(3)邻接表；　(4)逆邻接表。答：(1)每个顶点的出/入度是：出度入度103222321431512632(2)邻接矩阵：(3)邻接表：401231234Λ503Λ124565Λ5Λ0Λ014Λ(4)逆邻接表：401231234525Λ3Λ1Λ56323Λ145Λ5Λ1.试对如图6.29所示的非连通图，画出

6、其广度优先生成森林。图Error!Notextofspecifiedstyleindocument..29　非连通图GIKHEDACFBLJM答：GIKHEDACFBLJM1.已知图的邻接矩阵如图6.30所示。试分别画出自顶点A出发进行遍历所得的深度优先生成树和广度优先生成树。图Error!Notextofspecifiedstyleindocument..30　邻接矩阵答：IHEDABFGJCIHDABFGJCE1.请对如图6.31所示的无向网：　(1)写出它的邻接矩阵，并按克鲁斯卡尔算法求其最小生成树；　(2)写出它的邻接表，并按普里姆算法求其最小生成树。5346

7、55图Error!Notextofspecifiedstyleindocument..31　无向网5437ABEFDC9GH526答：(1)克鲁斯卡尔算法求其最小生成树ABEFDCGH23ABEFDCGH23ABEFDCGH23343ABEFDCGH23443ABEFDCGH234543ABEFDCGH234543ABEFDC9GH52(2)ABCD0123EFGH456714Λ32042535Λ941525475665Λ47031535Λ571937Λ353643Λ263552Λ672534Λ66普里姆算法求其最小生成树，从A开始3ABEFDCGH