软件设计师真题，数据结构专项练习（二十一）

快来打我* 2024-02-05 18:52 40阅读 0赞

### 图的遍历 ###

**邻接矩阵和邻接表是图（网）的两种基本存储结构，对于具有n个顶点、3条边的图，（59） 。（2009年下半年）**  
（59）  
A. 进行深度优先遍历运算所消耗的时间与采用哪一种存储结构无关  
B. 进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关  
C. 采用邻接表表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n\*e)  
D. 采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n^2)

> ![在这里插入图片描述][566b86b1edf04005bb037c4d9fa49994.png]

**以下关于图的遍历的叙述中，正确的是 （61） 。（2016年上半年）**  
（61）  
A. 图的遍历是从给定的源点出发对每一个顶点仅访问一次的过程  
B. 图的深度优先遍历方法不适用于无向图  
C. 使用队列对图进行广度优先遍历  
D. 图中有回路时则无法进行遍历

> ![在这里插入图片描述][4baa7f581d5e488ca92d7f58472baac2.png]

**以下关于无向连通图G的叙述中，不正确的是 （60） 。（2017年下半年）**  
（60）  
A. G中任意两个顶点之间均有边存在  
B. G中任意两个顶点之间存在路径  
C. 从G中任意顶点出发可遍历图中所有顶点  
D. G的临接矩阵是对称矩阵

> ![在这里插入图片描述][e66b42aa2e74440cb367bb33b107578a.png]

对有n个结点，e条边且采用数组表示法（即邻接矩阵存储）的无向图进行深度优先遍历，时间复杂度为 （61） 。（2018年上半年）  
![在这里插入图片描述][390657d6d0da4365834e2c81a3245167.png]

> ![在这里插入图片描述][8a585c0cf4c247b7bfe53ee7cdd75f44.png]

**图G的邻接矩阵如下图所示（顶点依次表示为v0、v1、v2、v3、v4、v5），G是 （60） 。对G进行广度优先遍历（从v0开始），可能的遍历序列为 （61） 。（2018年下半年）**  
![在这里插入图片描述][e28fb5350f3f424fa48c4a13d87f796c.png]

（60） A. 无向图 B. 有向图 C. 完全图 D. 强连通图  
（61） A. v0、v1、v2、v3、v4、v5 B. v0、v2、v4、v5、v1、v3  
C. v0、v1、v3、v5、v2、v4 D. v0、v2、v4、v3、v5、v1

> ![在这里插入图片描述][c18d5ed8a3c34f13b1c716a1b398cb78.png]

某有向图如下所示，从顶点v1出发对其进行深度优先遍历，可能能得到的遍历序列是 （60） ;从顶点v1出发对其进行广度优先遍历，可能得到的遍历序列是 （61） 。（2020年下半年）  
![在这里插入图片描述][6dd36e50fe174ad5ba33e321332854d2.png]  
![在这里插入图片描述][0c9acbc64124427fabc76bdb611c2f4e.png]

（60） A. ①②③ B. ①③④ C. ①②④ D. ②③④  
（61） A. ①② B. ①③ C. ②③ D. ③④

[566b86b1edf04005bb037c4d9fa49994.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/f63360d84a85498aa4180698e0565e97.png
[4baa7f581d5e488ca92d7f58472baac2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/a7963d88543e46ceb7b74e843a6b4494.png
[e66b42aa2e74440cb367bb33b107578a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/69099fbfa5544be89f40dc8bfa4a7ba0.png
[390657d6d0da4365834e2c81a3245167.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/e10a08806b614bbab15f5e554782f02e.png
[8a585c0cf4c247b7bfe53ee7cdd75f44.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/120d39620c1547069ca7ca831834323a.png
[e28fb5350f3f424fa48c4a13d87f796c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/b163bd0311f54b96b1322f9f21cf7f6d.png
[c18d5ed8a3c34f13b1c716a1b398cb78.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/6ea6c0e96ec74c29873e8c869a6bbd0a.png
[6dd36e50fe174ad5ba33e321332854d2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/fd44828fd85b477e8ee3e9234711f4e2.png
[0c9acbc64124427fabc76bdb611c2f4e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/abc6d7b65240410eb0d5e0080e665e90.png