数据结构习题及参考答案(8)

习题6参考答案

一、单项选择题

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 15. B 16. C 17. A 18. A 19. B 20. D 21. A 22. C 23. B 24. A 二、填空题

1. 2 2. n(n-1)/2，n(n-1) 3. 2，4 4. n-1 5. 邻接矩阵，邻接表 6. 1 7. k+1 8. 3

9. n，n 10. 2e，e 11. 出边，入边 12. O（n），O（e/n） 13.O（n2

），O（n+e） 14. acdeb，acedb （答案不唯一） 15. acfebd，acefbd （答案不唯一） 16. 深度，广度 17. n，n-1 18. 唯一

19. 唯一 20. aebdcf（答案不唯一） 三、应用题

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. 过程如图6-16所示 50 V1 60 V3 V1 V3 50 V1 V3 52 45 65 42 V2 V2 V4 V7 50 V4 V7 V2 V4 V7 40 30 V5 V6 V5 70 V6 V5 V6 (a)

(b) (c)

50 V1 V3 50 V1 V3 50 V1 V3 V2 V4 V7 V2 V4 V7 V2 V4 V7 40 V5 V6 40 50 V5 V6 40 50 30 V5 V6 (d)

(e)

(f)

50 V1 V3 50 V1 V3 45 -36-

14. B

6. 求解过程如图6-17所示。 V1 V3 V1 V3 V1 V3

V2 V4 V7 V2 V4 V7 V2 V4 42 V7 30 40

V5 V6 V5 30 V6 40 V5 30 V6 (a) (b)

(c)

V1 V3 45 50 V1 V3 V1 V3 V2 V4 42 V7 V2 V4 42 45 50 45 V7 V2 40 V5 30 V6 40 50 V4 42 V7 V5 30 V6 40 V5 30 V6 (d) (e)

(f)

图6-17

7. 求解过程如下表所示。 终点 从v0到各终点的D值和最短路径的求解过程 i=1 i=2 i=3 i=4 i=5 V1 ∞ ∞ ∞ ∞ ∞ 无 V2 10 (v0,v2) V3 ∞ 60 50 -37-

(v0,v2,v3) (v0,v4,v3) V4 30 30 (v0,v4) (v0,v4) V5 100 100 90 60 (v0,v5) (v0,v5) (v0,v4,v5) (v0,v4,v3,v5)

Vj V2 V4 V3 V5 S {v0,v2} {v0,v2,v4} {v0,v2,v3,v4} {v0,v2,v3,v4,v5}

8. 求解过程如下：

①事件的最早发生时间ve[k]。 ve (1)=0 ve (2)=3 ve (3)=4

ve (4)=ve(2)+2=5

ve (5)=max{ve(2)+1,ve(3)+3}=7 ve (6)=ve(3)+5=9

ve (7)=max{ve(4)+6,ve(5)+8}=15 ve (8)=ve(5)+4=11

ve (9)=max{ve(8)+10,ve(6)+2}=21 ve (10)=max{ve(8)+4,ve(9)+1}=22 ve (11)=max{ve(7)+7,ve(10)+6}=28

②事件的最迟发生时间vl[k]。 vl (11)= ve (11)=28 vl (10)= vl (11)-6=22 vl (9)= vl (10)-1=21

vl (8)=min{ vl (10)-4, vl (9)-10}=11 vl (7)= vl (11)-7=21 vl (6)= vl (9)-2=19

vl (5)=min{ vl (7)-8,vl (8)-4}=7 vl (4)= vl (7)-6=15

vl (3)=min{ vl (5)-3, vl (6)-5}=4 vl (2)=min{ vl (4)-2, vl (5)-1}=6 vl (1)=min{vl (2)-3, vl (3)-4}=0

③活动ai的最早开始时间e[i]和最晚开始时间l[i]。

活动a1 e (1)=ve (1)=0 l (1)=vl (2) -3 =3 活动a2 e (2)=ve (1)=0 l (2)=vl (3) - 4=0 活动a3 e (3)=ve (2)=3 l (3)=vl (4) - 2=13 活动a4 e (4)=ve (2)=3 l (4)=vl (5) - 1=6 活动a5 e (5)=ve (3)=4 l (5)=vl (5) - 3=4

-38-

活动a6 e (6)=ve (3)=4 l (6)=vl (6) - 5=14 活动a7 e (7)=ve (4)=5 l (7)=vl (7) - 6=15 活动a8 e (8)=ve (5)=7 l (8)=vl (7) - 8=13 活动a9 e (9)=ve (5)=7 l (9)=vl (8) - 4=7 活动a10 e (10)=ve (6)=9 l (10)=vl (9) - 2=19 活动a11 e (11)=ve (7)=15 l (11)=vl (11) - 7=21 活动a12 e (12)=ve (8)=11 l (12)=vl (10) - 4=18 活动a13 e (13)=ve (8)=11 l (13)=vl (9) - 10=11 活动a14 e (14)=ve (9)=21 l (14)=vl (10) -1=21 活动a15 e (15)=ve (10)=22 l (15)=vl (11) -6 =22

④最后，比较e[i]和l[i]的值可判断出a2,a5,a9,a13,a14,a15是关键活动，关键路径如图6-18所示。

a9=4 v1 a2=4 v5 v3 a5=3 v11 a15=6 v8 a13=10 v9

四、算法设计题

图6-18

v1001 a14=1 1. int degree1(Graph & ga, int numb)

{ //根据无向图的邻接矩阵求出序号为numb的顶点的度数 int j,d=0;

for(j=0; j

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

d++;

return (d); }

2. int degree2(Graph & ga, int numb)

//根据有向图的邻接矩阵求出序号为numb的顶点的度数 { int i,j,d=0;

//求出顶点numb的出度 for(j=0; j

-39-

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

d++;

//求出顶点numb的入度 for(i=0; i

d++; //返回顶点numb的度 return (d); }

3. int degree3(GraphL & gl, int numb)

//根据无向图的邻接表求出序号为numb的顶点的度数 { int d=0;

vexnode * p=gl.adjlist[numb]; while(p!=NULL) { d++; p=p->next;

} return (d); }

4. int degree4(GraphL & gl, int numb)

//根据有向图的邻接表求出序号为numb的顶点的度数 { int d=0, i;

vexnode * p=gl.adjlist[numb]; while (p!=NULL) { d++; p=p->next;

} //求出顶点numb的出度 for(i=0; i

{ if(p->vertex= =numb) d++;

p=p->next; }

}//求出顶点numb的入度

return (d); //返回顶点numb的度数 }

-40-

百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典综合文库数据结构习题及参考答案(8)在线全文阅读。