内容发布更新时间 : 2024/12/25 12:42:09星期一 下面是文章的全部内容请认真阅读。
137682543176524316524315243152
4、求下列最小生成树的权值
12234
C(T)=1+2+3=6
31531
C(T)=1+2+3+1=7
24620232836814916153
C(T)=1+3+4+8+9+23=48
1718549761023
C(T)=1+2+3+5+7=18
617713863161712
C(T)=3+6+6+7=22
1687569613114
C(T)=4+5+6+7=22
v292v14510v5v336831012v77v4C(T)=2+3+4+5+6+10=30
11v6
1223410037
56C(T)=2+2+3+5+6+100=118
4879102081215
C(T)=8+9+4+7=28
1355736241
C(T)=1+3+3+2+1=10
125412585854971689716899
54145454153633623662
161139108211176453910827C(T)=1+2+3+5+7=1845
5、在右图所示的带权图中,共有多少棵生成树,他们的权各为多少?,其中哪些是图中的最小生成树?
a1b322d4ca31w=8412w=6bcbca31w=6b2adad1w=74124b2a3w=94b2da3dadw=824cb2cbda3cbdw=72w=72ccdc五、求最优二叉树
对给定的实数序列w1?w2?L?wt,构造最优r元树的递归算法:
1、求最优二元树的Huffman算法:第一步,连接以w1,w2为权的两片树叶,得一个分支点及其所带的权w1?w2;第二步,在w1?w2,w3,L,wt中选出两个最小的权,连接它们对应的结点(不一定都是树叶),又得分支结点及其所带的权;重复第二步,直到形成t?1个分支点,t片树叶为止。
t?1为整数,则求法与求最优二元树的r?1t?1Huffman算法类似,只是每次取r个最小的权;(2)若不为整数,得余数s?[1,r?1),
r?1将s?1个较小的权对应的树叶为兄弟放在最长的路径上,然后算法同(1)。
2、求最优r?r?3?元树的Huffman算法:(1)若
1、找出叶的权分别为2,3,5,7,11,13,17,19,23,29,31,37,41的最优叶加权二叉树,并求其加权路径的长度。(
???w?v??L?v????789)
v?V29111323137411423753
172、求带权为2,3,5,7,8的最优二元树T,并给出T对应的二元前缀码集合。
(B={00,010,011,10,11},W(T)=2?5?3?2?3?3?2?7?2?8?55)
52378
3、求带权为1,2,3,4,5,6,7,8的最优二元树T,并给出T对应的二元前缀码集合。 (B={000,001,01000,01001,0101,011,10,11},W(T)=102)
7456312812578345623 4、(1)求带权为1,1,2,3,3,4,5,6,7的最优三元树;(2)求带权为1,1,2,3,3,4,5,6,7,8的最优三元树
3240201286456104311237157732211345
C(T1)=61,C(T2)=81
六、如图G
v2eafbv3cgdv5
v1v4图中的边割集有S1?{a,f,d},S2?{a,e,b},S3?{b,c,f},