首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知某图的邻接表如图4-12所示。 ①此邻接表所对应的无向图为(14)。 ②此图由F开始的深度优先遍历为(15)。 ③此图由9开始的深度优先遍历的支撑树为(16)。 ④此图由F开始的广度优先遍历为(17)。 ⑤此
已知某图的邻接表如图4-12所示。 ①此邻接表所对应的无向图为(14)。 ②此图由F开始的深度优先遍历为(15)。 ③此图由9开始的深度优先遍历的支撑树为(16)。 ④此图由F开始的广度优先遍历为(17)。 ⑤此
admin
2019-03-04
38
问题
已知某图的邻接表如图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
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
某公司按总价合同方式约定订购3000米高规格的铜缆。由于建设单位原因,工期暂停了半个月,待恢复施工后,承建单位以近期铜价上涨为理由,要求建设单位赔偿购买电缆增加的费用,并要求适当延长工期。以下说法中,(47)是正确的。
已知某系统由ABCDEF六个活动构成,项目实习人员根据活动逻辑关系及历时等信息绘制了该系统的网络图,并给出了该系统的工期为9周。项目组其他成员纷纷提出意见。以下意见中,____________是正确的。
根据GB/T12504-2008《计算机软件质量保证计划规范》的相关规定,以下评审和检查工作中,___________不是必须进行的。
___________指在软件维护阶段,为了检测由于代码修改而可能引入的错误所进行的测试活动。
在信息系统安全保护中,依据安全策略控制用户对文件、数据库表等客体的访问属于()安全管理。
存储转发是网络传输的一种形式,其问题是不确定在每个节点上的延迟时间。克服该问题最有效的方式是()。
(2009上集管)在项目结束阶段,大量的行政管理问题必须得到解决。一个重要问题是评估项目有效性。完成这项评估的方法之一是______。
(2012上集管)如果一个配置项的版本号为1.1,那么这个配置项处于______状态。
(2010上项管)T和H分别作为系统需求分析师和软件设计工程师,参与①、②、③、④四个软件的开发工作。T的工作必须发生在H开始工作之前。每个软件开发工作需要的工时如下表所示:在最短的软件开发工序中,单独压缩______对进一步加快进度没有帮助。
(2009上网工)两个公司希望通过Internet传输大量敏感数据,从信息源到目的地之间的传输数据以密文形式出现,而且不希望由于在传输结点使用特殊的安全单元而增加开支,最合适的加密方式是______(1),使用会话密钥算法效率最高的是______(2)。
随机试题
[2014]ABC会计师事务所的A注册会计师担任多家被审计单位2013年度财务报表审计的项目合伙人,遇到下列事项:(3)丙公司大部分采购和销售交易为关联方交易,管理层在2013年度财务报表附注中披露关联方交易价格公允,由于缺乏公开市场数据,A注册
边缘层
A.肝经B.肾经C.脾经D.心经
阿米巴痢疾肠道溃疡的特点是
可以有效防止不宜晾的中药的生虫、发霉的低温贮存温度是()
下列各项中,不属于比较优势原则应用的有()。
下列改革措施中,不属于北魏孝文帝时期的是
视图是【】的表,其内容是根据查询定义的。
Youwillhearfivedifferentbusinesspeopletalkingaboutcorporations.Foreachextracttherearetwotasks.ForTaskOne,cho
Whenyoucallthepolice,thepolicedispatcherhastolocatethecarnearestyouthatisfreetorespond.Thismeansthedispat
最新回复
(
0
)