首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C代码,将应填入(n)处的字句写在对应栏内。 [说明] HufTman树又称最优二叉树,是一类带权路径长度最短的树,在编码中应用比较广泛。 构造最优二叉树的Huffman算法如下: ①根据给定的n各权值{W
阅读下列函数说明和C代码,将应填入(n)处的字句写在对应栏内。 [说明] HufTman树又称最优二叉树,是一类带权路径长度最短的树,在编码中应用比较广泛。 构造最优二叉树的Huffman算法如下: ①根据给定的n各权值{W
admin
2010-12-17
70
问题
阅读下列函数说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
通过遍历用例的路径上基本流和备选流的黑盒测试方法是________________。
以下关于软件项目工作量估算的叙述中,不正确的是________________。
风险控制不包括______。
设数组a[1..n,1..m](n>1,m>1)中的元素以行为主序存放,每个元素占用1个存储单元,则数组元素a[i,j](1≤i≤n,1≤j≤m)相对于数组空间首地址的偏移量为()。
假设系统采用PV操作实现进程同步与互斥。若n个进程共享两台打印机,那么信号量S的取值范围为()。
测试用例是测试使用的文档化的细则,其规定如何对软件某项功能或功能组合进行测试。测试用例应包括下列(32)内容的详细信息。①测试目标和被测功能。②测试环境和其他条件。③测试数据和测试步骤。④测试记录和测试结果。
若计算机存储数据采用的是双符号位(00表示正号、11表示负号),两个符号相同的数相加时,如果运算结果的两个符号位经()运算得1,则可断定这两个数相加的结果产生了溢出。
函数t()、f()的定义如下所示。若调用函数t()时传递给x的值为3,并且调用函数f()时,第一个参数采用传值(call by value)方式,第二个参数采用传引用(call by reference)方式,则函数t0的返回值为(33).
静态图像压缩标准JPEG2000中使用的是(60)算法。
“<titlestyle="italic">science</title>”是XML中一个元素的定义,其中元素的内容是(29)。
随机试题
中国对外政策的宗旨是()
统计中的集中趋势指标是反映资料的
把“人命至重,有贵千金”作为从医的基本准则的是我国名医
下列各项,属于企业会计核算具体内容的有( )。
科学家发明的透明坚硬的镁铝氧化物新型材料,可以用作显示器和手机屏幕。下列有关镁和铝的说法正确的是()。
若{an}是公差d不为0的等差数列,且a1=7d,ai为a1与a22的等比中项,则i=().
Methodsofstudyingvary:whatworks【C1】______forsomestudentsdoesn’tworkatallforothers.Theonlythingyoucandoisexp
扩展名为mpr的文件是( )。
Whatisthereintheshop?
A、正确B、错误B词义理解题。根据原文Aleaderdoesnotnecessarilyoccupyaformalleadershipposition可知,领导未必占据正式的领导职位。由此可见,题干认为领导必须拥有领导职位与原文意思不
最新回复
(
0
)