haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 小学教育 > 学科竞赛学科竞赛

B070106 图图的辅导练习题及解答

发布时间:2014-03-06 19:32:46  

数据结构专科辅导六

------图的辅导练习题及解答

(一)单项选择题

1. 在一个具有n个顶点的有向图中,若所有顶点的出度数之和为s,则所有顶点的入度数之和为( )。

A s B s-1 C s+1 D n

2. 在一个具有n个顶点的有向图中,若所有顶点的出度数之和为s,则所有顶点的度数之和为( )。

A s B s-1 C s+1 D 2s

3. 在一个具有n个顶点的无向图中,若具有e条边,则所有顶点的度数之和为( )。

A n B e C n+e D 2e

4. 在一个具有n个顶点的无向完全图中,则所含的边数为( )。

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

5. 在一个具有n个顶点的有向完全图中,则所含的边数为( )。

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

6. 在一个无权图中,若两顶点之间的路径长度为k,则该路径上的顶点数为( )。

A k B k+1 C k+2 D 2k

7. 对于一个具有n个顶点的无向连通图,它包含的连通分量的个数为( )。

A 0 B 1 C n D n+1

8. 若一个图中包含有k个连通分量,若要按照深度优先搜索的方法访问所有顶点,则必须调用( )次深度优先搜索遍历的算法。

A k B 1 C k-1 D k+1

9. 若要把n个顶点连接为一个连通图,则至少需要( )条边。

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

10. 在一个具有n个顶点和e条边的无向图的邻接矩阵中,表示边存在的元素(又称为有效元素)的个数为( )。

A n B n?e C e D 2?e

11. 在一个具有n个顶点和e条边的有向图的邻接矩阵中,表示边存在的元素个数为

( )。

A n B n?e C e D 2?e

12. 在一个具有n个顶点和e条边的无向图的邻接表中,边结点的个数为( )。

A n B n?e C e D 2?e

13. 在一个具有n个顶点和e条边的有向图的邻接表中,保存顶点单链表的表头指针向量的大小至少为( )。

A n B 2n C e D 2e

14. 在一个无权图的邻接表表示中,每个边结点至少包含( )域。

A 1 B 2 C 3 D 4

15. 对于一个有向图,若一个顶点的度为k1,出度为k2,则对应邻接表中该顶点单链表中的边结点数为( )。

A k1 B k2 C k1-k2 D k1+k2

16. 对于一个有向图,若一个顶点的度为k1,出度为k2,则对应逆邻接表中该顶点单链表中的边结点数为( )。

1

A k1 B k2 C k1-k2 D k1+k2

17. 对于一个无向图,下面( )种说法是正确的。

A 每个顶点的入度等于出度 B 每个顶点的度等于其入度与出度之和

C 每个顶点的入度为0 D 每个顶点的出度为0

18. 在一个有向图的邻接表中,每个顶点单链表中结点的个数等于该顶点的( )。

A 出边数 B 入边数 C 度数 D 度数减1

19.若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)},则从顶点A开始对该图进行深度优先搜索,得到的顶点序列可能为( )。

A A,B,C,F,D,E B A,C,F,D,E,B

C A,B,D,C,F,E E A,B,D,F,E,C

20. 若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)},则从顶点A开始对该图进行广度优先搜索,得到的顶点序列可能为( )。

A A,B,C,D,E,F B A,B,C,F,D,E

C A,B,D,C,E,F D A,C,B,F,D,E

21. 若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>},则从顶点1开始对该图进行深度优先搜索,得到的顶点序列可能为( )。

A 1,2,5,4,3 B 1,2,3,4,5

C 1,2,5,3,4 C 1,4,3,2,5

22. 若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>},则从顶点1开始对该图进行深度优先搜索,得到的顶点序列可能为( )。

A 1,2,3,4,5 B 1,2,4,3,5

C 1,2,4,5,3 D 1,4,2,5,3

23. 由一个具有n个顶点的连通图生成的最小生成树中,具有( )条边。

