以下关于图的遍历的叙述中，正确的是( )。

admin2019-04-22 19

问题以下关于图的遍历的叙述中，正确的是( )。

选项 A、图的遍历是从给定的源点出发对每一个顶点仅访问一次的过程
B、图的深度优先遍历方法不适用于无向图
C、使用队列对图进行广度优先遍历
D、图中有回路时则无法进行遍历

答案C

解析本题考查数据结构基础知识。
图的遍历是指对图中所有顶点进行访问且只访问一次的过程。因为图的任一个结点都可能与其余顶点相邻接，所以在访问了某个顶点之后，可能沿着某路径又回到该结点上。因此为了避免顶点的重复访问，在图的遍历过程中，必须对已访问过的顶点进行标记。深度优先遍历和广度优先遍历是两种遍历图的基本方法。
图的广度优先遍历方法为：从图中某个顶点1，出发，在访问了v之后依次访问v的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点"被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时还有未被访问的顶点，则另选图中的一个未被访问的顶点作为起点，重复上述过程，直至图中所有的顶点都被访问到为止。
广度优先遍历图的特点是尽可能先进行横向搜索，即最先访问的顶点的邻接点也先被访问。为此，引入队列来保存已访问过的顶点序列，即每当一个顶点被访问后，就将其放入队中，当队头顶点出队时，就访问其未被访问的邻接点并令这些邻接顶点入队。

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

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

以下关于图的遍历的叙述中，正确的是( )。

软件设计师上午基础知识考试

软考中级

主机甲向主机乙发送了一个TCP报文段，SYN字段为“1”，序列号字段的值为2000，若主机乙同意建立连接，则发送给主机甲的报文段可能为(22)，若主机乙不同意建立连接，则(23)字段置“1”。(23)

某软件项目的活动图如下图所示，其中顶点表示项目里程碑，连接顶点的边表示包含的活动，边上的数字表示活动的持续时间(天)。由于某种原因，现在需要同一个开发人员完成BC和BD，则完成该项目的最少时间为_____________天。

建筑物综合布线系统中的干线子系统是(66)，水平子系统是(67)。（66）

100BASE—TX交换机，一个端口通信的数据速率(全双工)最大可以达到(12)________________。

HTTP协议中，用于读取一个网页的操作方法为__________。(2010年下半年试题)

在Linux操作系统中把外部设备当作文件统一管理，外部设备文件通常放在(31)目录中。

中国企业M与美国公司L进行技术合作，合同约定M使用一项在有效期内的美国专利，但该项美国专利未在中国和其他国家提出申请。对于M销售依照该专利生产的产品，以下叙述正确的是____________。

IIS服务支持的身份验证方法中，需要利用明文在网络上传递用户名和密码的是______。

阅读下列C++程序和程序说明，将应填入(n)处的字句写在对应栏内。【说明】设单链表的结点类和链表类的定义如下，链表不带有表头结点。请填空：#include＜iostream．h＞#include＜assert．h＞templ

Allthings______,herpaperisofgreatvalue.

裂隙灯显微镜可配备的附件包括

A．羌活B．苍耳子C．辛夷D．藁本E．白芷善治太阳头痛的药物是()

评标委员会由招标代理机构熟悉相关业务的代表和不少于成员总数（）的技术、经济等专家组成，成员人数为5人以上单数。

由同种活动和连续有关行为形成的组群，叫做()。

四种应力状态分别如图5-104所示，按照第三强度理论，其相当应力最大是()。

股票价格走势的压力线是()。

诗歌的表现手法中有欲扬先抑或欲抑先扬的手法，下列诗句运用了这种抑扬结合表现手法的是()。

下列关于线性表和链表的比较，叙述错误的是()。