首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码,将应填入(n)处的字句写在对应栏内。 [说明] HufTman树又称最优二叉树,是一类带权路径长度最短的树,在编码中应用比较广泛。 构造最优二叉树的Huffman算法如下: ①根据给定的n各权值{W
阅读下列函数说明和C代码,将应填入(n)处的字句写在对应栏内。 [说明] HufTman树又称最优二叉树,是一类带权路径长度最短的树,在编码中应用比较广泛。 构造最优二叉树的Huffman算法如下: ①根据给定的n各权值{W
admin
2010-12-17
34
问题
阅读下列函数说明和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://jikaoti.com/ti/c4i7FFFM
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
对于逻辑表达式(((a|b)‖(c>2))&&d<0),需要________________个测试用例才能完成条件组合覆盖。
下图所示的二叉树进行顺序存储(根结点编号为1,对于编号为i的结点,其左孩子结点为2i,右孩子结点为2i+1)并用一维数组BT来表示,已知结点X、E和D在数组BT中的下标为分别为1、2、3,可推出结点G、K和H在数组BT中的下标分别为____________
在指令系统的各种寻址方式中,获取操作数最快的方式是________________。
下面关于软件测试的说法,(48)是错误的。
系统功能测试过程中,验证需求可以正确实现的测试用例称为(32)。
某开发小组欲开发一个大型软件系统,需求变化较小,此时最不适宜采用()过程模型。
某应用系统采用防火墙技术来实现安全防护,在进行安全防护测试时,设计的测试点不包括______。
(1)不属于计算机控制器中的部件。
函数t()、f()的定义如下所示。若调用函数t()时传递给x的值为3,并且调用函数f()时,第一个参数采用传值(call by value)方式,第二个参数采用传引用(call by reference)方式,则函数t0的返回值为(33).
静态图像压缩标准JPEG2000中使用的是(60)算法。
随机试题
与COPD发生关系最密切的是
基因工程中实现目的基因与载体DNA共价拼接的酶是
A、葱B、白萝卜C、鳖肉D、醋E、萸菜人参忌
红天房地产开发公司为开发A楼盘与乙银行签订贷款合同,贷款金额1000万元,并以该开发的楼盘设定抵押担保。红天公司又与蓝天工程公司签订工程合同,由蓝天工程公司承建A楼盘。红天公司为提前收回成本,将该房预售给众客户,并签订了商品房预售合同。众客户有的支付了主要
美国佐治亚州亚特兰大市公民安娜认为,其州议会颁布的关于禁止黑人进入白人学校学习的法律违反宪法的“平等保护”条款。根据美国法律,安娜应该向下列哪一法院起诉?()
土坝坝身控制测量包括()。
国外的老客户向你要求寄送一般丝绸面料样品,量不多但要求快速,你会怎样寄送样品和处理样品寄送的费用()
甲向乙借款,丙与乙约定,丙以其名下的房屋提供贷款担保。丙仅将房产证交付乙,此后以种种理由推脱拒绝前往登记机关办理登记。借款到期后,甲无力清偿,丙的房屋被法院另行查封。下列表述正确的是哪些?()
[*]
PASSAGETHREEWhydoesTNTprovideemergencyhelpandknowledgetransfer?
最新回复
(
0
)