首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码,将应填入(n)处的字句写在对应栏内。 [说明] HufTman树又称最优二叉树,是一类带权路径长度最短的树,在编码中应用比较广泛。 构造最优二叉树的Huffman算法如下: ①根据给定的n各权值{W
阅读下列函数说明和C代码,将应填入(n)处的字句写在对应栏内。 [说明] HufTman树又称最优二叉树,是一类带权路径长度最短的树,在编码中应用比较广泛。 构造最优二叉树的Huffman算法如下: ①根据给定的n各权值{W
admin
2010-12-17
63
问题
阅读下列函数说明和C代码,将应填入(n)处的字句写在对应栏内。
[说明]
HufTman树又称最优二叉树,是一类带权路径长度最短的树,在编码中应用比较广泛。
构造最优二叉树的Huffman算法如下:
①根据给定的n各权值{W1,w2,…,wn)构成n棵二叉树的集合F={T1,T2,…,Tn},其中每棵树Ti中只有一个带权为wi的根节点,其左右子树均空。
②在F中选取两棵根节点的权值较小的树作为左右子树,构造一棵新的二叉树,置新构造二叉树的根节点的权值为其左右予树根节点的权值之和。
③从F中删除这两棵树,同时将新得到的二叉树加入到F中。
重复②③,直到F中只剩一棵树为止。
函数中使用的预定义符号如下:
#define INT MAX 10000
#define ENCODING LENGTH 1000
typedef enum(none,left_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 *sl,int *s2)
/*在0~END之间,找出最小和次小的两个节点序号,返吲S1、S2*/
{
int i;
int min 1=INT_MAX;
int min 2=INT_MAX;
for(i=0;i<=end;i++){/*找最小的节点序号*/
if(( (1) )&&(HT
.weight<minl)){
*s1=i;
min 1=HT
.weight;
}
}
for(i=0;i<=end;i++){/*找次小节点的序号*/
if((HT
.parent==0)&&( (2) )
&&(min 2>HT
.weight)){
*s2=i;
min 2=HT
.weight;
}
}
}
void HuffmanTreeCreat(HuffmanTree&HT)/*建立HUFFMAN树*/
{
int i;
int m=2*n-1;
int s1,s2;
for(i=n;i<m;i++){
Select( (3) );
HT[s1].parent=i;
HT[s2].parent=i;
HT[s1].sigh=left child;
HT[s2].sigh=right child;
HT
.weight=(4);
}
}
void HuffmanTreeEncoding(char sen[],HuffmanTree HT)
{ /*将句子进行编码*/
int i=0;
int j;
while(sen
!=’\0’){
for(j=0;j<n;j++){
if(HT[j].letter==sen
)(/*字母吻合则用代码取代*/
strcat(coding, (5) );
break;
}
}
i++;
if (Sen [1]==32) i++;
}
printf("\n%s",coding);
}
(5)
选项
答案
HT[j].code
解析
根据算法说明的②可知是根据根节点权值选择,即只考察根节点,而根节点对应的parent等于0,故空(1)应填HT
.parent==0。此答案可由空(2)处的if条件容易得出。
至于空(2),此处是找次小的,自然需要排除最小的,sl记录了最小树的下标,故填*s1 !=i。
仔细参照Select函数的定义,容易得出空(3)答案。应填“HT,i-1,&s1,&s2”,要注意的是后两个参数需要传递地址,因形参是指针。
根据算法说明的②,“置新构造二又树的根节点的权值为其左右子树根节点的权值之和”,而此处HT
的左右子树的根节点分别为HT[s1]和HT[s2],所以空(4)应填HT[s1].weight+HT[s2].weight。
由注释“字母吻合则用代码取代”可知,此处是将对应代码加到coding中,而节点的code字段存储了节点对应编码,故空(5)应填HT[j].code。
转载请注明原文地址:https://kaotiyun.com/show/5qDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
某软件项目的活动图如下图所示,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,边上的数字表示活动的持续时间(天),则完成该项目的最少时间为________________天。活动FG的松弛时间为________________天。
以下不属于易用性测试的是(69)________________。
以下关于设计功能测试用例的叙述,______是不正确的。A.尽量用80%测试用例覆盖20%的核心业务模块B.功能测试用例中不包括功能的依从性测试用例C.功能测试用例中包括业务流,也包括测试数据D.功能测试用例的设计应注意缺陷群集现象
堆是一种数据结构,分为大顶堆和小顶堆两种类型。大(小)顶堆要求父元素大于等于(小于等于)其左右孩子元素。则________________是一个小顶堆结构。堆结构用二叉树表示,则适宜的二叉树类型为________________。对于10个结点的小顶堆,其
某应用系统采用防火墙技术来实现安全防护,在进行安全防护测试时,设计的测试点不包括______。
软件可靠性是指在指定的条件下使用时,软件产品维持规定的性能级别的能力,其子特性(51)是指在软件发生故障或者违反指定接口的情况下,软件产品维持规定的性能级别的能力。
针对下列程序段,对于(A,B,C)的取值,以下(56)测试用例组合能够满足语句覆盖的要求。IF((A+10)=2OR(B-20)<3)THENC=0IF((A+30)=10AND(C-30)<0)THENB=30
静态图像压缩标准JPEG2000中使用的是(60)算法。
通常一个HFC网络由前端(FE)、主数字终端(HDT)、光纤节点(FN)、网络接口单元(NIU)、综合业务单元(ISU)及传输线路等构成。根据HFC网接入Internet网的典型配置,将图6-12所示的拓扑图中(A)~(D)空缺处的名称填写完整(请使用题干
阅读以下说明,回答以下问题,将解答填入答题纸对应的解答栏内。【说明】某学校有三个校区,校区之间最远距离达到61km,学校现在需要建设校园网,具体要求如下:校园网通过多运营商接入互联网,主干网采用千兆以太网将使每个校区的中心节点连起来,每
随机试题
请简单介绍20世纪30年代报告文学的兴盛。
可撤销合同自人民法院决定撤销之日起没有法律效力。()
根据承租人的授权和指示,代表承租人利益在租船市场上为承租人洽租合适船舶的人称为()
定期考核不合格的医师暂停执业活动期满,再次考核仍不合格的
根据合同法律制度的规定,由于债权人的原因,债务人无法向债权人交付合同标的物时,可以将该标的物交给提存部门,从而消灭债务,在标的物提存后,标的物毁损、灭失风险责任的承担者是()。
(2009年)两个平行的无限大灰体表面1和表面2,温度分别为T1和T2,发射率均为0.8。若在中间平行插入一块极薄的、发射率为0.4的金属板,则表面1和表面2之间换热量变为原来的()。
下列选项中不正确的是()。
某单位出纳员张某6月10日经办了三项业务:①收到单位从外地购物的发票,发现发票金额为30000元,实际支付金额为25000元,两者不一致,便在发票上做了更改,并加盖了自己的印章,作为报销凭证。②销售给外单位的商品发生退回,经单位领导批准,同意退款1
《中华人民共和国对外贸易法》的基本原则是什么?
Theprizesinthegames______ofmedalsanddiplomas.
最新回复
(
0
)