单元同步训练及答案.pdfVIP

单元5同步训练

一、单项选择题

1．在一个图中,所有顶点的度数之和等于所有边数的（）倍。

A．1/2B．1C．2D．4

2．在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的

（）倍。

A．1/2B．1C．2D．4

3．一个有n个顶点的无向图最多有（）条边。

A．nB．n(n-1)C．n(n-1)/2D．2n

4．具有4个顶点的无向完全图有（）条边。

A．6B．12C．16D．20

5．具有6个顶点的无向图至少应有（）条边才能确保是通图。

A．5B．6C．7D．8

6．在一个具有n个顶点的无向图中,要连通全部顶点至少需要（）条

边。

A．nB．n+1C．n-1D．n/2

7．对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵含元

素的个数是（）。

22

A．nB．(n-1)C．n-1D．n

8．含n个顶点的连通图中的任何一条简单路径，其长度不可能超过

（）。

A．1B．n/2C．n-1D．n

9．对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向

量的大小为（）。

A．nB．n+1C．n-1D．n+e

10．已知无向图如图5-19所示,若从顶点a出发按深度有哪些信誉好的足球投注网站法进行遍历,则

可能得到的一种顶点序列为（）。

A．a,b,e,c,d,fB．a,c,f,e,b,d

C．a,e,b,c,f,dD．a,e,d,f,c,b

a

1324^

c

2^

be

345^

4^

df524^

图5-19选择题第10题的图图5-20选择题第