首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列算法说明和算法,将应填入(n)处的语句写在对应栏内。 1. 【说明】 实现连通图G的深度优先遍历(从顶点v出发)的非递归过程。 【算法】 第一步:首先访问连通图G的指定起始顶点v; 第二步:从V出发,访问一个与v(1)
阅读下列算法说明和算法,将应填入(n)处的语句写在对应栏内。 1. 【说明】 实现连通图G的深度优先遍历(从顶点v出发)的非递归过程。 【算法】 第一步:首先访问连通图G的指定起始顶点v; 第二步:从V出发,访问一个与v(1)
admin
2012-12-10
46
问题
阅读下列算法说明和算法,将应填入(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
程序员下午应用技术考试
软考初级
相关试题推荐
在浏览网页时,当鼠标指针移至某些文字或某些图片时,会出现手形状,通常是由于网页在这个地方做了(17)。
以下关于计算机网络协议的叙述中,不正确的是(58)________________。
在Windows XP中,文件名中不允许出现的字符是(32)。
四位二进制数(从0000到1111)中,不含连续三位相同数字的数共有(4)个。
操作系统的功能不包括______。
某学校有多个班,每个班有多名学生但只能有一个班长,那么班长与学生这两个实体之间的关系是(57)。
甲和乙用如下图的两个转盘做游戏,游戏规则如下:分别旋转两个转盘,当两个转盘所转到的数字之积为奇数时,甲得2分;当所转到的数字之积为偶数时,乙得1分,则这游戏规则______。
在选择多媒体数据压缩算法时需要综合考虑(24)。
综合布线系统由6个子系统组成,将图1-1中(1)~(6)处空缺子系统的名称填写在答题纸对应的解答栏内。为满足公司要求,通常选用什么类型的信息插座?
Web客户端与服务器共同遵守(1)协议,默认端口号是(2),协作的过程是:Web客户端在浏览器的地址栏输入(3),连接到相应的WWW服务器上并获得指定的Web文档,然后断开与WWW服务器的连接,最后,Web文档以(4)格式在客户端解释。“如果服务器只有
随机试题
下列治疗军团菌病的首选药物是
下列哪些措施对预防饱胃病人发生反流误吸是无益的?()
近代宪法最早产生于西方资本主义国家。请问下列选项中的哪一项被认为是近代宪法起源地?()
背景材料: 某一高速公路标段长10km,路段包含一座大桥和一个互通式立交,涵洞通道18个,路基土方均为路堤填筑。承包人进场后,项目部明确了各部门、各施工队和班组项目成本考核内容,制订了降低施工项目成本的方法和途径。 问题:请说明项目部制定的降低
在下列控制经济中的货币总量的各个手段中,中央银行不能完全自主操作的是()。
罗杰斯认为,个体在其成长过程中,不断地与现实发生着互动,个体不断地对互动中的经验进行评价,这种评价依赖于()。
教育学生的感情基础是()。
Americanssufferfromanoverdoseofwork.【C1】______whotheyareorwhattheydo,theyspend【C2】______timeatworkthanatanyt
为了避免流程图在描述程序逻辑时的灵活性,提出了用方框图来代替传统的程序流程图,通常也把这种图称为_________。
若有下列定义(设int类型变量占2个字节):inti=8;则下列语句:printf("i=%08d",i);输出的结果是()。
最新回复
(
0
)