首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列算法说明和算法,将应填入(n)处的语句写在对应栏内。 1. 【说明】 实现连通图G的深度优先遍历(从顶点v出发)的非递归过程。 【算法】 第一步:首先访问连通图G的指定起始顶点v; 第二步:从V出发,访问一个与v(1)
阅读下列算法说明和算法,将应填入(n)处的语句写在对应栏内。 1. 【说明】 实现连通图G的深度优先遍历(从顶点v出发)的非递归过程。 【算法】 第一步:首先访问连通图G的指定起始顶点v; 第二步:从V出发,访问一个与v(1)
admin
2012-12-10
39
问题
阅读下列算法说明和算法,将应填入(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://jikaoti.com/ti/rbW7FFFM
本试题收录于:
程序员下午应用技术考试题库软考初级分类
0
程序员下午应用技术考试
软考初级
相关试题推荐
假设在Access中已经建立了“学生”表,表中包括“学号”、“姓名”、“性别”和“班级”等字段,如果要统计出每个班级的人数,那么在查询设计视图的“班级”的“总计”行和“学号”的“总计”行中应分别选择(65)。
西部某省考试机构工作人员统计了去年下半年三个地区四种资格的报考人数,将统计表抄录如下(其中有一个数据抄错了): 信息处理技术员小王很快就找出了错误的数据,并进行了纠正。错误的数据是(32),该数据应纠正为(33)。33.
在Word2007中,若用户需要将一篇文章中的字符串“Internet”全部替换为字符串“因特网”,则可以在编辑菜单中选择()命令。
以下关于计算机网络协议的叙述中,不正确的是(58)________________。
在Word中打开英文文档或者在文档中输入英文信息时,系统会自动对拼写和语法进行检查,如果出现红色波形下划线则表示存在(50)。
Windows XP的许多应用程序的“文件”菜单中,都有“保存”和“另存为”两个命令。以下对这两个命令的叙述,正确的是(36)。
在Word2003中,对当前正在编辑的文档内容进行多次剪切操作后关闭该文档,则剪贴板中的内容为______。
在Windows系统中,控制面板的功能不包括______。
综合布线系统由6个子系统组成,将图1-1中(1)~(6)处空缺子系统的名称填写在答题纸对应的解答栏内。制作交叉双绞线(一端按EIA/TIA568A线序,另一端按EIA/TIA568B线序)时,其中一端的线序如图1-2(a)所示,另一端线序如图1—2
随机试题
A、Heisproficientindriving.B、Heiskindandlearned.C、Heknowsashortcuttothemuseum.D、Heisaninexperiencedtaxidriv
患儿女性,3岁,因“肺炎,脓毒性休克”收住儿科重症监护室(PICU)。入院第3天,休克已经纠正,呼吸机治疗,腹胀,无肠鸣音,胃管内引流出咖啡样胃液。此时静脉营养成分的选择是
生物转化中甲基可来自生物转化中乙酰基可来自
男性,10岁。突发剑突下阵发性剧烈绞痛3小时,发作时辗转不安,呻吟痛苦,伴恶心呕吐,发作过后如常人。检查无发热无黄疸,腹平软无明显压痛,白细胞计数正常。应诊断为何病
利用中药中各成分沸点的差别进行提取分离的方法是
河流充分混合段是指污染物浓度在断面上均匀分布的河流。当()时,可以认为达到均匀分布。
甲公司严重资不抵债。因不能清偿到期债务向法院申请破产。下列财产属于债务人财产的是()。
个体在解决问题过程中,思维沿着许多不同的方向扩展,使观念发散到各个有关方面,最终产生多种可能的答案的认知方式称为()。
配置路由器时,PC机的串行口与路由器的(59)相连,路由器与PC机串行口通信的默认数据速率为(60)。(59)
AsmanyasoneinfourU.S.workersmaybechronicallyangryonthejob,withangryemployeesalsomorelikelytobebored,hav
最新回复
(
0
)