首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知某图的邻接表如图4-12所示。 ①此邻接表所对应的无向图为(14)。 ②此图由F开始的深度优先遍历为(15)。 ③此图由9开始的深度优先遍历的支撑树为(16)。 ④此图由F开始的广度优先遍历为(17)。 ⑤此
已知某图的邻接表如图4-12所示。 ①此邻接表所对应的无向图为(14)。 ②此图由F开始的深度优先遍历为(15)。 ③此图由9开始的深度优先遍历的支撑树为(16)。 ④此图由F开始的广度优先遍历为(17)。 ⑤此
admin
2019-03-04
50
问题
已知某图的邻接表如图4-12所示。
①此邻接表所对应的无向图为(14)。
②此图由F开始的深度优先遍历为(15)。
③此图由9开始的深度优先遍历的支撑树为(16)。
④此图由F开始的广度优先遍历为(17)。
⑤此图由9开始的广度优先遍历的支撑树为(18)。
选项
A、
B、
C、
答案
B
解析
本题实际上是考查无向图的邻接表存储方式,以及深度、广度优先遍历。
在图的邻接表中,为图的每个顶点建立一个链表,且第i个链表中的结点代表与顶点i相关联的一条边或由顶点i出发的一条弧。有n个顶点的图,需用n个链表表示,这n个链表的头指针通常由顺序线性表存储。
第一问是求邻接表所对应的无向图。首先我们看邻接表的第一行链表,在这个链表中,头结点为几后继结点有G、H和M,这表示的是结点G、H、M与结点F直接相连,而题目备选答案B中F和M并不是直接相连的,因此可以排除答案B。再看邻接表的第二行链表,在这个链表中,头结点为G,后继结点有F、I、L、J和K,这表示的是结点F、I、L、J、K与结点G直接相连,而题目备选答案A中G和L并不是直接相连的,所以答案A也可以排除。这样答案也就出来了,(1)应选C。
接下来求深度优先遍历。在图中任选一顶点V为初始出发点(源点),则深度优先遍历可定义如下:首先访问出发点V,并将其标记为已访问过:然后依次从V出发搜索 y的每个邻接点W。若W未曾访问过,则以W为新的出发点继续进行深度优先遍历,直至图中所有和源点V有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点,则另选一个尚未访问的顶点作为新的源点重复上述过程,直至图中所有顶点均已被访问为止。
在本题中,以9为源点。首先访问9,然后扫描其邻接表,邻接表的第一个元素是 G,且G未被访问过,所以访问G。接下来扫描G的邻接表,G邻接表的第一个元素是F,已经访问过,所以跳过:第二个是I,I未被访问过,所以访问结点I。接下来扫描I的邻接表,I的邻接表的第一个元素是G,已经访问过,所以跳过:第二个是L,L未被访问过,所以访问结点L,依次类推。最终得到深度优先遍历序列为F、G、I、L、 J、K、H、M。所以(2)应选答案B。
求出了深度优先遍历,深度优先遍历的支撑树就好求了。支撑树实际上就是生成树,也就是留下深度优先遍历时经过的边,去除其余的边而得到的树。如图4-15所示。
图4-15中的实线表示深度优先遍历经过的边,虚线表示不经过的边,把虚线去除,便得到深度优先遍历生成树,如图4-16所示。
接下来求广度优先遍历。广度优先遍历的过程是:首先访问出发顶点y,然后访问与顶点V邻接的全部未被访问过的顶点W0,W1,…,Wk-1;接着再依次访问与顶点 W0,W1,…,Wk-1邻接的全部未被访问过的顶点。依次类推,直至图的所有顶点都被访问到,或出发顶点V所在的连通分量的全部顶点都被访问到为止。
在本题中,从F点出发。首先访问F,然后依次访问F邻接表中所有未被访问过的结点G、H、M。接着访问当前邻接表第一个元素所指邻接表的所有未被访问过的元素,即G的邻接表中所有未访问元素I、L、J、K。所以得到广度优先遍历序列F、G, H,M,I,L,J,K。
我们可以用同样的方法来求广度优先遍历的生成树,结果如图4-17所示。把虚线去除得如图4-18所示的生成树。
转载请注明原文地址:https://kaotiyun.com/show/stTZ777K
本试题收录于:
数据库系统工程师上午基础知识考试题库软考中级分类
0
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
软件需求包括功能需求、非功能需求、设计约束三个主要部分。其中()属于功能需求内容。
综合布线系统中用于连接两幢建筑物的子系统是(24)。
在以太网中,双绞线使用一(23)接口与其他网络设备连接。
某项目中多个风险的发生概率和对成本、进度、绩效的影响如下表所示:若实现成本目标为首要考虑的问题,项目团队应处理的最关键风险是()。
(2010下监理)基线(Baseline)是指一个(或一组)配置项在项目生命周期的不同时间点上通过______而进入正式受控的一种状态。
(2012下项管)在网络数据流中适当的位置插入同步点,当传输出现中断时,可以从同步的位置开始重新传输,该网络功能的控制和管理属于______。
(2014上项管)某政府公开招标项目,在编制了招标文件并发布了招标公告后,招标人应随即______。
(2013下集管)(2010上系分)项目管理是保证项目成功的核心手段,在项目实施过程中具有重大作用。_____(1)是项目管理的重要元素,是项目实施的基础;_____(2)要确定哪些工作是项目应该做的,哪些工作不应该包含在项目中;_____(3)采用科学的
(2007上系分)关于UML中的状态图和活动图的叙述中,______是错误的。
(2009下架构)公司总部与分部之间需要传输大量数据,在保障数据安全的同时又要兼顾密钥算法效率,最合适的加密算法是______。
随机试题
人类对森林的过度砍伐,对草原和湿地的破坏,工业和汽车排放大量的CO2,是我国喜马拉雅山的冰峰不断消融。从因果关系上看,这属于()。
You______thisbook.Youcanborrowitfromthelibrary.
Passingbyasupermarket,Iwasattractedbyalongqueueofpeoplewithbigplasticbagsfullofkindsofgoodstheyboughtout
下列关于胆汁的叙述,哪项是错误的
A、红霉素B、琥乙红霉素C、克拉霉素D、阿齐霉素E、罗红霉素在胃酸中稳定且无味的抗生素是()。
按照消费者对产品两种属性的重视程度进行划分,就会形成不同偏好的细分市场,这时会出现()模式。
用一种钢制的活动防护装置或活动支撑,通过软弱含水层,特别是河底、海底或者城市中心区修建隧道的方法是()。[2012年10月真题]
会计从业资格管理机构作出准予颁发会计从业资格证书的决定,应当自作出决定之日起()内向申请人颁发会计从业资格证书。
做学问,“要大处着眼,小处下手”。由博入专,不可急功近利,能大处着眼,为学方不致流于__________,而有裨益于世;能小处下手,方不致流于__________,所以做学问千万不要求速效。依次填入画横线部分最恰当的一项是()。
把下面的六个图形分为两类,使每一类图形都有各自的共同特征或规律,分类正确的一项是:
最新回复
(
0
)