漫话数据结构答案2023

第六章测试

1.设有无向图G=（V，E）和G’=（V’,E’）,如G’为G的生成树，则下面不正确的说法是（ ）
A:G’为G的子图
B:G’为G的极小连通子图且V’=V
C:G’是G的无环子图
D:G’为G的连通分量

答案:D
2.任何一个带权的无向连通图的最小生成树（ ）
A:可能不存在
B:有一棵或多棵
C:只有一棵
D:一定有多棵
3.以下说法正确的是（ ）
A:对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。
B:在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧＜a,b＞。
C:连通分量是无向图中的极小连通子图。
D:强连通分量是有向图中的极大强连通子图。
4.

图中有关路径的定义是（ ）。

A:由不同边所形成的序列                        
B:由不同的相邻顶点所形成的序列
C:由不同顶点所形成的序列
D:由顶点和相邻顶点序偶构成的边所形成的序列      
5.设无向图的顶点个数为n，则该图最多有（ ）条边。
A:0
B:n(n+1)/2
C:n(n-1)/2
D:n-1