下列说法正确的是( )。 Ⅰ．当各边的权值相等时，广度优先遍历算法可用来解决单源最短路径问题 Ⅱ．广度优先遍历算法可用来求无向图的所有连通分量 Ⅲ．广度优先遍历算法类似于树中的后序遍历算法

admin2022-06-07 52

问题下列说法正确的是( )。
Ⅰ．当各边的权值相等时，广度优先遍历算法可用来解决单源最短路径问题
Ⅱ．广度优先遍历算法可用来求无向图的所有连通分量
Ⅲ．广度优先遍历算法类似于树中的后序遍历算法

选项 A、仅Ⅰ、Ⅱ
B、仅Ⅱ、Ⅲ
C、仅Ⅱ
D、仅Ⅰ、Ⅲ

答案A

解析 Ⅰ：对于无权图，广度优先搜索总是按照距离源点由近到远来遍历图中每个顶点(这里的距离是指当前顶点到源点路径上顶点的个数)，如图3-10所示。图中各顶点分布在3个层上，同一层上的顶点距离源点的距离是相同的。广度优先搜索就是沿着从1～3的层次顺序来遍历各个顶点，并在遍历的过程中形成了一棵树，称之为广度优先搜索生成树，树的分支总是连接不同层上的点，如图3-10中粗线所连。由源点沿生成树分支到达其余顶点的距离都是最近的(可以用层号来描述其远近)。因此对于无权图，可用广度优先搜索遍历的方法来求最短路径。而对于有权图，当图中各个边的权值相同的时候，就可以类比为无权图(无权图可理解为各边权值为1)，因为各边没有了权的大小之分，则同样可以用广度优先搜索遍历的方式来求最短路径，所以Ⅰ正确。

Ⅱ：从图中的一个顶点进行广度优先搜索可以将与这个顶点连通的顶点全部遍历到，也就找到了该顶点所在的连通分量，因此广度优先遍历可以求出无向图的所有连通分量，所以Ⅱ正确。
Ⅲ：广度优先遍历算法应该是类似于树中的层次遍历算法，所以Ⅲ错误。
综上所述，Ⅰ、Ⅱ正确。

转载请注明原文地址:https://kaotiyun.com/show/Ut3i777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

下列说法正确的是( )。 Ⅰ．当各边的权值相等时，广度优先遍历算法可用来解决单源最短路径问题 Ⅱ．广度优先遍历算法可用来求无向图的所有连通分量 Ⅲ．广度优先遍历算法类似于树中的后序遍历算法

计算机408

学硕统考专业

下列AOE网表示一项包含8个活动的工程。通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是

在操作系统中，要对并发进程进行同步的原因是()。

试编写一个建立带表头结点的双向循环链表的算法。

某公司的局域网设置如下所示，两个局域网通过路由器连接到NAT服务器上，并且通过NAT服务器连接到Internel：上。局域网1的掩码是192．168．14．0／25，局域网2的掩码是192．168．14．128／25，NAT服务器的内部IP地址为192．1

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1)，C(1)，E(2)E

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1)，C(1)，E(2)E

已知循环队列存储在一维数组A[0…n一1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是____。

若系统S1采用死锁避免方法，S2采用死锁检测方法。下列叙述中，正确的是_______。Ⅰ．S1会限制用户申请资源的顺序，而S2不会Ⅱ．S1需要进程运行所需资源总量信息，而S2不需要Ⅲ．S1不会给可能导致死锁的进程分配资源，而S2会

可供出售金融资产

男性，74岁，酗酒20余年，近来脾气暴戾，行为怪异，进而出现幻觉、狂躁等较严重的精神症状，入院后查血氨增高。该病人护理上重点要（）

左下肢深静脉血栓，如不及时治疗．最常见的并发症是

下列关于固定资产减值的表述中，符合会计准则规定的是()。

某股份有限公司的监事会提议召开临时股东大会，修改公司章程并讨论发行公司债券，该项决议由出席会议的股东所持表决权的半数以上通过即可。()

先前学习的材料对识记和回忆后学习材料的干扰作用叫倒摄抑制。()

公路客运方面：10月5日共发送客车3546车次，发送旅客5.45一人次；抵达客车1472车次，抵达旅客1.88万人次。24民航方面：10月5日共发送航班236班次，发送旅客3.25万人次；抵达航班233班次，抵达旅客2.83万人次。2017年10月

ParentsintheUnitedStatestendtoasktheirchildrenWhathappenedinthe1970s?

NoJetlag(时差反应)AnymoreMostpeoplewhotravellongdistancescomplainofjetlag(时差反应).Jetlagmakesbusinesstravelersless