离散数学课后习题答案 - 屈婉玲(高等教育出版社) 下载本文

(a) (b) 图16.16 解:(a)T的弦:c,d,g,h

T的基本回路系统: S={{a,c,b},{a,b,f,d},{e,a,b,h},{e,a,b,f,g}} T的所有树枝: e,a,b,f

T的基本割集系统: S={{e,g,h},{a,c,d,g,h},{b,c,d,g,h},{f,d,g}} (b)有关问题仿照给出

25、求图16.17所示带权图中的最小生成树.

(a) (b)

图16.17

解:

注:答案不唯一。

37、画一棵权为3,4,5,6,7,8,9的最优2叉树,并计算出它的权.

29

38.下面给出的各符号串集合哪些是前缀码? A1={0,10,110,1111} 是前缀码 A2={1,01,001,000} 是前缀码 A3={1,11,101,001,0011} 不是前缀码 A4={b,c,aa,ac,aba,abb,abc} 是前缀码 A5={ b,c,a,aa,ac,abc,abb,aba} 不是前缀码 41.设7个字母在通信中出现的频率如下: a: 35% b: 20% c: 15% d: 10% e: 10% f: 5% g: 5%

用Huffman算法求传输它们的前缀码.要求画出最优树,指出每个字母对应的编码.并指出传输10n(n≥2)个按上述频率出现的字母,需要多少个二进制数字.

解:

a:01 b:10 c:000 d:110 e:001 f:1111 g:1110 W(T)=5*4+5*4+10*3+10*3+15*3+20*2+35*2=255

传输10n(n≥2)个按上述频率出现的字母,需要255*10n-2个二进制数字.

30