2. 计算机
  3. 阅读下列算法说明和算法，将应填入(n)处的语句写在对应栏内。 1. 【说明】 实现连通图G的深度优先遍历(从顶点v出发)的非递归过程。 【算法】 第一步：首先访问连通图G的指定起始顶点v； 第二步：从V出发，访问一个与v(1)

阅读下列算法说明和算法，将应填入(n)处的语句写在对应栏内。 1. 【说明】 实现连通图G的深度优先遍历(从顶点v出发)的非递归过程。 【算法】 第一步：首先访问连通图G的指定起始顶点v； 第二步：从V出发，访问一个与v(1)

admin2012-12-10  82
问题 阅读下列算法说明和算法，将应填入(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://www.kaotiyun.com/show/bnjZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

相关试题推荐
随机试题
最新回复(0)