首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列算法说明和算法,将应填入(n)处的语句写在对应栏内。 1. 【说明】 实现连通图G的深度优先遍历(从顶点v出发)的非递归过程。 【算法】 第一步:首先访问连通图G的指定起始顶点v; 第二步:从V出发,访问一个与v(1)
阅读下列算法说明和算法,将应填入(n)处的语句写在对应栏内。 1. 【说明】 实现连通图G的深度优先遍历(从顶点v出发)的非递归过程。 【算法】 第一步:首先访问连通图G的指定起始顶点v; 第二步:从V出发,访问一个与v(1)
admin
2012-12-10
31
问题
阅读下列算法说明和算法,将应填入(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
程序员下午应用技术考试
软考初级
相关试题推荐
在Word2007中,为使内容更加醒目,文章更具有条理性,可在若干段落前面添加__________。
在Excel2007中,在单元格A1中输入函数“=LEN(”信息处理技术员”)”,按回车键后,则A1单元格中的值为__________。
数据收集的基本原则中不包括(7)。
在Word2007中,若用户需要将一篇文章中的字符串“Internet”全部替换为字符串“因特网”,则可以在编辑菜单中选择()命令。
某种考试共有75个试题,每对一题得2分,每错一题扣1分。某考生最后的分数是54分,则该考生共做对______题。
某PowerPo血文档共有10张幻灯片,先选中第6张幻灯片,再改变背景设置,单击“全部应用”命令后,则第________张幻灯片的背景被改变。
计算机病毒是一段程序,一般隐藏在______中。
甲和乙用如下图的两个转盘做游戏,游戏规则如下:分别旋转两个转盘,当两个转盘所转到的数字之积为奇数时,甲得2分;当所转到的数字之积为偶数时,乙得1分,则这游戏规则______。
由多台计算机组成的一个系统,这些计算机之间可以通过通信来交换信息,互相之间无主次之分,它们共享系统资源,程序由系统中的全部或部分计算机协同执行,执行过程对用户透明。管理上述计算机系统的操作系统是_________。
ASP是(1)网页制作技术。A.动态B.静态从以下备选答案内为程序中(5)~(9)处空缺部分选择正确答案。(5)A.CreatObjectB.ConnectC.ExecuteSQLD.Open()(6)A.<body>
随机试题
A.足少阳胆经B.手少阳三焦经C.手太阳小肠经D.足太阳膀胱经天宗穴所属的经脉是
下列关于心肺脑复苏的叙述,正确的是()
彩色多普勒技术可以与下列哪种技术并用
权力制约是依法治国的关键环节。下列哪些选项体现了我国宪法规定的权力制约原则?(2011年试卷一第59题)
水在2.03×105Pa压强下沸腾,沸点为120℃,在这压强下1.0kg的水变成水蒸气,其体积从10-3m3变成82.4×10-2m3,则此过程水蒸气对外做功为()。
设备质量的形成过程分为( )。
狭义的基金监管一般专指()依法对基金市场、基金市场主体及其活动的监督和管理。
假定无风险收益率为5%,投资人最优风险资产组合的期望收益率为15%,标准差为25%,试求:(复旦大学2017年真题)假设投资人需要构造标准差为10%的投资组合,则投资最优风险资产组合的比例是多少?构造的投资组合期望收益率是多少?
BobWon’tstoptrying______hegetsWhatheWants.
A、Theyaremuchdifficulttoconnectwith.B、Theyarewillingtoshowyouaround.C、Theyhelprelievereversecultureshock.D、T
最新回复
(
0
)