数据结构题目 课时8

题目

1、n（n> 0）个顶点的无向图最多有_______条边，最少有_______条边。

2、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_______倍。

3、下列关于无向连通图特性的叙述中，正确的是（ ）。
（1）所有顶点的度数之和为偶数
（2）边数小于顶点个数减 1
（3）至多有一个顶点的度数为 1
A. （1）
B. （2）
C. （1）（2）
D. （1）（3）

4、下面关于图的存储结构中正确的是（ ）。
A. 用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
B. 用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关
C. 用邻接矩阵法存储图，占用的存储空间大小与图中边数和结点个数都有关
D. 用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关

5、邻接矩阵适用于稀疏图的存储，邻接表适用于稠密图的存储。（ ）

6、如下图所示一个无向图，试分别给出它的邻接矩阵和邻接表。

7、如图所示是一个无向连通网的邻接矩阵，试画出该网。

8、对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的各个顶点。（ ）

9、已知有向图的邻接表存储结构如下图所示，则按深度优先遍历算法从顶点 v₁出发，所得到的顶点序列为（  ）。                                                                                                                                A. v₁,v₅,v₃,v₄,v₂
B. v₁,v₃,v₂,v₅,v₄
C. v₁,v₃,v₄,v₅,v₂
D. v₁,v₃,v₂,v₄,v₅

10、已知图的邻接矩阵如下：试给出邻接表结构，并给出从顶点 v₁出发进行深度优先和广度优先的搜索结果。

答案

1、n（n-1）/2；n- 1

2、1

3、A

4、B
用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关
用邻接矩阵法存储图，占用的存储空间大小只与结点个数有关，而与图中边数无关

5、错误
邻接表适用于稀疏图的存储，邻接矩阵适用于稠密图的存储

6、

7、

8、错误
该图必须是连通图

9、C

10、

深度优先搜索序列：14326857
广度优先搜索序列：14738625