2. 计算机
  3. 如图8-3所示，在下面的5个序列中符合深度优先遍历的序列有(42)个。　　　　aebdfc，acfdeb，aedfcb，aefdcb，aefdbc　

如图8-3所示，在下面的5个序列中符合深度优先遍历的序列有(42)个。　　　　aebdfc，acfdeb，aedfcb，aefdcb，aefdbc　

admin2013-05-11  26
问题 如图8-3所示，在下面的5个序列中符合深度优先遍历的序列有(42)个。　　　　aebdfc，acfdeb，aedfcb，aefdcb，aefdbc　
选项 A、2个
B、3个
C、4个
D、5个
答案C
解析 图的深度优先搜索遍历过程是：首先一个出发顶点v，并访问之，接着选择一个与v相邻接并且未被访问过的顶点w访问之，再从w开始进行深度优先搜索遍历。每当到达一个其所有相邻接的顶点都已被访问过的顶点时，就从最近所访问的顶点开始依次回退，直至退回某个顶点，该顶点尚有未曾访问过的邻接顶点，再从该邻接顶点开始继续进行深度优先搜索遍历。上述过程在两种可能情况下终止：所有顶点已都被访问，或从任一个已被访问过的顶点出发，再也无法到达未曾访问过的顶点。对于无向图，如果图是连通的，那么按深度优先搜索遍历时，可遍历全部顶点，得到全部顶点的一个遍历序列。从a出发，aebdfc，acfdeb，aedfcb，aefdcb都是符合深度优先遍历的序列。但aefdbc不是；因为走过aefd之后，与d相邻接的顶点都已被访问过，所以从最近访问的顶点开始依次回退，当回退到f时与　f相邻接的结点只有c未被访问过就访问c，然后又回退至e再访问b，因此只能是aefdcb，而不能是aefdbc，所以应选4个。
转载请注明原文地址:https://www.kaotiyun.com/show/vQRZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

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