首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码,将应填入(n)处的字句写在答题纸对应栏内。 【说明】 Huffman树又称最优二叉树,是一类带权路径长度最短的树,在编码中应用比较广泛。 构造最优二叉树的Huffman算法如下: ①根据给定的n各权值{w1,w2,…,wn}构成
阅读下列函数说明和C代码,将应填入(n)处的字句写在答题纸对应栏内。 【说明】 Huffman树又称最优二叉树,是一类带权路径长度最短的树,在编码中应用比较广泛。 构造最优二叉树的Huffman算法如下: ①根据给定的n各权值{w1,w2,…,wn}构成
admin
2014-10-11
73
问题
阅读下列函数说明和C代码,将应填入(n)处的字句写在答题纸对应栏内。
【说明】
Huffman树又称最优二叉树,是一类带权路径长度最短的树,在编码中应用比较广泛。
构造最优二叉树的Huffman算法如下:
①根据给定的n各权值{w
1
,w
2
,…,w
n
}构成n棵二叉树的集合F={T
1
,T
2
,…,T
n
},其中每棵树T
i
中只有一个带权为w
i
的根节点,其左右子树均空。②在F中选取两棵根节点的权值较小的树作为左右子树,构造一棵新的二叉树,置新构造二叉树的根节点的权值为其左右子树根节点的权值之和。③从F中删除这两棵树,同时将新得到的二叉树加入到F中。重复②③,直到F中只剩一棵树为止。函数中使用的预定义符号如下:
#detineINT—MAX 10000
#define ENCODING—LENGTH 1000
typedef enum(rlone, 1eft一child, right一child) which;
/*标记是左孩子还是右孩子*/
typedef char Elemtype;
typedef struct TNode{//Huffman树节点
Elemtype letter;
int weight; //权值
int parent; //父节点
Which Sigh;
char*code; //节点对应编码
)HTNode,*HuffmanTree;
int n;
char coding[50];//储存代码
【函数】
void Select(HuffmanTree HT,int end,int*s1,int*s2)
/*在0~END之问,找出最小和次小的两个节点序号,返回s1、s2*/
{
int i;
int mini=INT_MAX;
int min2=INT_MAX;
for(i=0;i<=end;i++){/*找最小的节点序号*/
if((1)&&(HT
.weight
*s1=i;
minl=HT
.weight;
}
}
for(i=0;i<=end;i++){/*找次小节点的序号*/
i f((HT
.parent==0)&&((2))
&&(min2 >HT
.weight)){
*S2:i;
min2=HT
.weight:
}
}
}
void HuffmanTreecrea七(HuffmanTree&HT)/*建立HuFFMAN树*/
{
int i;
int m=2*n一1;
int S1,S2;
for(i=n;i
Select((3));
HT[S1].parent=i:
HT[s2].parent=i;
HT[S1].Sigh=1eft_chiid;
HT[s2].Sigh=right—chiid;
HT
.weight= (4);
}
void HuffmanTreeEnc。ding(char sen[],HuffmanTree HT)
{ /*将句子进行编码*/
int i=0;
int j;
while(sen
!=’\0’){
for(J=0;j
i f(HT[j].1etter==sen
)(/*字母匹配则用代码取代*/
strcat(coding, (5));
break;
}
}
i++:
if(sen
==32)i++;
printf(“\n%s”,coding);
}
选项
答案
(1)HT[i].parent==0 (2)*s1!=i (3)HT,i—1,&s1,&s2 (4)HT[s1].weight+HTIs2].weight (5)HT[j].code
解析
根据算法说明的②可知是根据根节点权值选择,即只考察根节点,而根节点对应~parent等于0,故空(1)应填HT
.parent=0。此答案可由空(2)处的i涤件容易得出。至于空(2),此处是找次小的,自然需要排除最小的,S1记录了最小树的下标,故填*s1!=i。仔细参照Select~数的定义,容易得出空(3)答案。应填“HT,i—l,&sl,&s2”,要注意的是后两个参数需要传递地址,因形参是指针。根据算法说明的②,“置新构造二叉树的根节点的权值为其左右子树根节点的权值之和”,而此处HT
的左右子树的根节点分别为HT[s1]和NHT[s2],所以空(4)应填HT[s1].weight+HT[s2].weight。由注释“字母匹配则用代码取代”可知,此处是将对应代码加到coding中,而节点的code字段存储了节点对应编码,故空(5)应填HT[j].code。
转载请注明原文地址:https://kaotiyun.com/show/NaDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
在分层体系结构中,控制层接收用户的请求并决定调用哪个模型去处理该请求,以及确定选择哪个视图来显示返回的数据。在基于JavaEE平台开发的软件系统中,常用_________技术来实现该层。
以下不属于在需求分析阶段编写的文档是
以下描述中,属于通用操作系统基本功能的是_______。
在应用服务器关机的情况下,公司员工能连接上因特网吗?简要解释。假设采用ISDN基本速率接口,下载1875KB的文件,最快需要多长时间?
造成故障1的原因是什么?如何解决?1.路由器2上采用了NAT技术。NAT中的动态地址翻译和IP地址伪装有什么区别?2.图4-2是路由器2上的地址伪装表,将图4-2中(1)~(5)处空缺的信息填写在相应位置。
同一个VLAN中的成员可以形成一个广播域,从而实现何种功能?使Switch1的千兆端口允许所有VLAN通过的配置命令如下,请给出空白处的配置内容:Switchl(config)#interfacegigabit0/1(进入千兆端口配置模式)
阅读下列说明,回答问题1至问题6。[说明]某公司的业务员甲与客户乙通过Internet交换商业电子邮件(以下简称为“邮件”)。为保障邮件内容的安全,双方约定采用安全电子邮件技术对邮件内容进行加密和数字签名。安全电子邮件技术的实现原理如图4
阅读以下说明,回答问题1至问题8。[说明]Linux系统开机引导时首先启动内核,由内核检查和初始化硬件设备,载入设备的驱动程序模块,安装root文件系统,然后内核将启动一个名为init的进程。在init运行完成并启动其他必要的后续进程后,
某交换机的配置命令如下,根据命令后面的注释,填写(1)~(3)处的空缺内容,完成配置命令。Switch(config)#(1)//将交换机命名为Sw1Swl(config)#interfacevlan1Swl(config
阅读以下说明,回答问题l和问题2,将解答填入答题纸对应的解答栏内。【说明】某公司有3个分支机构,网络拓扑结构及地址分配如图4.1所示。在R1、R2和R3之间运行OSPF路由协议,其中R1、R2和R3的配置如下。行号配置代码1
随机试题
Sincewelivenearthesea,weenjoyahealthyclimate.
该患者最可能的诊断是术后应定期进行下列哪项处理
不属于正常前列腺液可见成分的是
胸部高千伏摄影片的主要优点是
某县张某系艾滋病患者,在市里传染病医院隔离治疗期间,擅自进出医院回到某县,脱离隔离治疗,为防止艾滋病传播,可以协助传染病医院追回张某采取强制隔离治疗的是
某施工单位中标承担了一副井井筒工程,该副井井筒净直径5m,掘进荒径6~7m,井筒深度720m,两侧马头门各施工20m,包含相关设备基础,管子道开口施工5m,该项目合同工期12个月,自签订合同之日起算,井筒平均进尺85m/月。井筒施工工期合同签订之后,项目经
如果检验检疫机构需要对出境货物实施检验检疫时,报检员应按要求配合施检,在机构()递交报检单和随附单据。
(2010—单选—9)在开辟新航路的过程中,由欧洲向东绕过非洲到达亚洲的是()。
主题统觉测验属于()
Thepossibilitythattheexplosionwascausedbysabotagecannotbe______.
最新回复
(
0
)