A n B n-1 C n+1 D 2?n

24. 已知一个无向图的边集为{(0,1)3, (0,2)5, (0,3)6, (1,4)10, (2,3)2, (2,4)9, (3,4)8},则该图的最小生成树的权为( )。

A 43 B 16 C 18 D 23

25. 已知一个无向图的边集为{(0,1)3, (0,2)5, (0,3)6, (1,4)10, (2,3)2, (2,4)9, (3,4)8},则该图的最小生成树的边集为( )。

A {(0,1)3,(0,2)5,(0,3)6,(3,4)8} B {(0,1)3,(0,2)5,(0,3)6,(2,3)2}

C {(2,3)2,(0,2)5,(3,4)8,(0,3)6} D {(2,3)2,(0,2)5,(3,4)8,(0,1)3}

26. 已知一个有向图的边集为{<a,b>,<a,c>,<a,d>,<b,d>,<b,e>,<d,e>},则由该图产生的一种可能的拓扑序列为( )。

A a,b,c,d,e B a,b,d,e,b

C a,c,b,e,d D a,c,d,b,e

(二)填空题

1.在一个图中,所有顶点的度数之和等于所有边数的________倍。

2.在一个具有n个顶点的无向完全图中,包含有________条边,在一个具有n个顶点的有向完全图中,包含有________条边。

3.已知一个连通图的边集为{(1,2)3, (1,3)6, (1,4)8, (2,3)4, (2,5)10, (3,5)12, (4,5)2},则度为3的顶点个数有________个。

4.假定一个有向图的顶点集为{a,b,c,d,e,f},边集为{<a,c>, <a,e>, <c,f>, <d,c>, <e,b>, <e,d>},则出度为0的顶点个数为________,入度为1的顶点个数为________。 2

5. 在一个具有n个顶点的无向图中,要连通所有顶点则至少需要________条边。

6.表示图的两种存储结构为__________和__________。

7.在一个连通图中存在着________个连通分量。

8.图中的一条路径长度为k,该路径所含的顶点数为________。

9. 若一个图的顶点集为{a,b,c,d,e,f},边集为{(a,b),(a,c),(b,c),(d,e)},则该图含有________个连通分量。

10.一个图的边集为{<0,1>3,<0,2>5,<0,3>5,<0,4>10,<1,2>4,<2,4>2,<3,4>6>},则从顶点V0到顶点V4共有________条简单路径。

11.一个图的边集为{<0,1>3,<0,2>5,<0,3>5,<0,4>10,<1,2>4,<2,4>2,<3,4>6>},则从顶点V0到顶点V4的最短路径长度为________。

12. 对于一个具有n个顶点的图,若采用邻接矩阵表示,则矩阵大小至少为________?________。

13.对于一个具有n个顶点和e条边的有向图和无向图,在其对应的邻接表中,所含边结点的个数分别为________和________。

14. 在有向图的邻接表和逆邻接表表示中,每个顶点邻接表分别链接着该顶点的所有________和________结点。

15.对于一个具有n个顶点和e条边的无向图,当分别采用邻接矩阵和邻接表表示时,求任一顶点度数的时间复杂性分别为________和________。

16. 假定一个图具有n个顶点和e条边,则采用邻接矩阵和邻接表表示时,其相应的空间复杂性分别为________和________。

17. 对用邻接矩阵表示的图进行任一种遍历时,其算法的时间复杂性为________,对用邻接表表示的图进行任一种遍历时,其算法的时间复杂性为________。

18.一个图的边集为{(a,c),(a,e),(b,e),(c,d),(d,e)},从顶点a出发进行深度优先搜索遍历得到的顶点序列为____________,从顶点a出发进行广度优先搜索遍历得到的顶点序列为____________。

19. 一个图的边集为{<a,c>,<a,e>,<c,f>,<d,c>,<e,b>,<e,d>},从顶点a出发进行深度优先搜索遍历得到的顶点序列为____________,从顶点a出发进行广度优先搜索遍历得到的顶点序列为____________。

