首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知某图的邻接表如图4-12所示。 ①此邻接表所对应的无向图为(14)。 ②此图由F开始的深度优先遍历为(15)。 ③此图由9开始的深度优先遍历的支撑树为(16)。 ④此图由F开始的广度优先遍历为(17)。 ⑤此
已知某图的邻接表如图4-12所示。 ①此邻接表所对应的无向图为(14)。 ②此图由F开始的深度优先遍历为(15)。 ③此图由9开始的深度优先遍历的支撑树为(16)。 ④此图由F开始的广度优先遍历为(17)。 ⑤此
admin
2019-03-04
49
问题
已知某图的邻接表如图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
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
某企业有一投资方案:每年生产某种设备1500台,生产成本每台700元,预计售价每台1800元,估算投资额为800万元。该投资方案寿命为7年。假设年产量、每台售价和投资额均有可能在±20%的范围内变动,就这三个不确定因素对投资回收期的敏感性分析得到了下表中的
一般而言,大型软件系统中实现数据压缩功能的模块,工作在OSI参考模型的(21)。
以下关于信息系统运维的叙述中,(18)是不正确的。
按照软件配置管理的基本指导思想,受控制的对象应是__________(62)。实施软件配置管理包括4个最基本的活动,其中不包括__________(63)。(63)
在统一建模语言中,___________的主要目的是帮助开发团队以一种可视化的方式理解系统的功能需求,包括基于基本流程的“角色”关系等。
大数据对产品、企业和产业有着深刻的影响。把信息技术看作是辅助或服务性的工具已经成为过时的观念,管理者应该认识到信息技术的广泛影响,以及怎样利用信息技术来创造有力而持久的竞争优势,__________将是未来经济社会发展的一个重要特征。
质量控制的方法、技术和工具有很多,其中(1)可以用来分析过程是否稳定、是否发生了异常情况。(2)直观地反映了项目中可能出现的问题与各种潜在原因之间的关系。(1)
(2007上监理)按照软件配置管理的原始指导思想,受控制的对象应是_____(1)。实施软件配置管理包括4个最基本的活动,其中不包括_____(2)。(1)
(2014上项管)某政府公开招标项目,在编制了招标文件并发布了招标公告后,招标人应随即______。
(2010下集管)某项目有五个独立的子项目,小张和小李各自独立完成项目所需的时间如下表所示:则如下四种安排中______的工期最短。
随机试题
A、①B、②C、③D、④C
简述银行控制流动性风险的方式。
国内药品生产,经营企业及医疗单位采购进口药品时,供货单位必须提供的合法证件是
对邀请招标来讲,投标单位的资格审查在( )时进行。
建设工程质量控制系统和建筑企业或其他组织机构按照GB/T1900标准建立的质量管理体系的区别有( )。
证券服务机构是指依法设立的从事证券服务业务的法人机构,下列属于证券服务机构的是( )。
导游人员必须在送站前24小时与游客或散客小包价旅游团确认送站的()。
根据下面材料回答下列题。下列各项中,笔记本电脑上网的网民数同比增长率最低的是()。
The(67)defines the phases that connect the beginning of a project to its end.
Thelevelofdiscriminationhasvariedenormouslyinthehistoryofhumansocieties,fromgenocidewhereethnicsarekilledoff
最新回复
(
0
)