内容发布更新时间 : 2024/4/19 15:23:48星期一 下面是文章的全部内容请认真阅读。

单项选择题

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

A. 1/2 B. 1 C. 2 D. 4 2．任何一个无向连通图的最小生成树 。

A.只有一棵

B.有一棵或多棵

C.一定有多棵

D.可能不存在

3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。

A. 1/2 B. 1 C. 2 D. 4 4．一个有n个顶点的无向图最多有____条边。

A. n B. n(n-1) C. n(n-1)/2 D. 2n 5．具有4个顶点的无向完全图有____条边。

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

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

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

7．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。

A. n B. n+1 C. n-1 D. n/2

8．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。

A. n B. (n-1) C. n-1 D. n

9．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。

① A. n B. n+1 C. n-1 D. n+e ② A. e/2 B. e D. n+e

10．已知一个图如图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到

的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列 为__②__。

① A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b ② A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b

2

2

a b e c

图 一个无向图

11．已知一有向图的邻接表存储结构如图所示。

1

2 ^ 3 4 ^ 4 ^ 2 5 一个有向图的邻接表存储结构图 4 5 3 2 ^ ^ ⑴ 根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。

A. v1,v2,v3,v5,v4 B. v1,v2,v3,v4,v5 C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v2

⑵ 根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。

A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5 C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v2

12．采用邻接表存储的图的深度优先遍历算法类似于二叉树的____。

A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历 13．采用邻接表存储的图的宽度优先遍历算法类似于二叉树的____。

A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历

14．判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用____。

A. 求关键路径的方法 B. 求最短路径的Dijkstra方法 C. 宽度优先遍历算法 D. 深度优先遍历算法 15．关键路径是事件结点网络中 。

A.从源点到汇点的最长路径 B.从源点到汇点的最短路径 C.最长的回路 D.最短的回路 16．下面不正确的说法是 。

（1）在AOE网中，减小一个关键活动上的权值后，整个工期也就相应减小； （2）AOE网工程工期为关键活动上的权之和；

（3）在关键路径上的活动都是关键活动，而关键活动也必在关键路径上。

A.（1）

B.（2）

C.（3）

D.（1）、（2）

17．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印出相应的顶点，则输出的顶点序列是 。

A.逆拓朴有序的

B.拓朴有序的

C.无序的

18．在图所示的拓朴排列的结果序列为 。

19．一个有n个顶点的无向连通图，它所包含的连通分量个数为 。

B.1

图有向图

B.516234

+1

20．对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中的结点数为 。

2

+k2

21．对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为 。

2

+k2

填空题（将正确的答案填在相应饿空中）

1．n个顶点的连通图至少____条边。

2．在无权图G的邻接矩阵A中，若(vi,vj)或＜vi,vj＞属于图G的边集合，则对应元素A[i][j]等于____，否则等于____。

3．在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i ]等于____。

4．已知图G的邻接表如图所示，其从顶点v1出发的深度有限搜索序列为____，其从顶点v1出发的宽度优先搜索序列为____。

v1 v2 v3 v4 ^ v2 v3 v6 v5 v5 v4