20. 图的________优先搜索遍历算法是一种递归算法,图的________优先搜索遍历算法需要使用队列。

21. 对于一个具有n个顶点和e条边的连通图,其生成树中的顶点数和边数分别为________和________。

22. 已知一个连通图的边集为{(1,2)3, (1,3)6, (1,4)8, (2,3)4, (2,5)10, (3,5)12, (4,5)2},该图的最小生成树的权为________。

23.若一个连通图中每个边上的权值均不同,则得到的最小生成树是________(唯一/不唯一)的。

24.根据图的存储结构进行某种次序的遍历,得到的顶点序列是________(唯一/不唯

一)的。

25.已知一个连通图的边集为{(1,2)3, (1,3)6, (1,4)8, (2,3)4, (2,5)10, (3,5)12, (4,5)2},若从顶点V1出发,按照普里姆算法生成的最小生成树的过程中,依次得到的各条

边为_______________。

26.假定一个有向图的边集为{<a,c>,<a,e>,<c,f>,<d,c>,<e,b>,<e,d>},对该图进行拓扑排序得到的顶点序列为________。

3

(三)应用题

1. 对于一个无向图6-1(a),假定采用邻接矩阵表示,试分别写出从顶点v0出发按深度

优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。

深度优先搜索序列:

广度优先搜索序列:

注:每一种序列都是唯一的,因为都是在存储结构上得到的。

2. 对于一个有向图6-1(b),假定采用邻接表表示,并且假定每个顶点单链表中的边结点是按出边邻接点序号从大到小的次序链接的,试分别写出从顶点v0出发按深度优先搜索

遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。

深度优先搜索序列:

广度优先搜索序列:

注:每一种序列都是唯一的,因为都是在存储结构上得到的。

图 7-25

图6-1

3.已知一个无向图的邻接矩阵如图6-2(a)所示,试写出从顶点v0出发分别进行深度优

先和广度优先搜索遍历得到的顶点序列。

深度优先搜索序列:

广度优先搜索序列:

4.已知一个无向图的邻接表如图6-2(b)所示,试写出从顶点v0出发分别进行深度优先

和广度优先搜索遍历得到的顶点序列。

深度优先搜索序列:

广度优先搜索序列:

(a) (b)

4

图6-2

5. 已知一个有向图的邻接矩阵如图6-3(a)所示,试写出从顶点v0出发分别进行深度优

先和广度优先搜索遍历得到的顶点序列。

深度优先搜索序列:

广度优先搜索序列:

6.已知一个有向图的邻接表如图6-3(b)所示,试写出从顶点v0出发分别进行深度优先

和广度优先搜索遍历得到的顶点序列。

深度优先搜索序列:

广度优先搜索序列:

(a) (b)

图6-3

(四)算法设计题

1. 编写一个算法,求出邻接矩阵表示的无向图中序号为numb的顶点的度数。 int degree1(GraphTpA& ga, int numb)

2. 编写一个算法,求出邻接矩阵表示的有向图中序号为numb的顶点的度数。 int degree2(GraphTpA& ga, int numb)

3. 编写一个算法,求出邻接表表示的无向图中序号为numb的顶点的度数。 int degree3(GraphTpL& gl, int numb)

4. 编写一个算法,求出邻接表表示的有向图中序号为numb的顶点的度数。 int degree4(GraphTpL& gl, int numb)

5.编写一个算法,求出一个用邻接矩阵表示图的所有顶点的最大出度值。 int maxOutDegree(GraphTpA& ga)

练习题参考解答

(一)单项选择题

1. A 2. D 3. D 4. C 5. B 6. B

7. B 8. A 9. C 10. D 11. C 12. D

13. A 14. B 15. B 16. C 17. A 18. A

19. B 20. D 21. A 22. C 23. B 24. C

25. D 26. A

5

(二)填空题

