首页
登录
从业资格
霍夫曼编码将频繁出现的字符采用短编码,出现频率较低的字符采用长编码。具体的操作过
霍夫曼编码将频繁出现的字符采用短编码,出现频率较低的字符采用长编码。具体的操作过
练习题库
2022-08-02
45
问题
霍夫曼编码将频繁出现的字符采用短编码,出现频率较低的字符采用长编码。具体的操作过程为:i)以每个字符的出现频率作为关键字构建最小优先级队列;ii)取出关键字最小的两个结点生成子树,根节点的关键字为孩子节点关键字之和,并将根节点插入到最小优先级队列中,直至得到一颗最优编码树。霍夫曼编码方案是基于( )策略的。用该方案对包含a到f六个字符的文件进行编码,文件包含100000个字符,每个字符的出现频率(用百分比表示)如下表所示,则与固定长度编码相比,该编码方案节省了( )存储空间。
问题1选项A.分治B.贪心C.动态规划D.回溯问题2选项A.21%B.27%C.18%D.36%
选项
答案
BA
解析
根据题目对霍夫曼编码的描述,我们不难知道,每次都是选择当前最小的情况,这符合贪心算法总是找当前看来最优的情况,因此属于贪心策略。如果对包含100,000个字符,且这些字符都属于a到f。那么如果采用固定长度的编码,针对于每个字符需要3位来编码(因为有6个不同的字符,至少需要3位才能表示6种不同的变化)。那么对100000个字符编码,其编码长度为300000。如果采用霍夫曼编码,那么首先我们就要根据字符出现的频率构造出其霍夫曼树。首先选择出现频率最低的4和8,生成子树,其父节点为12,然后放入出现频率队列中,后面的采用同样的道理,以此类推。构造出的霍夫曼树如下图所示:
由图可以知道,a的编码为00,b的编码为11,c的编码为0110,d的编码为0111,e的编码为010,f的编码为10。因此总的编码长度为(2*18%+2*32%+4*4%+4*8%+3*12%+2*26%)*100000=236000,因此节省的存储空间大小为300000-236000=64000。因此节省的存储空间为比例为64000/300000=21%。
转载请注明原文地址:https://tihaiku.com/congyezige/2409938.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
数字语音的采样频率定义为8kHz这是因为( )。A.语音信号定义的频率最高值
在异步通信中,每个字符包含1位起始位、7位数据位和2位终止位,若每秒钟传送500
在ISO制定并发布的MPEG系列标准中,( )的音、视频压缩编码技术被应用到V
在异步通信中,每个字符包含1位起始位、7位数据位和2位终止位,若每秒钟传送500
数字语音的采样频率定义为8kHz这是因为()。A.语音信号定义的频率最高值为4
MPEG视频中的时间冗余信息可以采用_()_的方法来进行压缩编码。A.帧间预测
未经压缩的数字音频数据传输率的计算公式为_()_。A.采样频率(Hz)*量化位
在异步通信中,每个字符包含1位起始位、7位数据位和2位终止位,若每秒钟传送500
以下媒体中,()是表示媒体,(请作答此空)是表现媒体。A.图像 B.图像编码
以下媒体中,()是感觉媒体。A.音箱 B.声音编码 C.电缆 D.声音
随机试题
Fiftyvolunteerswerealphabeticallydividedintotwoequalgroups,GroupA
Eachofusseeksourownpathtobliss.InacceptingtheNobelPrizefromth
[originaltext]I:Havetheygotanyconclusionastohowpeopleshouldinteract
WhereisHotelParliamentlocated?Itislocatedinthe______ofBudapest.[b
[originaltext]W:Tony,you’vebeenaracing-driverfornearly10years.You’ve
关于构件的描述,正确的是()。A.构件包含了一组需要同时部署的原子构件
以下()都属于健康管理服务内容。A.健康评估 B.健康教育 C.营养与胆固醇
在《江山如此多娇名作赏析》一课中,教师设置了如下教学目标:“在教师的指导下,
下列不属于收方时处方形式审查项目的是A.患者基本信息B.医师签名C.处方内容D.
一位制鞋工人,男性,24岁。自觉疲乏无力两个月。体检:皮肤黏膜苍白,巩膜无黄染,
最新回复
(
0
)