2. 计算机
  3. 阅读以下说明和C函数，将应填入(n)处的字句写在对应栏内。 【说明】 已知某二叉树的非叶子结点都有两个孩子结点，现将该二叉树存储在结构数组Ht中。结点结构及数组Ht的定义如下： #define MAXLEAFNUM 30 struct

阅读以下说明和C函数，将应填入(n)处的字句写在对应栏内。 【说明】 已知某二叉树的非叶子结点都有两个孩子结点，现将该二叉树存储在结构数组Ht中。结点结构及数组Ht的定义如下： #define MAXLEAFNUM 30 struct

admin2009-09-20  60
问题 阅读以下说明和C函数，将应填入(n)处的字句写在对应栏内。
【说明】
   已知某二叉树的非叶子结点都有两个孩子结点，现将该二叉树存储在结构数组Ht中。结点结构及数组Ht的定义如下：
   #define MAXLEAFNUM  30
   struct node{
       char ch;       /*当前结点表示的字符，对于非叶子结点，此域不用*/
       char *pstr;    /*当前结点的编码指针，非叶子结点不用*/
           int parent;    /*当前结点的父结点，为0时表示无父结点*/
       int lchild,rchild;
   /*当前结点的左、右孩子结点，为0时表示无对应的孩子结点*/
   };
   struct node Ht[2*MAXLEAFNUM];    /*数组元素Ht[0]不用*/
   该二叉树的n个叶子结点存储在下标为1～n的Ht数组元素中。例如，某二叉树如果其存储结构如下图所示，其中，与叶子结点a对应的数组元素下标为1，a的父结点存储在Ht[5]，表示为Ht[1].parent=5。Ht[7].parent=0表示7号结点是树根，Ht[7].child=3、Ht[7].rchild=6分别表示7号结点的左孩子是3号结点、右孩子是6号结点。
      
   如果用0或1分别标识二叉树的左分支和右分支(如上图所示)，从根结点开始到叶子结点为止，按所经过分支的次序将相应标识依次排列，可得到一个0、1序列，称之为对应叶子结点的编码。例如，上图中a，b，c，d的编码分别是100，101，0，11。
   函数LeafCode(Ht[],n)的功能是：求解存储在Ht中的二叉树中所有叶子结点(n个)的编码，叶子结点存储在Ht[1]～Ht[n]中，求出的编码存储区由对应的数组元素pstr域指示。
   函数LeafCode从叶子到根逆向求叶子结点的编码。例如，对上图中叶子结点a求编码的过程如下图所示。
      
   typedef enum Status  {ERROR,OK} Status;
【C函数】
Status LeafCode(struct node Ht[],  int n)
{
int pc, pf;  /*pc用于指出树中的结点，pf则指出pc所对应结点的父结点*/
int i,start;
char tstr[31] = {’\0’};   /*临时存储给定叶子结点的编码，从高下标开始存入*/
for(i = 1;(1); i++){ /*对所有叶子结点求编码，i表示叶结点在HT数组中的下标*/
    start = 29;
    pc = i;    pf = Ht.parent;
    while (pf !=(2)) {        /*没有到达树根时，继续求编码*/
        if ((3).lchild == pc ) /*pc所表示的结点是其父结点的左孩子*/
         tstr[--start] = ’0’;
        else
tstr[--start] = ’1’;
pc =(4);  pf = Ht[pf].parent;   /*pc和pf分别向根方向回退一层*/
    }/* end of while */
    Ht.pstr = (char *) malloc(31-start);
    if (!Ht.pstr)   return ERROR;
    strcpy(Ht.pstr,(5));
  }/* end of for */
  return OK;
}/* and of LeafCode */
选项
答案(1) i＜=n，或其等价表示 (2) 0 (3) Ht[pf]，或(*(Ht+pf)) (4) pf (5) &tstr[start]，或tstr+start
解析 本题考查C语言的基本控制结构、数组以及参数传递基础知识。
   哈夫曼算法构造最优二叉树的过程如下。
   (1)根据给定的n个权值{W1，W2，…，Wn}构成n棵二叉树的集合F={T1，T2，…， Tn}，其中每棵二叉树Ti中只有一个带权为Wi的根结点，其左、右子树均空。
   (2)在F中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树，且置新二叉树的根结点的权值为其左、右子树根结点的权值之和。
   (3)在F中删除这两棵二叉树，同时将新得到的二叉树加入F中。
   (4)重复(2)和(3)，直到F只含一棵树为止。这棵树便是最优二叉树。
   最优二叉树是从叶子到根构造起来的，每次都是先确定一棵二叉树的左、右子树，然后再构造出树根结点，因此，最优二叉树中只有叶子结点和分支数为2的内部结点。若已知叶子的数目为n，则内部结点数比叶子少1，因此，整棵树所需的存储空间规模是确定的，可以采用数组空间来存储最优二叉树。
   题目中已经指出该二叉树的n个叶子结点存储在下标为1～n的Ht数组元素中，同时举例说明父结点编号为0的结点式树根结点。因此，空(1)处应填入“i＜=n”。同时，除了根结点之外，每个结点都有唯一的父结点，因此到达树根的标志为结点的父结点编号为0，因此，空(2)处应填入“0”。
   根据代码中pc和pf的作用：pc用于指出树中的结点，pf则指出pc所对应结点的父结点，则空(3)处应填入“Ht[pf]”，空(4)处填入“pf”使得pc回退至其父结点位置。
   空(5)考查了标准函数的调用，对于函数strcpy()，其原型为char* strcpy (char*,const char*)。两个参数都是字符指针，根据代码中tstr的作用，应将tstr+start(tstr[start]～tstr[29]存放编码)作为实参调用strcpy，因此空(5)处应填入“tstr+start”或“&tstr[start]”。
转载请注明原文地址:https://kaotiyun.com/show/xIjZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

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