1. 2 2. n(n-1)/2 n(n-1)

3. 4 4. 2 4

5. n-1 6. 邻接矩阵 邻接表

7. 1 8. k+1

9. 3 10. 4

11. 7 12. n n

13. 2e e 14. 出边 入边

15. O(n) O(e/n) 16. O(n2) O(n+e)

17. O(n2) O(e) 18. a,c,d,e,b a,c,e,d,b (答案不唯一)

19. a,c,f,e,b,d a,c,e,f,b,d (答案不唯一)

20. 深度 广度 21. n n-1

22. 17 23. 唯一

24. 唯一 25. (1,3)3,(2,3)4,(1,4)8,(4,5)2

26. a,e,b,d,c,f (答案不唯一)

(三)应用题

1. 深度优先搜索序列:0,1,2,8,3,4,5,6,7,9

广度优先搜索序列:0,1,4,2,7,3,8,6,5,9

2. 深度优先搜索序列:0,4,7,5,8,3,6,1,2

广度优先搜索序列:0,4,3,1,7,5,6,2,8

3. 深度优先搜索序列:0,2,3,5,6,1,4

广度优先搜索序列:0,2,3,5,6,1,4

4. 深度优先搜索序列:0,3,6,4,1,5,2

广度优先搜索序列:0,3,2,6,5,4,1

5. 深度优先搜索序列:0,1,4,6,2,5,3

广度优先搜索序列:0,1,2,3,4,5,6

6. 深度优先搜索序列:0,2,5,6,1,4,3

广度优先搜索序列:0,2,3,1,5,6,4

(四)算法设计题

1.

//根据无向图的邻接矩阵求出序号为numb的顶点的度数

int degree1(GraphTpA& ga, int numb)

{

int j,d=0;

for(j=0; j<ga.vexnum; j++)

if(ga.ares[numb][j]!=0 && ga.ares[numb][j]!=MAXINT)

d++;

return d;

}

2.

6

//根据有向图的邻接矩阵求出序号为numb的顶点的度数

int degree2(GraphTpA& ga, int numb)

{

int i,j,d=0;

//求出顶点numb的出度

for(j=0; j<ga.vexnum; j++)

if(ga.ares[numb][j]!=0 && ga.ares[numb][j]!=MAXINT) d++;

//求出顶点numb的入度

for(i=0; i<ga.vexnum; i++)

if(ga.ares[i][numb]!=0 && ga.ares[i][numb]!=MAXINT) d++;

//返回顶点numb的度

return d;

}

3.

//根据无向图的邻接表求出序号为numb的顶点的度数

int degree3(GraphTpL& gl, int numb)

{

int d=0;

AreNodeTp* p=gl.adjlist[numb];

while(p!=NULL) {

d++;

p=p->nextare;

}

return d;

}

4.

//根据有向图的邻接表求出序号为numb的顶点的度数

int degree4(GraphTpL& gl, int numb)

{

int d=0;

//求出顶点numb的出度

AreNodeTp* p=gl.adjlist[numb];

while(p!=NULL) {

d++;

p=p->nextare;

}

//求出顶点numb的入度

int i;

for(i=0; i<gl.vexnum; i++) {

p=gl.adjlist[i];

7

while(p!=NULL) {

if(p->adjvex==numb) d++;

p=p->nextare;

}

}

//返回顶点numb的度数

return d;

}

5.

//求出一个图中所有顶点的最大出度值

int maxOutDegree(GraphTpA& ga)

{

int i,j,max=0;

//求出所有顶点的最大出度值

for(i=0; i<ga.vexnum; i++) {

//将顶点的出度置为0

int k=0;

//统计出顶点i的出度

for(j=0; j<ga.vexnum; j++)

if(ga.ares[i][j]!=0 && ga.ares[i][j]!=MAXINT) k++;

//若k的值大于max则用它修改max的值

if(k>max) max=k;

}

//返回所有顶点的最大出度值

return max;

}

8

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com