首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知某图的邻接表如图4-12所示。 ①此邻接表所对应的无向图为(14)。 ②此图由F开始的深度优先遍历为(15)。 ③此图由9开始的深度优先遍历的支撑树为(16)。 ④此图由F开始的广度优先遍历为(17)。 ⑤此
已知某图的邻接表如图4-12所示。 ①此邻接表所对应的无向图为(14)。 ②此图由F开始的深度优先遍历为(15)。 ③此图由9开始的深度优先遍历的支撑树为(16)。 ④此图由F开始的广度优先遍历为(17)。 ⑤此
admin
2019-03-04
48
问题
已知某图的邻接表如图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
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
配置管理是软件生命周期中的重要控制过程,在软件开发过程中扮演着重要的角色。按照GB/T11457一2006《软件工程术语》的描述,以下关于配置管理基线的叙述中,(13)是不正确的。
以下关于网络协议的叙述中,_________是正确的。
从任一节点走到相连的下一节点算一步,在下图中,从A节点到B节点至少需要走()步。
以下关于外包和外包管理的叙述中,不正确的是:()。
依据GB/T16260.2—2006《软件工程产品质量第2部分外部质量的度量》,评估软件的帮助系统和文档的有效性是对软件进行()。
绘制数据流图是软件设计过程的一部分,用以表明信息在系统中的流向。数据流图的基本组成部分包括()。
在面向对象系统中,()关系表示一个较大的“整体”类包含一个或多个“部分”类。
虽然不同的操作系统可能装有不同的浏览器,但是这些浏览器都符合()协议。
(2008上项管)测试是信息系统工程质量监理的重要手段之一,这是由信息系统工程的特点所决定,测试结果是判断信息系统工程质量最直接的依据之一。在整个质量控制过程中,可能存在承建单位、监理单位、建设单位以及专业的测试机构对工程的测试。各方的职责和工作重点有所不
(2005上项管)项目小组建设对于项目的成功很重要,因此,项目经理想考察项目小组工作的技术环境如何,有关信息可以在______中找到。
随机试题
某孕妇怀孕24周,被诊断为妊娠子痫,病情较重危及孕妇生命,医生决定给予引产。此医疗处置符合哪项道德原则
甲公司欠银行200万元贷款,现该公司将一部分资产分离出去,成立乙公司。则在公司分立后,应由谁对这笔债务承担清偿责任?()
下列关于土地证书填写方法叙述不正确的是()。
利率提高会导致房地产价格上升,需求加大。()
二氧化氯极不稳定,常以水溶液形式或现场制取使用,试计算50000m3/d规模的水厂,如采用NaClO2与Cl2制取ClO2,平均加气量为1mg/L。计划建造一座40%NaClO2储存量为30天的储液池,该池容积应为()。(溶液相对密度以1计,
建设工程信息分为组织类、管理类、经济类和技术类多种。下列项目信息中,属于经济类信息的是()。
某公司办公楼地上共9层,建筑高度为28m,耐火等级为二级,每层建筑面积为1000m2,设置为一个防火分区,该建筑为“L”形外廊式建筑,“L”形建筑长边为45.6m、短边为22.20m,均采用不燃烧材料装修,办公场所设有计算机、复印机等办公用电子设备。办公楼
公路零担货物运输系指同一货物托运人托运的货物不超过()。
某县政府依据田某的申请作出复议决定,撤销该县车管所对田某车辆的错误登记,责令其在30日内重新登记,但某县车管所拒绝进行重新登记。田某可以采取的措施是()。
下列人员可以被录用为公务员的是:
最新回复
(
0
)