首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列说法正确的是( )。 Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题 Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量 Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
下列说法正确的是( )。 Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题 Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量 Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
admin
2022-06-07
44
问题
下列说法正确的是( )。
Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题
Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量
Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
选项
A、仅Ⅰ、Ⅱ
B、仅Ⅱ、Ⅲ
C、仅Ⅱ
D、仅Ⅰ、Ⅲ
答案
A
解析
Ⅰ:对于无权图,广度优先搜索总是按照距离源点由近到远来遍历图中每个顶点(这里的距离是指当前顶点到源点路径上顶点的个数),如图3-10所示。图中各顶点分布在3个层上,同一层上的顶点距离源点的距离是相同的。广度优先搜索就是沿着从1~3的层次顺序来遍历各个顶点,并在遍历的过程中形成了一棵树,称之为广度优先搜索生成树,树的分支总是连接不同层上的点,如图3-10中粗线所连。由源点沿生成树分支到达其余顶点的距离都是最近的(可以用层号来描述其远近)。因此对于无权图,可用广度优先搜索遍历的方法来求最短路径。而对于有权图,当图中各个边的权值相同的时候,就可以类比为无权图(无权图可理解为各边权值为1),因为各边没有了权的大小之分,则同样可以用广度优先搜索遍历的方式来求最短路径,所以Ⅰ正确。
Ⅱ:从图中的一个顶点进行广度优先搜索可以将与这个顶点连通的顶点全部遍历到,也就找到了该顶点所在的连通分量,因此广度优先遍历可以求出无向图的所有连通分量,所以Ⅱ正确。
Ⅲ:广度优先遍历算法应该是类似于树中的层次遍历算法,所以Ⅲ错误。
综上所述,Ⅰ、Ⅱ正确。
转载请注明原文地址:https://kaotiyun.com/show/Ut3i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
设将n(n,1)个整数存放到一维数组R中,试设计一个在时间和空间两方面尽可能有效的算法,将R中保有的序列循环左移P(0<P<n)个位置,即将R中的数据由(X1,X2,…,Xn)变换为(XP,XP+1,…,XN,X1,XP-1),要求:(1)给出算
已知有向图G=(V,A),其中V={a,b,c,d,e},A={,,,,,},对该图进行拓扑排序,下面序列中不是拓扑排序的是().,
在虚拟地址和物理地址均为32位、页大小为4KB的某种体系结构中,假定存在下表所示的地址映像关系,问:对应于下列虚拟地址的物理地址分别是什么?(1)22433007H(2)13385ABCH(3)ABC89011H
设算术表达式由字符串b表示,其中可以包括三种括号:圆括号、方括号以及花括号,嵌套的顺序随意,如:“{[()]()}”。试编写算法,实现判定给定表达式中所含括号是否正确配对的出现。
为实现快速排序算法,待排序序列宜采用的存储方式是____。
已知一个整数序列A=(a0,a1,…,an+1),其中0≤ai<n(0≤i<n)。若存在ap1=ap2=…=apm=x且m>n/2(0≤pk<n,1≤k≤m),则称x为A的主元素。例如A=(0,5,5,3,5,7,5,5),则5为主元素;又如A=(0,5,
将关键字序列(7,8,30,11,18,9,14)散列存储到散列表中,散列表的存储空间是一个下标从0开始的一维数组,散列函数为:H(key)=(key×3)MOD7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。请画出所构造的散列表。
用哈希(散列)方法处理冲突(碰撞)时可能出现堆积(聚集)现象,下列选项中,会受堆积现象直接影响的是_______。
下列关于总线仲裁方式的说法中,不正确的是()。
队尾已到达一维数组的最高下标,不能再插入元素,然而队中元素个数小于队列的长度,这种现象称作()。
随机试题
双层墙能提高隔声能力主要是下列哪项措施起作用?[2005年第7题]
A.tRNAB.mRNAC.rRNAD.hnRNAE.snRNA作为核糖体组成成分,参与蛋白质合成的是
A.应逐件抽样检验B.可不开箱检查C.可不打开最小包装D.应至少检查一个最小包装根据《药品经营监督管理办法》,药品批发企业对每次到货药品进行抽样验收的要求是同批号的药品
房地产经纪人员签订房地产经纪服务合同时,正确的做法有()。
2014年4月,甲公司委托乙仓库保管M机床,双方约定:保管期限为2个月,甲公司在保管期满提取M机床时一次付清保管费用。2014年6月,保管合同履行完毕。2014年7月,甲公司将M机床出租给丙公司,租期1年。租赁期间,甲公司计划以M机床作抵押从丁公司购进一
关于固定汇率制度,下列表述正确的是()。
下列对ISO900l标准的理解,正确的有()。
针对“人肉搜索”,你认为应该加强监督权还是应该保护民众的隐私?
请根据下图所示网络结构回答下列问题。如果该网络内服务器群的IP地址为172.19.52.100~172.19.52.126和172.19.53.100~172.19.53.200,要求用一种设备对服务器群提供如下保护:检测发送到服务器群的数据包,如果
两次运行下列的程序,如果从键盘上分别输入3和1,则输出结果是()。main(){intx;scanf("%d",&x);if(x++>2)printf("%d",x);els
最新回复
(
0
)