欢迎来到天天文库
浏览记录
ID:33846336
大小:3.35 MB
页数:18页
时间:2019-03-01
《第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)
2、。A.第行上的非零元素个数和第列上的非零元素个数一定相等B.矩阵中的非零元素个数等于图中的边数C.第行与第列上的非零元素的总数等于顶点的度数D.矩阵中非全零行的行数等于图中的顶点数6.已知一个有向图的邻接矩阵,要删除所有以第个顶点为孤尾的边,应该(B)。A.将邻接矩阵的第行删除 B.将邻接矩阵的第行元素全部置为0C.将邻接矩阵的第列删除 D.将邻接矩阵的第列元素全部置为07.下面关于图的存储的叙述中,哪一个是正确的?……(A)A.用邻接矩阵存储图,占用的存储空间只与图中顶点数有关,而与边数
3、无关B.用邻接矩阵存储图,占用的存储空间只与图中边数有关,而与顶点数无关C.用邻接表存储图,占用的存储空间只与图中顶点数有关,而与边数无关D.用邻接表存储图,占用的存储空间只与图中边数有关,而与顶点数无关8.对图的深度优先遍历,类似于对树的哪种遍历?……(A)A.先根遍历 B.中根遍历 C.后根遍历 D.层次遍历9.任何一个无向连通图的最小生成树(B)。A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在10.下面是三个关于有向图运算的叙述:(1)求两个指向结点
4、间的最短路径,其结果必定是唯一的(2)求有向图结点的拓扑序列,其结果必定是唯一的(3)求AOE网的关键路径,其结果必定是唯一的其中哪个(些)是正确的?……( D )A.只有(1) B.(1)和(2) C.都正确 D.都不正确二、填空题1.若用表示图中顶点数,则有 条边的无向图称为完全图。2.若一个无向图有100条边,则其顶点总数最少为 15 个。3.个顶点的连通无向图至少有 条边,至多有 条边。4.若有向图的邻接矩阵为:则顶点的入度是 3 。5.对于一个有向图,若一个顶点的度为
5、,出度为,则对应逆邻接表中该顶点单链表中的边结点数为 。6.图的遍历算法BFS中用到辅助队列,每个顶点最多进队 1 次。7.在求最小生成树的两种算法中, 克鲁斯卡尔 算法适合于稀疏图。8.数据结构中的迪杰斯特拉算法是用来求 某个源点到其余各顶点的最短路径 。9.除了使用拓扑排序的方法,还有 深度优先搜索 方法可以判断出一个有向图是否有回路。10.在用邻接表表示图时,拓扑排序算法的时间复杂度为 。三、应用题1.已知如图6.28所示的有向图,请给出该图的123456图6.28 有向图 (1)每个顶点的
6、出/入度; (2)邻接矩阵; (3)邻接表; (4)逆邻接表。答:(1)每个顶点的出/入度是:出度入度103222321431512632(2)邻接矩阵:(3)邻接表:401231234Λ503Λ124565Λ5Λ0Λ014Λ(4)逆邻接表:401231234525Λ3Λ1Λ56323Λ145Λ5Λ1.试对如图6.29所示的非连通图,画出其广度优先生成森林。图Error!Notextofspecifiedstyleindocument..29 非连通图GIKHEDACFBLJM答:GIKHEDACFB
7、LJM1.已知图的邻接矩阵如图6.30所示。试分别画出自顶点A出发进行遍历所得的深度优先生成树和广度优先生成树。图Error!Notextofspecifiedstyleindocument..30 邻接矩阵答:IHEDABFGJCIHDABFGJCE1.请对如图6.31所示的无向网: (1)写出它的邻接矩阵,并按克鲁斯卡尔算法求其最小生成树; (2)写出它的邻接表,并按普里姆算法求其最小生成树。534655图Error!Notextofspecifiedstyleindocument..31 无向网
8、5437ABEFDC9GH526答:(1)克鲁斯卡尔算法求其最小生成树ABEFDCGH23ABEFDCGH23ABEFDCGH23343ABEFDCGH23443ABEFDCGH234543ABEFDCGH234543ABEFDC9GH52(2)ABCD0123EFGH456714Λ32042535Λ941525475665Λ47031535Λ571937Λ353643Λ263552Λ672534Λ66普里姆算法求其最小生成树,从A开始3ABEFDCGH
此文档下载收益归作者所有