免费智能真题库 > 历年试卷 > 软件设计师 > 2019年下半年 软件设计师 上午试卷 综合知识
  第65题      
  知识点:   二叉树的应用:最优二叉树
  章/节:   计算机软件知识       

 
已知某文档包含5个字符,每个字符出现的频率如下表所示。采用霍夫曼编码对该文档压缩存储,则单词“cade”的编码为(64),文档的压缩比为(65)。
 
 
  A.  20%
 
  B.  25%
 
  C.  27%
 
  D.  30%
 
 
 

  相关试题:二叉树          更多>  
 
  第60题    2011年下半年  
   37%
一棵满二叉树,其每一层结点个数都达到最大值,对其中的结点从1开始顺序编号, 即根结点编号为1,其左、右孩子结点编号分别为2和..
  第60题    2013年下半年  
   34%
以下关于哈夫曼树的叙述,正确的是(60)。
  第58题    2012年下半年  
   22%
若某二叉树的后序遍历序列为KBFDCAE,中序遍历序列为BKEFACD,则该二叉树为(58)。
   知识点讲解    
   · 二叉树的应用:最优二叉树
 
       二叉树的应用:最优二叉树
        霍夫曼树又称最优二叉树,是一类带权路径长度最短的树。
        路径:是指从树中一个节点到另一个节点之间的通路,路径上的分支数目称为路径长度。
        树的路径长度:是从树根到每一个叶子的路径长度之和。节点的带权路径长度为从该节点到树根之间的路径长度与该节点权的乘积。
        树的带权路径长度:指树中所有叶子节点的带权路径长度之和,记为
        
        式中,n为带权叶子节点的数目;wi为叶子节点的权值;li为叶子节点到根的路径长度。
        霍夫曼树是指权值为w1w2,…,wnn个叶子节点的二叉树中带权路径长度最小的二叉树。
        构造最优二叉树的霍夫曼算法如下。
        (1)根据给定的n个权值w1w2,…,Wn构成n棵二叉树的集合F={T1,T2,…,Tn},其中每棵二叉树Ti中只有一个带权为wi的根节点,其左右子树均空。
        (2)在F中选取两棵根节点的权值最小的树作为左右子树,构造一棵新的二叉树,置新构造二叉树的根节点的权值为其左、右子树根节点的权值之和。
        (3)从F中删除这两棵树,同时将新得到的二叉树加入到F中。
        重复(2)、(3),直到F中只含一棵树时为止。这棵树便是霍夫曼树。
   题号导航      2019年下半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
第65题    在手机中做本题