首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列说法正确的是( )。 Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题 Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量 Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
下列说法正确的是( )。 Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题 Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量 Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
admin
2022-06-07
46
问题
下列说法正确的是( )。
Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题
Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量
Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
选项
A、仅Ⅰ、Ⅱ
B、仅Ⅱ、Ⅲ
C、仅Ⅱ
D、仅Ⅰ、Ⅲ
答案
A
解析
Ⅰ:对于无权图,广度优先搜索总是按照距离源点由近到远来遍历图中每个顶点(这里的距离是指当前顶点到源点路径上顶点的个数),如图3-10所示。图中各顶点分布在3个层上,同一层上的顶点距离源点的距离是相同的。广度优先搜索就是沿着从1~3的层次顺序来遍历各个顶点,并在遍历的过程中形成了一棵树,称之为广度优先搜索生成树,树的分支总是连接不同层上的点,如图3-10中粗线所连。由源点沿生成树分支到达其余顶点的距离都是最近的(可以用层号来描述其远近)。因此对于无权图,可用广度优先搜索遍历的方法来求最短路径。而对于有权图,当图中各个边的权值相同的时候,就可以类比为无权图(无权图可理解为各边权值为1),因为各边没有了权的大小之分,则同样可以用广度优先搜索遍历的方式来求最短路径,所以Ⅰ正确。
Ⅱ:从图中的一个顶点进行广度优先搜索可以将与这个顶点连通的顶点全部遍历到,也就找到了该顶点所在的连通分量,因此广度优先遍历可以求出无向图的所有连通分量,所以Ⅱ正确。
Ⅲ:广度优先遍历算法应该是类似于树中的层次遍历算法,所以Ⅲ错误。
综上所述,Ⅰ、Ⅱ正确。
转载请注明原文地址:https://kaotiyun.com/show/Ut3i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
调用(),系统会为文件创建文件控制块。
某计算机的存储系统由Cache一主存系统构成,Cache的存取周期为10ns,主存的存取周期为50ns。在CPU执行一段程序时,Cache完成存取的次数为4800次.主存完成的存取次数为200次,该Cache一主存系统的效率是()。
已知有向图G=(V,A),其中V={a,b,c,d,e},A={,,,,,},对该图进行拓扑排序,下面序列中不是拓扑排序的是().,
1、2、3、4顺序入栈(起始为空栈),只要栈不空即可出栈,不可能的序列是()。
下面关于电子邮件的说法中,不正确的是()。
某调制解调器同时使用幅移键控和相移键控,采用0、π/2、π和3/2π四种相位,每种相位又都有2个不同的幅值,问在波特率为1200的情况下数据速率是()。
某局域网采用CSMA/CD协议实现介质访问控制,数据传输速率为10Mbit/s,主机甲和主机乙之间的距离为2km,信号传播速度为200000km/s。请回答下列问题,要求说明理由或写出计算过程。若网络不存在任何冲突与差错,主机甲总是以标准的最长以太网数
下列选项中,满足短任务优先且不会发生饥饿现象的调度算法是____。
在请求分页存储管理中,若采用FIFO的页面淘汰算法,当分配的页面数增加时,缺页中断的次数()。
以下数据结构中,()是线性数据结构。
随机试题
密度实质是以对数级表示的,理由是
患者,女,35岁。高处坠落,左枕着地,进行性意识障碍,1小时后右侧瞳孔散大。最可能的诊断是
图示一矩形断面通风管道,断面尺寸为1.2m×0.6m,空气密度P=1.20kg/m3,流速v=16.2m/s,沿程阻力系数λ=0.0145,流程长度L=12m的沿程压强损失为:
配套的五保、水土保持和安全等设施,应与主体工程同时()。
3,8,6,ll,9,14,(),()
文明是文化的高级形态,是文化的结晶体。文化是文明的初级形态、原生态,只有经过_______的固化的成分才是文明。文化是_______,反映人类社会进步的过程;文明是_______,表现人类社会发展的成果。填入划横线部分最恰当的一项是:
甲将一幅古画交给乙进行装裱,该合同在性质上属于
ln3
设矩阵若向量都是方程组Ax=0的解,试证r(A)=2;
Itisdifficulttoimaginewhatlifewouldbelikewithoutmemory.Themeaningsofthousandsofeverydayperceptions,thebases
最新回复
(
0
)