首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列说法正确的是( )。 Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题 Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量 Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
下列说法正确的是( )。 Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题 Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量 Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
admin
2022-06-07
23
问题
下列说法正确的是( )。
Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题
Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量
Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
选项
A、仅Ⅰ、Ⅱ
B、仅Ⅱ、Ⅲ
C、仅Ⅱ
D、仅Ⅰ、Ⅲ
答案
A
解析
Ⅰ:对于无权图,广度优先搜索总是按照距离源点由近到远来遍历图中每个顶点(这里的距离是指当前顶点到源点路径上顶点的个数),如图3-10所示。图中各顶点分布在3个层上,同一层上的顶点距离源点的距离是相同的。广度优先搜索就是沿着从1~3的层次顺序来遍历各个顶点,并在遍历的过程中形成了一棵树,称之为广度优先搜索生成树,树的分支总是连接不同层上的点,如图3-10中粗线所连。由源点沿生成树分支到达其余顶点的距离都是最近的(可以用层号来描述其远近)。因此对于无权图,可用广度优先搜索遍历的方法来求最短路径。而对于有权图,当图中各个边的权值相同的时候,就可以类比为无权图(无权图可理解为各边权值为1),因为各边没有了权的大小之分,则同样可以用广度优先搜索遍历的方式来求最短路径,所以Ⅰ正确。
Ⅱ:从图中的一个顶点进行广度优先搜索可以将与这个顶点连通的顶点全部遍历到,也就找到了该顶点所在的连通分量,因此广度优先遍历可以求出无向图的所有连通分量,所以Ⅱ正确。
Ⅲ:广度优先遍历算法应该是类似于树中的层次遍历算法,所以Ⅲ错误。
综上所述,Ⅰ、Ⅱ正确。
转载请注明原文地址:https://kaotiyun.com/show/Ut3i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
已知一个由正数组成的序列a1,a2,…,an,在这个序列中的元素既有正整数也有负整数。我们定义SUMk,l=ak+ak+1+……+al为当前序列的子段之和。如果在某一子段上全部都是负数,我们定义其子段之和为0。如果子段之和为正整数,那么就保留其为子段之和。
利用逐点插入建立序列(50,72,43,85,75,20,35,45,65,30)对应的二叉排序树以后,要查找元素30要进行元素间的比较次数是()。
请求分页管理系统中,假设某进程的页表内容如下表所示。页面大小为4KB,一次内存的访问时间是100ns,一次快表(TLB)的访问时间是10ns,处理一次缺页的平均时间为108ns(已含更新TLB和页表的时间),进程的驻留集大小固定为2,采用最近最少使用置
设某计算机有四个中断源,优先顺序按1→2→3→4降序排列,若1、2、3、4中断源的服务程序中对应的屏蔽字分别为1110、0100、0110、1111,试写出这四个中断源的中断处理次序(按降序排列)。若四个中断源同时有中断请求,画出CPU执行程序的轨迹。
CPU的中断周期前可能是()。
设与某资源关联的信号量初值为3,当前值为1。若M表示该资源的可用个数,N表示等待该资源的进程数,则M、N分别是____。
有两个并发执行的进程P1和P2,共享初值为1的变量x。p1对x加1,P2对x减1。加1和减1操作的指令序列分别如下所示。//加1操作//减1操作loadR1,x//取x到寄存器R1中loadR2,xincR1decR2storex,R1//将R1的内容存入
已知字符串S为“abaabaabacacaabaabcc”,模式串t为“abaabc”。采用KMP算法进行匹配,第一次出现“失配”(s[i]≠t[j])时,i-j=5,则下次开始匹配时,i和j的值分别是_______。
在页式虚拟存储管理系统中,采用某些页面置换算法,会出现Belady异常现象,即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。下列算法中,可能出现Belady异常现象的是_______。Ⅰ.LRU算法Ⅱ.FIFO算法Ⅲ.OFT算法
已知一算术表达式的中缀形式为A+B*C-D/E,后缀形式为ABC*+DE/一,其前缀形式为()。
随机试题
急救止血法有()
痰壅气逆食滞,症见咳嗽喘逆,痰多胸痞,食少难消,舌苔白腻,脉滑。宜选用
与种属无关,存在于人、动物及微生物之间的共同抗原称为
患者,女性,68岁,晨起发现左手不能上举,左腿行走困难,急诊入院。查体:神志清,左上肢肌力Ⅳ级,左下肢肌力Ⅲ级,初步考虑为
A.湿度B.日光C.温度D.成分E.氧化中药饮片变色的内因是()
在城市蓝线内所禁止的活动不包括()
随同产品出售不单独计价的包装物,应于包装物发出时,作为包装费用,计人其他业务成本。()
下列描述中,属于SWOT分析中的机会的有()。
谈话法特别有助于激发学生的思维,培养他们独立思考和______的能力,谈话法可分为______和启发谈话两种。
环境移民,是指人类生存的自然环境和人居环境受到突发或渐近式的不利影响而产生的各种人口迁移行为,包括自愿的、非自愿的,事后被迫的、预先计划的,暂时的、永久性的,个体和家庭自发的、政府主导的移民类型。根据上述定义,下列不属于环境移民的是()。
最新回复
(
0
)