免费智能真题库 > 历年试卷 > 软件设计师 > 2020年下半年 软件设计师 上午试卷 综合知识
  第60题      
  知识点:   深度优先遍历   广度优先遍历
  章/节:   计算机软件知识       

 
某有向图如下所示,从顶点v1出发对其进行深度优先遍历,可能能得到的遍历序列是(60); 从顶点v1出发对其进行广度优先遍历,可能得到的遍历序列是(61)。

①v1 v2 v3 v4 v5
②v1 v3 v4 v5 v2
③v1 v3 v2 v4 v5
④v1 v2 v4 v5 v3

 
 
  A.  ①②③
 
  B.  ①③④
 
  C.  ①②④
 
  D.  ②③④
 
 
 

 
  第1题    2018年上半年  
   49%
对有n个结点、e条边且采用数组表示法(即邻接矩阵存储)的无向图进行深度优先遍历,时间复杂度为(1)。
  第61题    2020年下半年  
   45%
某有向图如下所示,从顶点v1出发对其进行深度优先遍历,可能能得到的遍历序列是(60); 从顶点v1出发对其进行广度优先遍历,可能..
  第61题    2018年下半年  
   43%
图G的邻接矩阵如下图所示(顶点依次表示为v0、v1、v2、v3、v4、v5),G是(60)。对G进行广度优先遍历(从v0开始),可能的遍历序..
   知识点讲解    
   · 深度优先遍历    · 广度优先遍历
 
       深度优先遍历
        从图G中任一个顶点v出发,深度优先遍历(DFS)的算法步骤如下。
        (1)设立搜索指针p,使p指向顶点v
        (2)访问p顶点,并使p指向与p顶点相邻接的且尚未被访问过的顶点。
        (3)若p不空,则重复步骤(2);否则执行步骤(4)。
        (4)沿着刚才访问的次序、方向回溯到一个尚有邻接顶点且未被访问过的顶点,并使p指向这个未被访问的邻接顶点,然后重复步骤(2),直至所有的顶点均被访问为止。
        这个算法的特点是尽可能先对纵深方向搜索,因此可以很容易得到其遍历的递归算法。
        深度优先遍历图的过程实质上是对某个顶点查找其邻接节点的过程,其耗费的时间取决于所采用的存储结构。当图用邻接矩阵表示时,查找所有顶点的邻接点所需时间为O(n2)。若以邻接表作为图的存储结构,则需要O(e)的时间复杂度查找所有顶点的邻接点。因此,当以邻接表作为存储结构时,深度优先搜索遍历图的时间复杂度为O(n+e)。
 
       广度优先遍历
        图的广度优先遍历的基本思想是:给定图G=(V,E),从图中某个源点v出发,在访问了顶点v之后,接着就尽可能先在横向搜索v的所有邻接点。在依次访问v的各个未被访问过的邻接点w1,w2,…,wk之后,分别从这些邻接点出发依次访问与w1,w2, …,wk邻接的所有未曾访问过的顶点。依此类推,直至图中所有和源点v有路径相通的顶点都已访问过为止,此时从v开始的搜索过程结束。若G是连通图,则遍历完成;否则,在图G中另选一个尚未访问的顶点作为新源点继续上述的搜索过程,直至图G中所有顶点均已被访问为止。采用广度优先搜索法遍历图的方法称为图的广度优先遍历。
        为确保先访问的顶点其邻接点亦先被访问,在搜索过程中可使用队列来保存已访问过的顶点。当访问v和u时,这两个顶点相继入队,此后,当v和u相继出队时,分别从v和u出发搜索其邻接点v1,v2,…,vs和u1,u2, …,ut,对其中未访者进行访问并将其入队。这种方法是将每个已访问的顶点入队,保证了每个顶点至多只有一次入队。
   题号导航      2020年下半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
第60题    在手机中做本题