首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列算法说明和算法,将应填入(n)处的语句写在对应栏内。 1. 【说明】 实现连通图G的深度优先遍历(从顶点v出发)的非递归过程。 【算法】 第一步:首先访问连通图G的指定起始顶点v; 第二步:从V出发,访问一个与v(1)
阅读下列算法说明和算法,将应填入(n)处的语句写在对应栏内。 1. 【说明】 实现连通图G的深度优先遍历(从顶点v出发)的非递归过程。 【算法】 第一步:首先访问连通图G的指定起始顶点v; 第二步:从V出发,访问一个与v(1)
admin
2012-12-10
62
问题
阅读下列算法说明和算法,将应填入(n)处的语句写在对应栏内。
1. 【说明】
实现连通图G的深度优先遍历(从顶点v出发)的非递归过程。
【算法】
第一步:首先访问连通图G的指定起始顶点v;
第二步:从V出发,访问一个与v(1)p,再从顶点P出发,访问与p(2)顶点q,然后从q出发,重复上述过程,直到找不到存在(3)的邻接顶点为止。
第三步:回退到尚有(4)顶点,从该顶点出发,重复第二、三步,直到所有被访问过的顶点的邻接点都已被访问为止。
因此,在这个算法中应设一个栈保存被(5)的顶点,以便回溯查找被访问过顶点的未被访问过的邻接点。
选项
答案
(1)邻接的顶点 (2)邻接的且未被访问的 (3)未访问过 (4)未被访问过的邻接点的 (5)访问过
解析
本题考查连通图的深度优先遍历算法的非递归过程。
在做题前,我们首先来了解一下图的遍历。和树的遍历类似,图的遍历也是从某个顶点出发,沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。
连通图的深度优先遍历可定义如下:首先访问出发点v,并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点w。若w未曾访问过,则以w为新的出发点继续进行深度优先遍历,直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。其关键是每次遍历都是往下直到最后再往回搜索,找到还未被访问过的邻接点的顶点,然后从该顶点出发,对它及下面的顶点进行深度优先遍历。下面来具体分析其算法。
第(1)空在第二步中,在访问起始顶点v后应该访问的结点,那么这个结点肯定是与起始顶点v邻接的顶点,因此此空答案为“邻接的顶点”。
第(2)空是在访问p顶点后应该访问的顶点,接下来应该也是访问与p顶点邻接的顶点,但这个时候p顶点的邻接顶点中有已经被访问过了的顶点,因此在访问前还需判断此顶点是否被访问过了,所以此空答案为“邻接的且未被访问的”。
第(3)空也在第二步中,结合前后的内容,可以知道此空是要判断是否还可以找到与当前访问顶点邻接而未被访问的顶点,根据上面分析,如果找不到,才往回搜索,因此此空答案为“未访问过”。
第(4)空是回退过程中要注意的地方,一般回退到还未被访问过的邻接点的顶点,接着访问这个未被访问过的邻接点。因此此空答案为“未被访问过的邻接点的”。
第(5)空是存放在栈中的内容,栈具有后进先出的特点,根据上面对深度优先遍历的分析可以知道,在回退的过程中需要用到被访问过的顶点,而且回退的过程是按遍历的顶点的顺序回退的,越后被访问的顶点越先被回退,因此此空答案是“访问过”。
转载请注明原文地址:https://kaotiyun.com/show/bnjZ777K
本试题收录于:
程序员下午应用技术考试题库软考初级分类
0
程序员下午应用技术考试
软考初级
相关试题推荐
为向相关人员以可视化方式展示数据分析结果,首先需要明确目标受众(即需要给哪些人看),并了解他们考虑的一些问题。这些问题一般不包括(69)________________。
在Excel的A1单元格中输入函数“=ROUND(3.1415,2)”,则A1单元格中显示的值为(57)。
数据录入工作有两个指标:录入速度和错误率。一般而言,数据录入员在录入大批数据时,录入速度会(65),错误率会(66)。65
在大型分布式信息系统中,为提高信息处理效率,减少网络拥堵,信息存储的原则是:数据应尽量(66)________________。
在Excel的A1单元格中输入函数“=IF(12,1,2)”,按回车键后,A1单元格中的值为()。
下列选项中,衡量数据校验人员业务水平的主要指标是(20)。
在PowerPoint中,下列关于自定义放映的叙述不正确的是(63)。
下图是某国多年来统计的出生人数和死亡人数曲线图。从图中看出,该国从________________年以后,死亡人数超过了出生人数,出现了人口危机。
程序员一般用(7)软件编写和修改程序。
ASP是(1)网页制作技术。A.动态B.静态从以下备选答案内为程序中(5)~(9)处空缺部分选择正确答案。(5)A.CreatObjectB.ConnectC.ExecuteSQLD.Open()(6)A.<body>
随机试题
婴儿出现(),如出血位置无法压迫,可让婴儿躺下,用拳头或手掌根部把出血的血管压向对侧的骨头方向。
常见的肛周脓肿是
治疗阴虚内热型内伤发热的首选方剂是
可能的诊断是若需要应采取的正确预防措施是
喜欢买报纸的人、常常________于报刊亭的人必然有着阅读的兴趣并养成了习惯,这样的行为不仅影响着个人的生活,也在________中影响着他人。将报刊亭打造成一个公共的阅读空间,就像现在随处可见的自助K歌房一样,这种________又便捷的阅读点,激发的
典型欠阻尼二阶系统超调量大于5%,则其阻尼ξ的范围为()。
从各国保险立法来看,关于投保人或被保险人的告知方式一般分为以下两种,即()。
某企业2011年年底“应付账款”科目月末贷方余额20000元,其中:“应付甲公司账款”明细科目贷方余额15000元,“应付乙公司账款”明细科目贷方余额5000元;“预付账款”科目月末贷方余额10000元,其中:“预付账款——甲工厂”明细科目贷方余额
Manystudentsfindtheexperienceofattendinguniversitylecturestobeareallyconfusingand【C1】______experience.Thelecture
Ithasbeenproventhatshortburstsofconcentrationrepeatedfrequentlyaremuchmore【B1】______thanonelongperiod.So,even
最新回复
(
0
)