第7章 图单元测试(答案).pdfVIP

百学须先立志。——朱熹

第七章图

____

一、选择题

1．设无向简单图的顶点个数为n，则该图最多有（B）条边。

A．n-1B．n(n-1)/2C．n(n+1)/2D．n2

2．一个n个顶点的连通无向图，其边的个数至少为（A）。

A．n-1B．nC．n+1D．nlogn；

3．在一个无向图中，所有顶点的度数之和等于所有边数（B）倍，在一个有向图中，所有

顶点的入度之和等于所有顶点出度之和的（C）倍。

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

4．下列哪一种图的邻接矩阵是对称矩阵？（）

A．有向图B．无向图C．AOV网D．AOE网

5．下列有关图的遍历的说法中，不正确的是（）。

A．用邻接表存储的图的深度优先有哪些信誉好的足球投注网站的时间复杂度为O(n＋e)

B．图的广度优先有哪些信誉好的足球投注网站中邻接点的寻找具有“先进先出”的特征，需要采用队列结构来

实现

C．非连通图不能用深度优先有哪些信誉好的足球投注网站法

D．图的遍历要求每一顶点访问且仅被防问一次

6.求解最短路径的Floyd算法的时间复杂度为()。

23

A．O（n）B.O（n+c）C.O（n）D.O（n）

7.在用邻接表表示图时，拓扑排序算法时间复杂度为()。

2

A.O(n)B.O(n＋e)C.O（n）

3

D.O（n）vv

173

8.右图所示的无向网的最小生成树的权为()。

v12

0v

A．11B．92535

C．14D．12

46

9.关键路径是AOE网中（）。

v1v

A．从源点到汇点的最长路径24

B．从源点到汇点的最短路径

C．最长回路

D．最短回路

10．下列关于AOE网的叙述中，不正确的是（）。

A．关键活动不按期完成就会影响整个工程的完成时间

B．任何一个关键活动提前完成，那