第七章的练习题

一、选择题

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

A ．n-1

B ．n(n-1)/2

C ． n(n+1)/2

D ．0

E ．n 2

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

A ．n-1

B ．n

C ．n+1

D ．nlogn ； 3．要连通具有n 个顶点的有向图，至少需要（ ）条边。

A ．n-l

B ．n

C ．n+l

D ．2n 4．n 个结点的完全有向图含有边的数目（ ）。

A ．n*n Ｂ．n （n ＋１） C ．n ／2 D ．n*（n －l ）

5．一个有n 个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。

A ．0

B ．1

C ．n-1

D ．n

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

A ．1/2

B ．2

C ．1

D ．4

7．一个图中包含K 个连通分量，若按深度优先搜索方法访问所有结点，则必须调用（ ）次深度优先搜索遍历算法。

A ．1

B ．K-1

C ．K DK+1． 8．下列哪一种图的邻接矩阵是对称矩阵？（ ）

A ．有向图

B ．无向图

C ．AOV 网

D ．AO

E 网

9． 从邻接阵矩

?????

?????=01

0101

010A 可以看出，该图共有（①）个顶点；如果是有向图该图共有（②） 条弧；

如果是无向图，则共有（③）条边。

①．A ．9 B ．3 C ．6 D ．1 E ．以上答案均不正确 ②．A ．5 B ．4 C ．3 D ．2 E ．以上答案均不正确 ③．A ．5 B ．4 C ．3 D ．2 E ．以上答案均不正确 10．对某个无向图的邻接矩阵来讲，（ ）。

A ．第i 行上的非零元素个数和第i 列的非零元素的个数一定相等

B ．矩阵中的非零元素个数等于图中的边数

C ．第i 行上，第i 列上非零元素总数等于顶点vi 的度数

D ．矩阵中非全零行的行数等于图中的顶点数

11．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。

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

B ．a,c,f,e,b,d

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

D ．a,e,d,f,c,b 12. 设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（ ）

a e

b d f

c a c f

d

e b a e d

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

5个 B ．4个 C ．3个 D ．2个

第12题图第13题图

13.下图中给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍历得到的序列是( ① )，而进行广度优先遍历得到的顶点序列是（②）。

①．A．1354267 B．1347652 C．1534276 D．1247653 E．以上答案均不正确

②．A．1534267 B．1726453 C．l354276 D．1247653 E．以上答案均不正确14．下面哪一方法可以判断出一个有向图是否有环（回路）：

A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径

15.已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，

E={,,,,,,,,},G的拓扑序列是（）。

A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7

C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7

16．一个有向无环图的拓扑排序序列（）是唯一的。

A．一定 B．不一定

17. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）。

A．G中有弧 B．G中有一条从Vi到Vj的路径

C．G中没有弧 D．G中有一条从Vj到Vi的路径

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

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

B．任何一个关键活动提前完成，那么整个工程将会提前完成

C．所有的关键活动提前完成，那么整个工程将会提前完成

D．某些关键活动提前完成，那么整个工程将会提前完成

二、填空题

1. 设无向图 G 有n 个顶点和e 条边，每个顶点Vi 的度为di（1<=i<=n〉，则e=______

4．G是一个非连通无向图，共有28条边，则该图至少有______个顶点。

5. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要______条弧。

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

7．N个顶点的连通图的生成树含有______条边。

8．有N个顶点的有向图，至少需要量______条弧才能保证是连通的。

9．右图中的强连通分量的个数为______个。

10．N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_______个非零元素。

11．在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的______；对于有向图来说等于该顶点的______。

12. 在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是______。

13. 已知一无向图G=（V，E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是______遍历方法。

14. 一无向图G（V，E），其中V（G）={1,2,3,4,5,6,7}，E（G）={（1,2）,(1,3），（2,4），（2,5），（3,6），（3,7），（6,7）（5,1）},对该图从顶点3开始进行遍历，去掉遍历中未走过的边，得一生

成树G’(V，E’）,V（G’）=V（G），E（G’）={（1,3），（3,6），（7,3），（1,2），（1,5），（2,4）}，则采用的遍历方法是______。

15. 按下图所示，画出它的广度优先生成树______和深度优先生成树______。

16．求图的最小生成树有两种算法，______算法适合于求稀疏图的最小生成树。

17.有向图G=(V,E),其中 V(G)={0,1,2,3,4,5}，用三元组表示弧及弧上的权d.E(G)为{<0,5,100>,<0,2,10><1,2,5><0,4,30><4,5,60><3,5,10><2,3,50><4,3,20>}，则从源点0到顶点3的最短路径长度是______，经过的中间顶点是______。

18．AOV网中,结点表示______,边表示______。AOE网中,结点表示______,边表示______。

19．在 AOV网中，存在环意味着______，这是______的；对程序的数据流图来说，它表明存在______。

20. 当一个AOV网用邻接表表示时，可按下列方法进行拓扑排序。

（1）．查邻接表中入度为______的顶点，并进栈；

（2）．若栈不空，则①输出栈顶元素Vj，并退栈；②查Vj的直接后继Vk，对Vk入度处理，处理方法是______；

（3）．若栈空时，输出顶点数小于图的顶点数，说明有______，否则拓扑排序完成。

三、应用题

1．首先将如下图所示的无向图给出其存储结构的邻接链表表示，然后写出对其分别进行深度，广度优先遍历的结果。

2．下面的邻接表表示一个给定的无向图

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

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

3．设G=(V,E)以邻接表存储，如图所示，试画出图的深度优先和广度优先生成树。

4．已知一个无向图如下图所示，要求分别用Prim 和Kruskal 算法生成最小树（假设以①为起点，试画出构造过程）。 第4题 第五题

5．请看无向加权图。 （1）写出它的邻接矩阵；

（2）按Prim 算法求其最小生成树，并给出构造最小生成树过程中辅助数组的各分量值。

6．已知世界六大城市为:北京(Pe)、纽约(N)、巴黎(Pa)、 伦敦(L) 、 东京(T) 、 墨西哥(M),下表给定了这六大城市之间的交通里程:

世界六大城市交通里程表(单位:百公里)

（1）画出这六大城市的交通网络图;

（2）画出该图的邻接表表示法;

（3）画出该图按权值递增的顺序来构造的最小(代价)生成树.

7．下图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求：由顶点V1到顶点V3的最短路径。

8．已知图的邻接矩阵为：

当用邻接表作为图的存储结构，且邻接表都按序号从大到小排序时，试写出： （1）以顶点V1为出发点的唯一的深度优先遍历； （2）以顶点V1为出发点的唯一的广度优先遍历； （3）该图唯一的拓扑有序序列。

123456(顶点边)

（出边表）