首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知某图的邻接表如图4-12所示。 ①此邻接表所对应的无向图为(14)。 ②此图由F开始的深度优先遍历为(15)。 ③此图由9开始的深度优先遍历的支撑树为(16)。 ④此图由F开始的广度优先遍历为(17)。 ⑤此
已知某图的邻接表如图4-12所示。 ①此邻接表所对应的无向图为(14)。 ②此图由F开始的深度优先遍历为(15)。 ③此图由9开始的深度优先遍历的支撑树为(16)。 ④此图由F开始的广度优先遍历为(17)。 ⑤此
admin
2019-03-04
40
问题
已知某图的邻接表如图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
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
有一种游戏为掷两颗骰子,其规则为:当点数和为2时,游戏者输9元;点数和为7或者11时,游戏者赢x元;其他点数时均输1元。依据EMV准则,当X超过___________元时才对游戏者有利。
在需求跟踪过程中,检查设计文档、代码、测试用例等工作成果是否都能在《产品需求规格说明书》中找到出处的方法属于___________。
项目组合管理是一个保证组织内所有项目都经过风险和收益分析及平衡的方法论。作为公司的项目经理进行项目组合管理时,___________应是重点考虑的要素。
以下关于WLAN安全机制的叙述中,__________是正确的。
(2010上系分)某大型移动通信运营商欲开发一个新的应用系统以替换原有系统。在需求分析阶段,为尽快从已有系统文档资料和用户处获取整体系统需求,采用______的方法捕获需求最为合适。
(2010下集管)Web服务(WebService)定义了一种松散的、粗粒度的分布式计算模式。Web服务的提供者利用①描述Web服务,Web服务的使用者通过②来发现服务,两者之间的通信采用③协议。以上①②③处依次应是______。
(2009上项管)安全审计是保障计算机系统安全的重要手段之一,其作用不包括______。
(2010下集管)某项目有五个独立的子项目,小张和小李各自独立完成项目所需的时间如下表所示:则如下四种安排中______的工期最短。
(2014下集管)根据《信息技术软件工程术语GB/T11457—2006》的规定,______是计算机程序中的一个点,在此点检验或记录程序的状态、状况或结果。
(2009下架构)公司总部与分部之间需要传输大量数据,在保障数据安全的同时又要兼顾密钥算法效率,最合适的加密算法是______。
随机试题
既能用于新的陆上网络,又可对现有系统进行升级改造,特别适用于DWDM系统传输的是()光纤。
以下对施工企业项目经理的工作性质的说明,正确的是( )。
下列属于影响可转换公司债券价值的因素为()。
关于库存商品、发出商品的核算,下列说法正确的有()。
《中华人民共和国税收征收管理法》第八十八条规定,纳税人、扣缴义务人、纳税担保人同税务机关在纳税上发生争议时,必须先依照税务机关的纳税决定缴纳或者解缴税款及滞纳金或者提供相应的担保,然后可以依法申请行政复议;对行政复议决定不服的,可以依法向人民法院起诉。这体
根据《企业所得税法》的规定,企业的下列各项支出,在计算应纳税所得额时,准予从收入总额中直接扣除的有()。
镜泊湖是大约1万年前,由于()而形成的。
教育电视台是指教育行政部门开办的专业电视台。()
TheAmericanFamilyIntheAmericanfamilythehusbandandwifeusuallyshareimportantdecisionmaking.Whenthechildrenare(5
Therearethreekindsofgoals:short-term,medium-rangeandlong-termgoals.Short-rangegoalsarethosethatusuallydealwith
最新回复
(
0
)