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

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

admin2010-12-17  43
问题 阅读下列函数说明和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

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

软考中级

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