77范文网 - 专业文章范例文档资料分享平台

数据结构各章习题及答案!!(10)

来源:网络收集 时间:2019-08-01 下载这篇文档 手机版
说明:文章内容仅供预览,部分内容可能不全,需要完整文档或者需要复制内容,请下载word后使用。下载word有问题请添加微信号:或QQ: 处理(尽可能给您提供完整文档),感谢您的支持与谅解。点击这里给我发消息

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

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

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

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

20. 假定一个有向图的边集为{,,,,,},对该图进行拓扑排序得到的顶点序列为________。 20. aebdcf(答案不唯一)

三、应用题

1. 对于一个无向图6-11(a),假定采用邻接矩阵表示,试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。

注:每一种序列都是唯一的,因为都是在存储结构上得到的。 1. 深度优先搜索序列:0,1,2,8,3,4,5,6,7,9 广度优先搜索序列:0,1,4,2,7,3,8,6,5,9

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

注:每一种序列都是唯一的,因为都是在存储结构上得到的。 0 0 1 2 1 4 6 5 3 4 5 7 9

8

6 2 3 7 8 (a) (b)

图6-11

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

3. 已知一个无向图的邻接矩阵如图6-12(a)所示,试写出从顶点0出发分别进行深度优先和广度优先搜索遍历得到的顶点序列。 3. 深度优先搜索序列:0,2,3,5,6,1,4 广度优先搜索序列:0,2,3,5,6,1,4

4. 已知一个无向图的邻接表如图6-12(b)所示,试写出从顶点0出发分别进行深度优先和广度优先搜索遍历得到的顶点序列。

(a) (b)

图6-12

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

5. 已知图6-13所示的一个网,按照Prim方法,从顶点1 出发,求该网的最小生成树的产生过程。

5. 过程如图6-16所示 60 V1 V3 V1 V1 V3 V3 50 50 45 52 65 42 V4 V7 V2 V4 V4 V7 V7 V2 V2 50 30 40 V5 V6 V5 V5 V6 V6 70 (c) (b) (a)

V1 V1 V3 V1 V3 V3

50 50 50

V4 V7 V2 V4 V7 V4 V7 V2 V2 50 30 50 40 40 40 V5 V6 V5 V6 V5 V6

(f) (d) (e)

V1 V3 V1 V3 50 50 45 42 42 V2 V4 V7 V7 V4 V2 50 30 50 30 40 40 V5 V6 V5 V6

(g)

图6-16

(h)

6. 已知图6-13所示的一个网,按照Kruskal方法,求该网的最小生成树的产生过程。

60 V1 V3 50 45 52

42 65 V4 V7 V2

50 30 40 V5 V6 70 图6-13

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

42 V7 V4 V4 V4 V7 V2 V2 V2 V7 30 30 30 40 40 V5 V5 V6 V6 V5 V6

(a)

V1 V3 45 42

V7 V4 V2

30 40 V5 V6

(d)

(b)

(c)

50 V2 40 V1 V4 V5 30 (e)

V3 42 45 V7 V6 42 V4 V7 V2 50 40 30 V5 V6 (f)

50 V1 V3 45 图6-17

7. 图6-14所示为一个有向网图及其带权邻接矩阵,要求对有向图采用Dijkstra算法,求从V0 到其余各顶点的最短路径。

V5 100 60 30 V0 V4 ∞ ∞ 10 ∞ 30 100

∞ ∞ 5 ∞ ∞ ∞ 10 20 10 ∞ ∞ ∞ 50 ∞ ∞ V1 ∞ ∞ ∞ ∞ ∞ 10

∞ ∞ ∞ 20 ∞ 60 5 V3 50 ∞ ∞ ∞ ∞ ∞ ∞ V2 (b) 带权邻接矩阵 (a) 有向带权图

图6-14 有向带权图及其邻接矩阵 7. 求解过程如下表所示。

终点 从v0到各终点的D值和最短路径的求解过程 i=1 i=2 ∞ i=3 ∞ i=4 ∞ i=5 ∞ 无 ∞ 10 (v0,v2)

V1 V2

V3 V4 ∞ 30 60 (v0,v2,v3) 30 50 (v0,v4,v3) (v0,v4) (v0,v4) V5 100 (v0,v5) Vj S V2 100 (v0,v5) V4 90 (v0,v4,v5) V3 {v0,v2,v3,v4} 60 (v0,v4,v3,v5) V5 {v0,v2,v3,v4,v5}

{v0,v2} {v0,v2,v4} 8. 图6-15给出了一个具有15个活动、11个事件的工程的AOE网,求关键路径。 v4 a7=6 a3=2 v7 v2 a4=1 a1=3 a11=7 a8=8

v5 v1 a9=4 a5=3 a2=4 v11 v3 v8 a12=4

a13=10 a15=6a6=5

v6 v1001

a10=2 v9 a14=1 图6-15 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 活动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 v5 v3 a2=4 a5=3 v11 v8 a15=6 a13=10 v9 v1001 a14=1

四、算法设计题

图6-18

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

int degree1(Graph & ga, int numb)

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读,免费范文网,提供经典小说教育文库数据结构各章习题及答案!!(10)在线全文阅读。

数据结构各章习题及答案!!(10).doc 将本文的Word文档下载到电脑,方便复制、编辑、收藏和打印 下载失败或者文档不完整,请联系客服人员解决!
本文链接:https://www.77cn.com.cn/wenku/jiaoyu/668388.html(转载请注明文章来源)
Copyright © 2008-2022 免费范文网 版权所有
声明 :本网站尊重并保护知识产权,根据《信息网络传播权保护条例》,如果我们转载的作品侵犯了您的权利,请在一个月内通知我们,我们会及时删除。
客服QQ: 邮箱:tiandhx2@hotmail.com
苏ICP备16052595号-18
× 注册会员免费下载(下载后可以自由复制和排版)
注册会员下载
全站内容免费自由复制
注册会员下载
全站内容免费自由复制
注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信: QQ: