【14，4，6】 假设一个文本使用的字符集为{a,b,c,d,e,f,g}, 字符的哈夫曼编码依次为{0110，10，110，111，00，0111，010}。
（1）请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应的字符；
0
1
0 e
b
1
g
c d
a
f
（2）若这些字符在文本中出现的频率分别为：{3,35,13,15,20,5,9}，求该哈夫曼树的带权路径长度。
WPL=4*(3+5)+3*(9+13+15)+2*(20+35)=253
【15，5，3】用公式5.6计算一下你的身份证号码的散列值是多少。 924300
【16，5，4】设有一组关键字{29，01，13，15，56，20，87，27，69，9，10，74}，散列函数为：H(key) = key % 17，采用平方探测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表。
首先将各个数除以17取余数：（6,2,7,1,2,7,7,6）可见20,85与46冲突，58与71冲突。将7+1再对13取余，直到无冲突，类似的6+1对13取余，最后可得H(71)=6；H（28）=2；H（46）=7；H(14)=1；H(2)=3；H(20)=8；H(85)=9；
16
H(58)=10； 哈希表存储结构：
0 1 2 3 4 5 6 7 8 9 10 14 28 2 71 46 20 85 58
平均查找长度=（1×4+2×2+3×1+4×1）/8=15/8
【17，5，4】将关键字序列（7，8，30，11，18，9，14）散列存储到散列列表中，散列表的存储空间是一个下标从0开始的一个一维数组。处理冲突采用线性探测法，散列函数为：H（key）=（key×3）mod TableSize，要求装入因子为0.7。
由装载因子0.7，数据总数7个→存储空间长度为10→P=10 所以，构造的散列表为： H（7）=（7×3）MOD10=1 0 30 1 7 2 14 3 11 4 8 5 18 6 . 7 9 8 . 9 . 查找成功的ASL=(1+1+1+1+2+1+1)/7=8/7
查找不成功的ASL=(7+6+5+4+3+2+1+2+1+1)/10=3.2
【18，6，3】已知一个无向图的顶点集为{V0，V1，…，V7}，其邻接矩阵如下所示：
V0 0 1 0 1 1 0 0 0 V1 1 0 1 0 1 0 0 0 V2 0 1 0 0 0 1 0 0 V3 1 0 0 0 0 0 1 0 V4 1 1 0 0 0 0 1 0 V5 0 0 1 0 0 0 0 0 V6 0 0 0 1 1 0 0 1 V7 0 0 0 0 0 0 0 1
(1) 画出该图的图形；
17
1 2 0 3 6 4 5 7
(2) 给出从V0出发的深度优先遍历序和广度优先遍历序。 深度优先序列 V0,V1,V2,V5,V4,V6,V3,V7 广度优先序列 V0 V1 V3 V4 V2 V6 V5 V7
【19，6，3】已知有向图如右图所示，请给出该图的 （1） 每个顶点的入度和出度； （2） 邻接矩阵； （3） 邻接表； （4） 逆邻接表；
（5） 各个强连通分量。
各顶点的入度和出度如下：
①：3/0 ②2/2 ③ 1/2 ④1/2 ⑤ 2/1 ⑥2/3 邻接矩阵如下： 1 2 3 4 1 0 0 0 0 2 1 0 0 1 3 0 1 0 0 4 0 0 1 0 5 1 0 0 0
18
5 0 0 0 1 0 6 0 0 1 1 0
6 1 1 0 0 1 0 邻接表如下：
逆邻接表
有三个强连通分量
19
【20，6，3】试利用Dijkstra算法求下图在从顶点A到其它顶点的最短距离及对应的路径，写出计算过程中各步状态。
终点 Dist K＝1 K＝2 K＝3 K＝4 K＝5 K＝6
b 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) 15 (a,b) c 2 (a,c) d 12 (a,d) 12 (a,d) 11 (a,c,f,d) 11 (a,c,f,d) e 10 (a,c,e) 10 (a,c,e) f 6 (a,c,f) g 16 (a,c,f,g) 16 (a,c,f,g) S {a,c} {a,c,f} {a,c,f,e} {a,c,f,e,d} 14 {a,c,f,e,d,g} (a,c,f,d,g) {a,c,f,e,d,b} 【21，6，3】给出如下图所示的具有7个结点的网G。请：
（1） 画出该网的邻接矩阵；
（2） 采用Prim算法，从4号结点开始，给出该网的最小生成树（画出Prim算法
的执行过程及最小生成树的生成示意图）。
1
1 6 2 3 7 4 0 5 6 2 5 3 3 2 5 1 4 20 4