首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下预备知识、函数说明和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
24
问题
阅读以下预备知识、函数说明和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
软件设计师上午基础知识考试
软考中级
相关试题推荐
FDDI与TokenRing都采用(21)传递协议,在FDDI的令牌帧中有(22),其主要作用是(23)。FDDI在(24)产生新令牌帧,允许在环上同时存在(25)。
为了进行差错控制,必须对传送的数据帧进行校验,由接收方检测数据传输是否出现差错,常用的差错控制方法是(6)。要检测接收的数据是否有错,最常用的方法是(7)。海明码是一种纠错码,采用海明码纠正一位差错,若信息位为7bit,则冗余位至少应为(8),CRC-16
在双绞线布线后要进行测试,一般情况,下面(43)不是测试的项目。光纤测试的内容不包括(44)项目。
国际标准化组织制定的OSI网络管理协议是(36),另外,ISO还定义了5个管理功能域,(37)属于性能管理域。IAB制定的网络管理协议是SNMP,在SNMP管理框架中使用的管理信息库为(38)。管理站(Manager)通过GetRequest命令查询代理(
TCP是互联网中的(6)协议,使用(7)次握手协议建立连接。当主动方发出SYN连接请求后,等待对方回答(8)。这种建立连接的方法可以防止(9)。TCP使用的流量控制协议是(10)。
WhiletheInternetisinherentlyinsecure,businessesstillneedtopreservetheprivacyofdataasittravelsoverthenetwork.
WhiletheInternetisinherentlyinsecure,businessesstillneedtopreservetheprivacyofdataasittravelsoverthenetwork.
Networkscanbeinterconnectedbydifferentdevices.Inthephysicallayer,networkscanbeconnectedby(66)orHubs,whichjust
RS-232-C是目前常见的一种接口标准,它是由(32)提供制定的。该标准在OSI模型中属于(33)层协议标准,通过RS-232-C来连接两个设备最少要连接(34)条线。这个标准的设计数据速率是处理(35)bit/s。(35)bit/s条件下,采用RS-4
Routingprotocolsusedifferenttechniquesforassigning(1)toindividualnetwork.Further,eachroutingprotocolformsametricag
随机试题
急性冠状动脉综合征的病理基础
关于急性中毒下列哪项说法是错误的?()
简支梁受分布荷载作用如图4-15所示。支座A、B的约束力为()。
矿山必须有与外界相通的、符合安全要求的()设施。
村镇银行是指由境内外金融机构、()、境内自然人出资,在农村地区设立的主要为当地农民、农业和农村经济发展提供金融服务的银行业金融机构。
下列关于银行代理黄金业务的说法,错误的是()。
回收站中的内容可以是()。
士官服现役的期限可长可短,当士官具备一定条件时就需要退出现役,根据《中国人民解放军士官退出现役安置暂行办法》,下列关于士官退出现役条件的说法中,正确的有()。
《新华日报》(中国传媒大学2014年研;厦门大学2013年研)
甲公司与乙公司约定:为满足甲公司开发住宅小区景观的需要,甲公司向乙公司支付100万元,乙公司在20年内不得在自己厂区建造6米以上的建筑。甲公司将全部房屋出售后不久,乙公司在自己的厂区建造了一栋高8米的厂房。下列哪一个选项是正确的()。
最新回复
(
0
)