数据结构第三单元练习题答案

一、选择题

1.设无向图的顶点个数为n，则该图最多有（ ）条边。 A.n-1 B.n(n-1)/2 C.n(n+1)/2 D.0

2.在一个无向图中，所有顶点的度数之和等于所有边数（ B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ C ）倍。 A.1/2 B.2 C.1 D.4

3.若一个具有n个顶点，k条边的无向图是一个森林（n>k），则该森林中必有（）棵树。 A.k B.n C. n-k D.（D）1 4.下列哪一种图的邻接矩阵是对称矩阵？（ ） A.有向图B.无向图 C.AOV网D.AOE网

5.一个有向图邻接表和逆邻接表中结点的个数( A )。

A.一样多B.邻接表中结点比逆邻接表中结点多C.逆邻接表中结点比邻接表结点多D.不确定 6.在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的 （ ） A.先根遍历B.中根遍历C.后根遍历D.按层次遍历 7.下列说法不正确的是（ ）。

A.图的遍历是从给定的源点出发每一个顶点仅被访问一次 B.遍历的基本算法有两种：深度遍历和广度遍历 C.图的深度遍历不适用于有向图 D.图的深度遍历是一个递归过程

8.在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。

23

A.O(n) B.O(n+e) C.O(n) D.O(n) 9.AOV网是一种（ ）。

A.有向图 B.无向图 C.无向无环图 D.有向无环图 10.一个有向无环图的拓扑排序序列（ ）是唯一的。 A.一定 B.不一定

11.有拓扑排序的图一定是（ ）。

A.有环图B.无向图C.强连通图 D.有向无环图

12.在用邻接表表示图时，拓扑排序算法时间复杂度为( )。 A.O(n) B.O(n＋e) C.O(n*n) D.O(n*n*n)

13.下列关于AOE网的叙述中，不正确的是（ ）。 A.关键活动不按期完成就会影响整个工程的完成时间

B.任何一个关键活动提前完成，那么整个工程将会提前完成 C.所有的关键活动提前完成，那么整个工程将会提前完成 D.某些关键活动提前完成，那么整个工程将会提前完成 14.最短路径的生成算法可用（ ）。 A.普里姆算法B.克鲁斯卡尔算法 C.迪杰斯特拉算法 D.哈夫曼算法

15.若一个具有n个顶点，k条边的无向图是一个森林（n>k），则该森林中必有（ ）棵树。 A. k B.n C.n-k D.1 二、判断题

1.在n个结点的无向图中，若边数大于n-1,则该图必是连通图。× 2.强连通分量是无向图的极大强连通子图。×

1 用心用情 服务社会 自信考试 诚信做人 3.用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。×

4.有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半。√

5.有向图的邻接矩阵是对称的。×

6.邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。× 7.任何无向图都存在生成树。×

8.带权无向图的最小生成树必是唯一的。× 9.拓扑排序的有向图中，最多存在一条环路。×

10．任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。×

11.若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。√ 12.AOV网的含义是以边表示活动的网。×

13.关键路径是AOE网中从源点到终点的最长路径√

14.在表示某工程的AOE网中，加速其关键路径上的任意关键活动均可缩短整个工程的完成时间。×

15.在AOE图中，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。√ 三、填空题

1.在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的__度 ____；对于有向图来说等于该顶点的__出度____。 2.已知一无向图G=（V，E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是__深度优先____遍历方法。

3.利用Kruskal算法生成最小代价生成树其时间复杂度为__ O(eloge)____。

2

4.求最短路径的Dijkstra算法的时间复杂度为_____ O(n）_。 四、应用题 1．给出图G

（1）画出G的邻接表表示图；

（2）给出从顶点①开始,对图G用深度优先搜索法进行遍历时的顶点序列； （3）给出从顶点①开始,对图G用广度优先搜索法进行遍历时的顶点序列。

（4）根据你画出的邻接表，以顶点①为根，画出G的深度优先生成树和广度优先生成树。 1 3 4 2

5 6 7

(1)略 8 9 10 （2）深度优先遍历序列 1，2，5，3，4，7，6，8，9，10 （3）广度优先遍历序列

1，2，3，4，5，6，7，8，9，10 （4）（假设表结点的编号按由小到大的顺序排列）

2 用心用情 服务社会 自信考试 诚信做人

1 1 2 2 4 3 6 5 8 7 9 3 6 5 8 4 9 7 10 10 深度优先生成树 广度优先生成树

2.已知一个图的顶点集V为： V={1,2,3,4,5,6,7};共有10条边。该图用如下边集数组存储：

起点 1 2 2 5 5 2 2 6 1 3 终点 权

6 1 4 1 5 2 4 2 7 2 6 3 7 3 7 4 7 5 5 7 试用克鲁斯卡尔算法依次求出该图的最小生成树中所得到的各条边及权值。 用克鲁斯卡尔算法得到的最小生成树为：

(1,6)1, (2,4)1, (2,5)2, (5,7)2, (2,6)3, (3,5)7

3．试利用Dijkstra算法求下图中从顶点a到其他个顶点间的最短路径。

b

15

28

ace

1249

510 dfg 2顶点 I=0 b c d e f g S 15 (a,b) 2 (a,c) 12 (a,d) ∞ ∞ ∞ {c} I=1 15 (a,b) 12 (a,d) 10 (a,c,e) 6 (a,c,f) ∞ {c,f} I=2 15 (a,b) I=3 15 (a,b) I=4 15 (a,b) I=5 15 (a,b) {c,f,e,d,g,b} 11 11 (a,c,f,d) (a,c,f,d) 10 (a,c,e) 16 16 13 (a,c,f,g) (a,c,f,g) (a,c,f,d,g) {c,f,e} {c,f,e,d} {c,f,e,d,g}

4．对图示的AOE网络，计算各活动弧的e(ai)和l(ai)的值，各事件（顶点）的ve（Vj）和vl (Vj)的值，列出各条关键路径。

3 用心用情 服务社会 自信考试 诚信做人 A1B6534C72E821 11106F9 1716H12WG13D

是 是 是 是 是 事件 Ve α A B C D F E H G W 0 1 6 3 4 13 24 22 39 52 Vl 0 29 24 3 7 13 31 22 39 52 活动 α→A α→B α→C α→D A→E B→E B→W C→G C→F D→F F→E F→W F→H E→G H→G H→W G→W e 0 0 0 0 1 6 6 3 3 4 13 13 13 24 22 22 39 l 21 18 0 3 29 24 31 34 3 7 20 36 13 31 22 40 39 l- e 关键活动？ 21 18 0 3 28 18 25 31 0 3 7 23 0 7 0 19 0 路径长度为：3+10+9+17+13=52 关键路径如下：

5.设有边集合：〈0，1〉，〈1，2〉，〈4，1〉，〈4，5〉，〈5，3〉，〈2，3〉求此图的所有可能的拓扑序列；

041253、041523、045123、401253、401523、405123、450123

4 用心用情 服务社会