首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于下图G,按下列条件试分别写出从顶点O出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 (1)假定它们均采用邻接矩阵表示; (2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。
对于下图G,按下列条件试分别写出从顶点O出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 (1)假定它们均采用邻接矩阵表示; (2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。
admin
2013-07-12
30
问题
对于下图G,按下列条件试分别写出从顶点O出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。
(1)假定它们均采用邻接矩阵表示;
(2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。
选项
答案
(1)采用邻接矩阵表示得到的顶点序列如下表所示: [*] (2)采用邻接表表示得到的顶点序列如下表所示: [*]
解析
导致对一个图进行遍历而得到的遍历序列不唯一的因素有许多。首先,遍历的出发顶点的选择不唯一,而得到的遍历序列显然也不是唯一的。即使遍历的出发顶点相同,采用的遍历方法若不相同,得到的结果也是不相同的。另外,即使遍历的出发顶点相同,并且采用同一种遍历方法,若图的存储结构不相同,则得到的结果也可能是不相同的。例如,对于邻接表结构而言,建立邻接表时提供边的信息的先后次序不同,边结点的链接次序也不同,从而会建立不同的邻接表;同一个图的不同邻接表结构会导致不同的遍历结果。
本题中导致对一个图进行遍历而得到的遍历序列不唯一的因素都确定下来,那么遍历序列就唯一确定下来。
本题需要先建立图G的邻接矩阵和按顶点序号从大到小的次序链接的邻接表,然后再进行深度优先和广度优先遍历。
转载请注明原文地址:https://kaotiyun.com/show/Drxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
20世纪20年代,日本面临的一度有利的国际环境开始逆转,主要原因是()。
布雷顿森林体系的建立对世界历史产生的重大影响是()。
下面条约没有涉及德国的赔款问题的是()。
“土木之变”是明与()之间的冲突导致的。
我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说,如炎帝和黄帝两个部落曾战于(),结果黄帝取得了胜利。
()的设置是清王朝实行满汉联合、以汉制汉统治方式在军事上的具体体现
与前两次工业革命相比,第三次科技革命在能源结构上的主要变化是()
阅读材料,回答问题:材料一:巴尔干半岛和东地中海地区,历来被英国视为大英帝国的生命线。大战结束前后,美国利用种种借口,千方百计渗入这个连接欧亚两大洲的重要战略地区……1947年2月21日,英国向美国国务院发出了结束援助希腊、土耳其的照会,声称国内严重的经
某计算机采用微程序控制方式,微指令字长32位,采用字段直接编码的控制方式,共有55个微命令,可分为6个互斥组,分别包含1、3、7、8、12、24个微命令。另外,该机共有5个可判定的外部条件,采用断定方式形成后续微指令地址。(1)设计该机微指令的格式,
高度为7的AVL树最少有()个结点。
随机试题
Beautyisacuriousphenomenon,oneofpermeable,shiftingboundaries.Wemaythinkweunderstandit,【C1】______wesenseiteffor
关于月经的特点.下述何项是正确的
通常货币资金总是流向最有发展潜力、能为投资者带来最大利益的地区、部门和企业,这属于金融市场的()。[2015年10月真题]
某公司2013年12月份销售收入和2014年1~2月份的预计销售收入分别为200万元、180万元、250万元。其他有关资料如下:(1)收账政策:当月销售当月收现80%,其余部分下月收回。(2)材料按下月销售收入的70%采购。付款政策:当
阅读是学生的_________行为,不应以教师的分析代替学生的阅读实践。
幼儿喜欢玩的“娃娃家”属于表演游戏。()
甲对乙说:当我的岁数是你现在的岁数时,你才4岁。乙对甲说:当我的岁数到你现在的岁数时,你将有67岁。甲乙现在各有()。
在考生文件夹下完成如下简单应用:(1)建立一个名为NEW_VIEW的视图,该视图含有选修了课程但没有参加考试(成绩字段值为NULL)的学生信息(包括“学号”、“姓名”和“系部”3个字段)。(2)建立表单MYFORM3,在表单上添加一个表格控件(名称为g
有一个事件过程,其功能是:从已存在于磁盘上的顺序文件NM1.txt中读取数据,计算读出数据的平方值,将该数据及其平方值存入新的顺序文件NM2.txt中。请填空。PrivateSubForm_Click()DimxAsSingle,yAsS
小李是东方公司的会计,利用自己所学的办公软件进行记账管理,为节省时间,同时又确保记账的准确性,她使用Excel编制了2014年3月员工工资表“Excel.xlsx”。请你根据下列要求帮助小李对该工资表进行整理和分析(提示:本题中若出现排序问题则采
最新回复
(
0
)