第2题
A.一般在哈夫曼树中,权值越大的叶子离根结点越近
B.哈夫曼树中没有度数为1的分支结点
C.若初始森林中共有n裸二叉树,最终求得的哈夫曼树共有2n-1个结点
D.若初始森林中共有n裸二叉树,进行2n-1次合并后才能剩下一棵最终的哈夫曼树
第3题
A、不确定
B、2N-1
C、2N+1
D、2N
第4题
(8)A.贪心
B.分治
C.递推
D.回溯
【我提交的答案】: B |
【参考答案与解析】: 正确答案:A |
解析:给定一个序列的集合,若不存在一个序列是另一个序列的前缀,则该序列集合称为前缀码。相反,给定一个序列的集合,若不存在一个序列是另一个序列的后缀,则该序列集合称为后缀码。平均码长或文件总长最小的前缀编码称为最优的前缀码,最优的前缀码对文件的压缩效果亦最佳。
利用哈夫曼树很容易求出给定字符集及其概率(或频度)分布的最优前缀码。哈夫曼编码是一种应用广泛且非常有效的数据压缩技术,该技术一般可将数据文件压缩掉 20%至90%,其压缩效率取决于被压缩文件的特征。在构造哈夫曼树的过程中,每次都是选取两棵最小权值的二叉树进行合并,因此使用的是贪心算法。
哈夫曼树的具体构造过程如下:
假设有n个权值,则构造出的哈夫曼树有n个叶子结点。n个权值分别设为w1, w2,…,wn,则哈夫曼树的构造规则为:
(1)将w1,w2,…,wn看成是有n棵树的森林(每棵树仅有一个结点);
(2)在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;
(3)从森林中删除选取两棵树,并将新树加入森林;
(4)重复第(2)和(3)步,直到森林中只剩一棵树为止,该树即为所求的哈夫曼树。
什么是贪心算法
第5题
A.2n
B.2n十2
C. 2n-1
D.2n+1
为了保护您的账号安全,请在“上学吧”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!