首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下预备知识、函数说明和C代码,将应填入(n)处的字句写在对应栏内。 【预备知识】 ①对给定的字符集合及相应的权值,采用哈夫曼算法构造最优二叉树,并用结构数组存储最优二叉树。例如,给定字符集合{a,b,c,d}及其权值2、7、4、5,可构造如图5
阅读以下预备知识、函数说明和C代码,将应填入(n)处的字句写在对应栏内。 【预备知识】 ①对给定的字符集合及相应的权值,采用哈夫曼算法构造最优二叉树,并用结构数组存储最优二叉树。例如,给定字符集合{a,b,c,d}及其权值2、7、4、5,可构造如图5
admin
2009-05-15
48
问题
阅读以下预备知识、函数说明和C代码,将应填入(n)处的字句写在对应栏内。
【预备知识】
①对给定的字符集合及相应的权值,采用哈夫曼算法构造最优二叉树,并用结构数组存储最优二叉树。例如,给定字符集合{a,b,c,d}及其权值2、7、4、5,可构造如图5-6所示的最优二叉树和相应的结构数组Ht(数组元素Ht[0]不用)。
结构数组Ht的类型定义如下:
#define MAXLEAFNUM 20
struct node{
char ch; /*当前节点表示的字符,对于非叶子节点,此域不用*/
int weight; /*当前节点的权值*/
int parent; /*当前节点的父节点的下标,为0时表示无父节点*/
int lchild,rchild;
/*当前节点的左、右孩子节点的下标,为0时表示无对应的孩子节点*/
}Ht[2*MAXLEAFNUM];
②用“0”或“1”标识最优二叉树中分支的规则是:从一个节点进入其左(右)孩子节点,就用“0”(“1”)标识该分支(示例见图5-6)。
③若用上述规则标识最优二叉树的每条分支后,从根节点开始到叶子节点为止,按经过分支的次序,将相应标识依次排列,可得到由“0”、“1”组成的一个序列,称此序列为该叶子节点的前缀编码。例如图5-6所示的叶子节点a、b、c、d的前缀编码分别是110、0、111、10。
【函数5-6说明】
函数void LeafCode(int root,int n)的功能是:采用非递归方法,遍历最优二叉树的全部叶子节点,为所有的叶子节点构造前缀编码。其中形参root为最优二叉树的根节点下标,形参n为叶子节点个数。
在构造过程中,将Ht[P].weight域用做被遍历节点的遍历状态标志。
【函数5-6】
char **Hc;
void LeafCode(int root, int n)
/*为最优二叉树中的n个叶子节点构造前缀编码,root是树的根节点下标*/
{
int i,p=root,cdlen=0;
char code[20];
Hc=(char**)maloc((n+1)*sizeof(char*)); /*申请字符指针数组*/
for(i=1;i<=p;++i)
Ht
.weight=0; /*遍历最优二叉树时用做被遍历节点的状态标志*/
while(p){ /*以非递归方法遍历最优二叉树,求树中每个叶子节点的编码*/
if(Ht[p].weight==0){/*向左*/
Ht[p].weight=1;
if(Ht[p].lchild !=0){
p=Ht[p].lchild;
code[cdlen++]=’0’;
}else if(Ht[p].rchild==0){ /*若是叶子节点,则保存其前缀编码*/
Hc[p]=(char *)malloc((cdlen+1)*sizeof(char));
(1);
strcpy(Hc[p],code);
}
}else if(Ht[p].weight==1)(/*向右*/
Ht[p].weight=2;
if(Ht[p].rchild !=0){
p=Ht[p].rchild;
code[edlen++]=’1’;
}
}else { /*Ht[p].weight==2,回退*/
Ht[p].weight=0;
p=(2);
(3); /*退回父节点*/
}
}/*while结束*/
}
【函数5-7说明】
函数void Decode(char *buff,int root)的功能是:将前缀编码序列翻译成叶子节点的字符序列,并输出。其中形参root为最优二叉树的根节点下标,形参buff指向前缀编码序列。
【函数5-7】
void Decode(char *buff,int root)
{
int pre=root,p;
while(*buff !=’\0’){
p=root;
while(p !=0){/* 存在下标为p的节点*/
pre=p;
if((4))p=Ht[p].lchild; /*进入左子树*/
else p=Ht[p].rchild; /*进入右子树*/
buff++; /*指向前缀编码序列的下一个字符*/
}
(5);
printf("%c",Ht[pre].ch);
}
}
选项
答案
(1) [cdlen]=’\0’或code[cdlen]=0 (2) Ht[p].parent (3) --cdlen或等价形式 (4) *buff==’0’或等价形式 (5) buff--或等价形式
解析
本题考查Huffman树最优前缀码的编码和译码。
函数5-6是用来为Huffman树的每个叶节点构造最优前缀码的,根据说明,实际上就是求从根节点到各叶节点的路径。程序对Huffman树进行前序遍历,将路径记录在code数组中,每碰到一个叶节点就输出从根节点到该叶节点的路径,即该叶节点的最优前缀码。
构造前缀码过程中,Ht
.weight用做被遍历节点的遍历状态:为0表示节点i未被遍历过; 1表示已经被遍历过;2表示位于i节点的分支都被遍历,下步该遍历i节点的兄弟节点分支。故while语句下的3个if语句很明显分别对应这3种情况。
第一个if语句中,如果i节点没有被遍历过(Ht
.weight为0),则应该先考查其是否有左子节点,有的话就表示其还不是叶节点,则下一个被遍历的节点为其左节点,同时将“0”字符保存到code数组中。如果没有左节点且没有右节点,表示其为叶节点,保存该路径。空 (1)之后的strcpy就是实现字符串拷贝,而字符串结束标志是“\0”,因此空(1)应填“code[cdlen]=’\0’”。这点在实际编程时亦需要特别注意。
第二个if语句中,考查Ht
.weight等于1的情况,如果成立则表示i节点被遍历过(即已考查了其左节点),如果该节点没有右节点(Ht
.rchild为0),应该回退到它的父节点,求下一个叶节点的编码;否则,记录字符“1”,继续遍历其右子树。
第三个if语句为回退到父节点,即指针p应指向i节点的父节点,同时路径存储数组code也应该回退一个字符(特别注意这一点)。故空(2)应填“Ht
.parent”,空(3)应填“--cdlen”。
函数Decode的功能是将前缀码序列翻译成叶子节点的字符序列并输出。根据前缀编码在 Huffman树中表示的意义,程序依次扫描前缀码序列,根据扫描到的编码值遍历Huffman树:为0往左子树继续扫描,为1往右子树扫描。据注释,空(4)是进入左子树的条件,应该为“*buff==0”。
空(5)有比较大的难度。仔细分析while循环,会发现当while循环结束时,buff已经指向下一个叶子节点编码的第二个字符了。故空(5)应将编码字符指针回退一个字符,即应填“buff--”。
转载请注明原文地址:https://kaotiyun.com/show/I5xZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
在OSI网络管理标准中定义了网络管理的5大功能。对历史数据进行分析、统计和整理,为未来的网络规划提供参考的功能属于(41);提供一系列实时数据采集、分析和可视化工具对流程、负载、丢包、温度、内存、延迟等网络设备和线路进行实时检测的功能属于(42);接收报警
每个盘块512字节的目录文件存放在某一磁盘上,其中文件控制块占64B(文件名占用8B)。若采用“文件控制块分解法”将文件控制块分解成两部分,第一部分占10字节(包括文件名和文件内部号),第二部分占56字节(包括文件内部号和文件其他描述信息)。那么对于一个共
国际标准化组织制定的OSI网络管理协议是(36),另外,ISO还定义了5个管理功能域,(37)属于性能管理域。IAB制定的网络管理协议是SNMP,在SNMP管理框架中使用的管理信息库为(38)。管理站(Manager)通过GetRequest命令查询代理(
TCP是一个面向连接的协议,它提供连接的功能是(31)的,采用(32)来实现可靠数据流的传送。为了提高效率,又引入了滑动窗口协议,协议规定重传(33)的分组,这种分组的数量最多可以(34),TCP协议采用滑动窗口协议解决了(35)。
TCP是互联网中的(6)协议,使用(7)次握手协议建立连接。当主动方发出SYN连接请求后,等待对方回答(8)。这种建立连接的方法可以防止(9)。TCP使用的流量控制协议是(10)。
PriortotheavailabilityofenterpriseEDM,locatingadocumentoveraLANcouldbedifficult,andoveraWAN(66)nearlyimpossi
下列复用方式中,(112)是光纤通信中使用的复用方式,EI载波把32个信道按(113)方式复用在一条2.048Mb/s的高速信道上,每条话音信道的数据速率是(114)。
UML提供了一系列的图支持面向对象的分析与设计,其中(13)给出系统的静态设计视图;(14)对系统的行为进行组织和建模是非常重要的;(15)和(16)都是描述系统动态视图的交互图,其中(15)描述了以时间顺序组织的对象之间的交互活动,(16)强调收发消息的
Routingincircuit-switchingnetworkshastraditionallyinvolvedastaticroutingstrategywiththeuseof(1)pathstorespond
Routingincircuit-switchingnetworkshastraditionallyinvolvedastaticroutingstrategywiththeuseof(1)pathstorespond
随机试题
杵状指可见于
单剂量固体制剂含量均匀度的检查是为了
患者素有胃痛,近日因情志不遂而加重,现症见胃脘胀痛,痛连胁肋,嗳气后胃部胀痛可减轻,食欲不振,舌红苔薄白,脉弦。按照中医五行学说,与胃相对应的是()
下列有关公海上的管辖权,哪个选项正确?()
运用观测分析法估测设备的有形损耗率时需考虑的主要因素有()。
根据《建设工程安全生产管理条例》的规定,注册执业人员未执行法律、法规和工程建设强制性标准的,情节严重的,吊销执业资格证书,( )年内不予注册,造成重大安全事故的,终身不予注册。
青岛某服装厂以CIF成交价格从美国购进一批缝编机,发票列明:缝编机USD20000,进口后的安装费USD1000,培训费USD1000,卖方佣金USD500,经海关审查上述成交价格属实,请问该缝编机海关审定的完税价格应是;
采矿、煤炭、石油等资源开发业,多年来一直是我国重点扶植的产业,这对于一定时期内振兴国民经济和实现经济资助是有积极意义的。但是,由于资源开发缺乏中长期整体规划,采矿、煤炭、石油等部门只知道单纯地增加年度产量,忽略了资源的合理利用,从而导致资源枯竭已见端倪,同
把下面的六个图形分为两类,使每一类图形都有各自的共同特征或规律,分类正确的一项是:
皇姑屯事件
最新回复
(
0
)