第7章 图

第七章图

一、单选题

1.在一个无向图中，所有顶点的度数之和等于所有边的【】倍。

A.1/2

B.1

C.2

D.4

2.在一个有向图中，所有顶点的入度数之和等于所有顶点的出度之和的【】倍。

A.1/2

B.1

C.2

D.4

3.一个有n个顶点的无向图最多有【】条边。

A.n

B.n(n-1)

C.n(n-1)/2

D.2n

4.具有4个顶点的无向完全图有【】条边。

A.6

B.12

C.16

D.20

5.具有6个顶点的无向图至少应有【】条边才能确保是一个连通图。

A.5

B.6

C.7

D.8

6.一个有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是【】。

A.n

B. (n-1)2

C. (n-1)

D. n2

7.对某个无向图的邻接矩阵来说，【】。

A.第i行上的非0元素个数等于第i列上非0元素个数

B.矩阵中非0元素个数等于图中的边数

C.第i行、第i列上非0元素个数等于顶点vi的度数

D.矩阵中非全0行的行数等于图中的顶点数

8.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为【①】；所有邻接表中结点总数为【②】。

①A.n B.n+1 C.n-1 D.n2

②A.e/2 B.e C.2e D.n+e

二、判断题

【】1.n个顶点的无向图至多有n(n-1)条边。

【】2.有向图中，各顶点的入度之和等于各顶点的出度之和。

【】3.邻接矩阵只存储了边的信息，没有存储顶点的信息。

【】4.连通分量是无向图的极小连通子图。。

【】5.如果表示有向图的邻接矩阵是对称的，则该有向图一定是完全有向图。

【】6.如果表示图的邻接矩阵是对称的，则该图一定是无向图。

【】7.如果表示图的邻接矩阵不是对称的，则该图一定是有向图。

三、填空题

1.有n个顶点的无向图最多有条边。

2.具有n个顶点的强连通有向图至少有条边。

3.具有n个顶点的有向图最多有条边。

4.一个图的邻接矩阵表示法是唯一的，而邻接表表示法是不唯一的。

5.具有10个顶点的无向图，边的总数最多为。

6.在有n个顶点的有向图中，每个顶点的度最大可达。

7.已知一个有向图采用邻接矩阵表示，计算第i个顶点的入度的方法是。

8.已知一个有向图的邻接矩阵表示，删除所有从第i个结点出发的弧的方法是。

9.对于n的顶点的无向图，采用邻接矩阵表示，求图中边的方法是，判

断任意两个顶点是否有边相连的方法是，求任意顶点的度的方法是。

10.对于n个顶点的有向图，采用邻接矩阵表示，求图中边的方法是，判断任意两个顶点是否有边相连的方法是，求任意顶点的度的方法是。

12.若无向图有m条边，，则表示该无向图的邻接表中有个结点。

四、简答题

1.从占用的存储空间来看，对于稠密图和稀疏图，采用邻接矩阵和邻接表那个更好些？

2.用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？为什么？。