首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列说法正确的是( )。 Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题 Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量 Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
下列说法正确的是( )。 Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题 Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量 Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
admin
2017-04-28
46
问题
下列说法正确的是( )。
Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题
Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量
Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
选项
A、仅Ⅰ、Ⅱ
B、仅Ⅱ、Ⅲ
C、仅Ⅱ
D、仅Ⅰ、Ⅲ
答案
A
解析
Ⅰ:对于无权图,广度优先搜索总是按照距离源点由近到远来遍历图中每个顶点(这里的距离是指当前顶点到源点路径上顶点的个数),如图3—10所示。图中各顶点分布在3个层上,同一层上的顶点距离源点的距离是相同的。广度优先搜索就是沿着从1~3的层次顺序来遍历各个顶点,并在遍历的过程中形成了一棵树,称之为广度优先搜索生成树,树的分支总是连接不同层上的顶点,如图3—10中粗线所连。由源点沿生成树分支到达其余顶点的距离都是最近的(可以用层号来描述其远近)。因此对于无权图,可用广度优先搜索遍历的方法来求最短路径。而对于有权图,当图中各个边的权值相同的时候,就可以类比为无权图(无权图可理解为各边权值为1),因为各边没有了权的大小之分,则同样可以用广度优先搜索遍历的方式来求最短路径,所以Ⅰ正确。
Ⅱ:从图中的一个顶点进行广度优先搜索可以将与这个顶点连通的顶点全部遍历到,也就找到了该顶点所在的连通分量,因此广度优先遍历可以求出无向图的所有连通分量,所以Ⅱ正确。
Ⅲ:广度优先遍历算法应该是类似于树中的层次遍历算法,所以Ⅲ错误。
综上所述,Ⅰ、Ⅱ正确。
补充:分别使用邻接表、邻接矩阵进行广度、深度优先遍历的时间、空间复杂度的总结。
(1)对于有n个顶点e条边的图采用邻接表表示时,进行深度优先遍历的时间复杂度是O(n+e),空间复杂度是O(n)。
(2)对于有n个顶点e条边的图采用邻接矩阵表示时,进行深度优先遍历的时间复杂度是O(n
2
)。
(3)对于有n个顶点e条边的图采用邻接表表示时,进行广度优先遍历的时间复杂度是 O(n+e),空间复杂度是O(n)。
(4)对于有n个顶点e条边的图采用邻接矩阵表示时,进行广度优先遍历的时间复杂度是 O(n
2
)。
转载请注明原文地址:https://kaotiyun.com/show/9JRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
开皇三年,隋文帝下令州县官吏根据户籍簿上登记的年龄,来核对本人体貌,以防诈老诈小逃避租役,是为()。
下列有关曲辕犁的表述正确的是()①曲辕犁早在中国汉代即已使用了②曲辕犁在中国出现至少比欧洲早一千多年③我国古代的农业工具和农耕技术曾长期居世界领先地位④处于“蒸汽时代”的欧洲农业技术革新,滞后于同时代工业的发展
古文经学家()为了反对今文经派根据隶定的古书穿凿附会而曲解经文,于是编成一部《说文解字》,共收小篆及其他古文字9353个,逐字注释其形体音义。
下列关于国际联盟及其活动的叙述,正确的是()。
“文化大革命”结束后,在纠正“文化大革命”错误的过程中,整个过程受到()的严重阻碍。
1947年,苏联一些农村的干部和群众,为了调动广大群众生产积极性,在管理制度方面进行改革,其主要措施是()。
在阿拉伯()统治时期,阿拉伯军队曾与当时中国的唐朝军队发生冲突。
下列选项中,不属于选官制度的是()
阅读以下史料,结合相关背景知识,分析古巴比伦社会的等级制度和奴隶制度。《汉谟拉比法典》(节录)第七条自由民从自由民之子或自由民之奴隶手中买得或为之保管银或金。或奴隶,或女奴,或牛,或羊,或驴,或不论任何物,而无证人及契约者,是为窃贼,
linkNODE(intitem,link1,linkr){lnikt=malloc(sizeof*t);t->item=item;t->1=1;t->r=r;returnt;}lin
随机试题
患者,女,50岁。到某社区卫生服务中心就诊,主诉:月经不规律1年多,近4个月月经未来潮,放置带铜IUD13年,检查已排除妊娠。处理措施首先应考虑
引起抗利尿激素分泌的最敏感因素是
A.直接扩散B.上行性感染C.透壁性感染D.血行播散E.淋巴感染女性淋菌性腹膜炎的常见感染途径是
甲自来水厂(增值税一般纳税人)销售自产的自来水,2015年12月取得含税销售收入30万元,当期外购设备,取得增值税专用发票上注明进项税额为4万元,甲自来水厂销售自来水选择按征收率缴纳增值税。则下列说法正确的是()。
对从业人员来说,所谓职业化指的是从业人员工作状态的()。
地球上最大的淡水资源库是()。
(2006年单选20)全国人民代表大会常务委员会对国务院制定的同宪法相抵触的行政法规()。
设D是以(1,1),(-1,1)为顶点的三角形区域,D1是D在第一象限的部分,且f(x,y)-xy+(x,y)dxdy,其中f(x,y)在D上连续,则()
J.Martin指出,以下因素:Ⅰ.程序的适应性差Ⅱ.数据格式的不一致导致数据的共享性差Ⅲ.系统开发方法选择不当Ⅳ.开发工具选择不当哪个(些)是造成数据处理生产效率低的主要原因?
A、Theyeattoomuchforlunch.B、Theysleeptoolittleatnight.C、Theirbodytemperaturesbecomelower.D、Theweatherbecomesa
最新回复
(
0
)