文档库

最新最全的文档下载
当前位置:文档库 > 第7章练习题

第7章练习题

第七章的练习题

一、选择题

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 B.n (n +1) 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个

第7章练习题

第7章练习题

第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.右图中的强连通分量的个数为______个。

第7章练习题

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.首先将如下图所示的无向图给出其存储结构的邻接链表表示,然后写出对其分别进行深度,广度优先遍历的结果。

第7章练习题

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

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

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

第7章练习题

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

第7章练习题

第7章练习题

第7章练习题

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

5.请看无向加权图。 (1)写出它的邻接矩阵;

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

第7章练习题

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

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

第7章练习题

第7章练习题

(1)画出这六大城市的交通网络图;

(2)画出该图的邻接表表示法;

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

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

第7章练习题

8.已知图的邻接矩阵为:

第7章练习题

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

123456(顶点边)

(出边表)