2014数据结构习题集答案(3)

2020-04-17 22:12

3.

(1) (2) 6 5 5 3 6 6

(3) (4)

4.

表1 各事件(顶点)的最早发生时间和最迟发生时间为: 顶点 a b c d e f g h k ve 0 6 4 5 7 7 15 14 18 vl 0 6 6 8 7 10 16 14 18 表2 各活动(弧)的最早开始时间和最迟开始时间为: 弧 ab ac ad be ce df eg eh fh ghk k e 0 0 0 6 4 5 7 7 7 115 4 l 0 2 3 6 6 8 8 7 1110 6 4 关键路径为: , , ,

5.

V1 (1)有向带权图的邻接矩阵为: V2 (V3 3)深度优先生成树。??023??????V4 ??0?5?????V6 ????0310?????????0?4??????????0?3??

V5 V7 ?????20?6???V8 ???????01??????????0???

(2)拓扑排序有两种可能结果:V1V2V3V4V6V5V7V8V1V3V2 V4V6V5V7V8

终从V1到各终点的距离点 和最短路径的求解过程

和 ii==2 1 V--2 2 ---- V3 3 3 V4 V5 V6 V7 i=i=i=i=i= (4) 注:斜粗体的部分为所求。 3 4 5 6 7

-------------------------------- -- -- -- -- -------------------------------- -- -- -- -- ------------∞ 7 6 -------------- -- -- -- ------∞∞ 13 13 12 -------- -- ---------∞∞ ∞ 10 ----------- -- -- ---∞∞ ∞ ∞ ∞ 15 ----- V∞∞ ∞ ∞ 16 16 16 8 vvvv4 v6 v5 v7 v8 j 2 3 第九章 参考答案:

一.单选与填空

1.4 2. B 3.B 4.C 5.B 6.D 7.B 8. C 9.D 二.解答题

1. 长度为12的有序表进行折半查找的判定树为: 6

9 3

4 11 1 7

2 8 1012 5 6

等概率查找成功时的平均查找长度为: (1×1+2×2+4×3+5×4)/12=37/12 2.

3.

0123456789103355236538402053

成功:(1+2+2+5+1+1+1+2)/8=15/8; 不(5+4+3+2+1+2+1+2+1+7+6)/11=34/11 4. 0

49 ∧ 1

22 ∧ 2

∧ 3

∧ 4 32 39 ∧ 5 ∧ 6 13 55 20 ∧

成功:ASLsucc= (1*4+2*2+3)/7=11/7; 不成功:(1+1+2+3)/7=7/7=1 5.

成功:ASLnsucc=


2014数据结构习题集答案(3).doc 将本文的Word文档下载到电脑 下载失败或者文档不完整,请联系客服人员解决!

下一篇:服装立体裁剪教案

相关阅读
本类排行
× 注册会员免费下载(下载后可以自由复制和排版)

马上注册会员

注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信: QQ: