首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下预备知识、函数说明和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
51
问题
阅读以下预备知识、函数说明和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)。
在局域网中,常用的介质访问控制方法CSMA/CD、令牌总线和令牌环,IEEE802.4标准采用(16)媒体访问控制方法,IEEE802.5标准采用(17)媒体访问控制方法。其中(18)介质访问控制方法对最短帧长度有要求。假设这种网络的传输速率为10Mbi
IPv6是下一代IP协议,其基本报头中的(61)字段指明了一个特定的信源向某个特定信宿发送的分组序列,各个中间路由器要对该分组序列进行特殊处理以满足应用程序的特殊传输需求。
TCP是互联网中的(6)协议,使用(7)次握手协议建立连接。当主动方发出SYN连接请求后,等待对方回答(8)。这种建立连接的方法可以防止(9)。TCP使用的流量控制协议是(10)。
WhiletheInternetisinherentlyinsecure,businessesstillneedtopreservetheprivacyofdataasittravelsoverthenetwork.
Networkmanagershavelongawaitedpracticalvoice-over-IP(VOIP)solutions.VOIPpromiseseasenetworkmanagementanddecreases(6
在分布式数据库的类型中,网络中有一个中心站,在这个站点上存放着所有的数据,这种类型是(56)。
程序的(39)理论是虚拟存储管理系统的基础。根据这个理论,Denning又提出了工作集理论。工作集是进程运行时被频繁地访问的页面集合。在进程运行时,如果它的工作集页面都在(40)内,能够使该进程有效地运行,否则会出现频繁的页面调入/调出现象。
IEEE802.11定义了无线局域网的两种工作模式,其中(45)模式是一种点对点连接的网络,不需要无线接入点和有线网络的支持,用无线网卡连接的设备之间可以直接进行通信。IEEE802.11的物理层规定了三种传输技术,即红外技术、直接序列扩频(DSSS)
Networkscanbeinterconnectedbydifferentdevices.Inthephysicallayer,networkscanbeconnectedby(66)orHubs,whichjustmo
随机试题
患者,男性,25岁。因肾病综合征入院。查体:无贫血,肾功能正常,有严重低蛋白血症和高度水肿,尿圆盘电泳示高分子蛋白尿。下列哪个治疗方案是错误的
男性,55岁,确诊为心绞痛型冠心病来住院。该患者应具有以下哪组症状
医嘱:洋地黄0.1mg,qod,p.o.,正常执行时间为:
当煤气管道与氧气管等助燃气体管共架时,其最小净距应为()mm。
符合下列()条件的场所,不宜选择火焰探测器。
根据《建立相对独立的平面坐标系统管理办法》,下列关于相对独立的平面坐标系统的说法中,正确的是()。
投资效益包括()
下列各项中,不属于原始凭证的有( )。
根据《公司法》的规定,下列关于公司章程效力及修改程序的说法中,正确的是()。(2014年)
趋同进化:指不同生物物种在进化过程中由于适应相似的环境而呈现出外形上的相似性。下列属于趋同进化的是()。
最新回复
(
0
)