2. 计算机
  3. 阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸对应栏内。 【说明】 Huffman树又称最优二叉树，是一类带权路径长度最短的树，在编码中应用比较广泛。 构造最优二叉树的Huffman算法如下： ①根据给定的n各权值{w1，w2，…，wn}构成

阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸对应栏内。 【说明】 Huffman树又称最优二叉树，是一类带权路径长度最短的树，在编码中应用比较广泛。 构造最优二叉树的Huffman算法如下： ①根据给定的n各权值{w1，w2，…，wn}构成

admin2014-10-11  72
问题 阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸对应栏内。

【说明】
Huffman树又称最优二叉树，是一类带权路径长度最短的树，在编码中应用比较广泛。
构造最优二叉树的Huffman算法如下：
①根据给定的n各权值{w1，w2，…，wn}构成n棵二叉树的集合F={T1，T2，…，Tn}，其中每棵树Ti中只有一个带权为wi的根节点，其左右子树均空。②在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;iSelect((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;ji 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

软件设计师下午应用技术考试

软考中级

相关试题推荐
随机试题
最新回复(0)