考研帮 > 数学 > 每日一练

4.3 图的遍历

4.3 图的遍历
  考试大纲涉及本节的知识点有:深度优先搜索和广度优先搜索。

一、选择题

  1.选择题题目部分
  ● 如图4-8所示,从顶点A出发,按深度优先搜索法进行遍历,可能得到的一种顶点序列是 (1)

1.jpg

  (1)A.ABECDF B.ACFEBD
  C.ABCDEF D.ABDFEC
  ● 如图4-8所示,已知某个深度优先搜索序列为A??F??,则可能的序列为 (2)
  ① ABDFEC ② ABCFDE ③ ACEFBD ④ ACEFDB ⑤ADCFEB ⑥ ADBFEC
  (2)A.①、②和⑥ B.①和④ C.①、③、④、⑤ D.②、③、④、⑤
  ● 无向图G=(V,E),其中:V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},对该图进行深度优先遍历,得到的顶点序列正确的是 (3)
  (3)A.a,b,e,c,d,f B.a,c,f,e,b,d
  C.a,e,b,c,f,d D.a,e,d,f,c,b
  ● 如图4-8所示,从顶点A出发,如按照广度优先搜索法进行遍历,可能得到的一种顶点序列为 (4)
  (4)A.ABECDF B.ACFEBD C.ABCDEF D.ABDFEC
  ● 图的深度优先搜索算法最需要以下哪种数据结构? (5)
  (5)A.栈 B.队列 C.数组 D.双向循环链表
  2.选择题练习答案与分析
  题号(1)
  答案 D
  习题分析:
  (1)观察选项A,首先访问A,然后访问B,此后必须回溯到A继续访问与A相邻且未被访问的顶点,即C或者D,选项中却访问了“E”,矛盾,故A选项错误。
  (2)观察选项B,首先访问A,然后访问C,此后只有E满足下一个访问的条件,但选项中却是“F”,矛盾,故B选项错误。
  (3)观察选项C,首先访问A,然后访问B,此后必须回溯到A继续访问与A相邻且未访问的顶点,即C或者D,选项中访问了C,此后只有E满足下一个访问的条件,但选项中却是“D”,矛盾,故C选项错误。
  (4)观察选项D,首先访问A,然后访问B,再回溯到A,访问D,此后只能访问F,访问F后只能访问E,访问E后只能访问C,即深度优先搜索序列为:ABDFEC,故选项D即为所求。
  题号(2)
  答案 B
  习题分析:
  从题中可以得出,第一个访问顶点是A,第4个访问顶点是F,有:
  (1)如果第2个访问D,那么第3个必须访问F,此时与F第4个访问矛盾。
  (2)如果第2个访问C,那么第3个必须访问E,第4个必须访问F,第5个必须访问D,第6个必须访问B,正好满足条件,因此ACEFDB是一个满足条件的序列。
  (3)如果第2个访问B:
  如果第3个访问D,那么第4个必须访问F,第5个必须访问E,第6个必须访问C,正好满足条件,因此ABDFEC是一个满足条件的序列。
  如果第3个访问C,那么第4个必须访问E,此时与第4个必须访问F冲突。
  题号(3)
  答案 D
  习题分析:
  对于无向图G=(V,E),其中:V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e), (c,f),(f,d),(e,d)},可以画出该无向图如图4-9所示。

4-9.jpg

  对该图进行深度遍历,从对供选答案可知,要从a进行深度遍历。根据深度遍历的算法可知,D为正确答案。
  题号(4)
  答案 C
  习题分析:
  首先访问顶点A,由于B、C、D与A相邻,则此后必须访问B、C和D,其中访问B、C、D的次序可以不同,但是这3个顶点的访问必须在访问其他顶点(即顶点E和F)之前。选项A中顶点E先于顶点C、D被访问,选项B中顶点F先于顶点B、D被访问,选项D中顶点F和E先于顶点C被访问,故选项A、B和D不是图4-8的广度优先搜索遍历序列。因此,正确答案为C。
  题号(5)
  答案 A
  习题分析:
  可以通过递归方法或使用栈完成图的深度优先搜索。
  3.训练自测表(如表4-5所示)
 

表4-5  选择题练习自测表

题    号

考  查  点

得    分

(1)~(3) 深度优先遍历  
(4) 广度优先遍历  
(5) 深度优先遍历使用的数据结构  

关于"最后阶段,真题的正确打开方式_备考经验_考研帮"15名研友在考研帮APP发表了观点

扫我下载考研帮

考研帮地方站更多

你可能会关心:

来考研帮提升效率

× 关闭