2. 计算机
  3. 阅读以下说明和C语言函数，将应填入(n)处。 [说明] 二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：若它的左子树非空，则左子树上所有结点的值均小于根结点的值；若它的右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身就是两棵二

阅读以下说明和C语言函数，将应填入(n)处。 [说明] 二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：若它的左子树非空，则左子树上所有结点的值均小于根结点的值；若它的右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身就是两棵二

admin2012-12-10  49
问题 阅读以下说明和C语言函数，将应填入(n)处。
[说明]
   二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：若它的左子树非空，则左子树上所有结点的值均小于根结点的值；若它的右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身就是两棵二义排序树。
    函数insert_BST(char *str)的功能是：对给定的字符序列按照ASCⅡ码值大小关系创建二叉排序树，并返回指向树根结点的指针。序列中重复出现的字符只建一个结点，并由结点中的Count域对字符的重复次数进行计数。
   二叉排序树的链表结点类型定义如下：
    typedef struct BSTNode{
           char Elem;                  /*结点的字符数据*/
           int Count;                  /*记录当前字符在序列中重复出现的次数*/
           struct BSTNode *Lch,*Rch;   /*接点的左、右子树指针*/
   }*BiTree;
[函数]
   BiTree insert_BST(char *str)
   { BiTree root,parent,p;
     char  (1);             /*变量定义及初始化 */
     root=(BiTree)malloc(sizeof(struct BSTNode));
     if(!root||*s==’\0’) return NULL;
     root-＞Lch=root-＞Rch=NULL;  foot-＞Count=1;  root-＞Elem=*s++;
     for(; *s!=’\0’;s++) {
     (2);    parent=NULL;
       while (p){       /*p从树跟结点出发查找当前字符*s所在结点 */
         parent = p;
   if(*s==p-＞Elem)/*若树中已存在当前字符结点，则当前字符的计数值加1*/
   {p-＞Count++;  break;}
        else  /*否则根据字符*s与结点*p中字符的关系，进入*p的左子树或右子树*/
           if (*s＞p-＞Elem)  p=p-＞Rch;
           else   p=p-＞Lch;
      }/*while*/
      if( (3)) {/* 若树中不存在字符值为*s的结点，则申请结点并插入树中 */
         p=(BiTree)malloc(sizeof(struct BSTNode));
         if(!p)return NULL;
   p-＞Lch=p-＞Rch=NULL;   p-＞Count=1;    p-＞Elem=*s;
/*根据当前字符与其父结点字符值的大小关系，将新结点作为左子树或右子树插入*/
          if(p-＞Elem＞parent-＞Elem)    (4)=p;
          else      (5)=p;
       }
     }/*for*/
     return root；
   }
选项
答案(1) *s=str(2) p=root(3) p==NULL (4) parent-＞Rch(5) parent-＞Lch
解析 本题考查二叉排序树在链表存储结构上的运算。
   函数insert_BST(char *str)的功能是对给定的字符序列str按照ASCⅡ码值大小关系创建二叉排序树，并返回指向树根结点的指针，序列中重复出现的字符只建一个结点，并由结点中的Count域对字符的重复次数进行计数。
   根据程序代码中对字符序列中字符的引用情况，可知需要在空(1)处定义字符指针s，其初值应为参数str的值。for语句的作用是对序列中的每个字符*s，用while循环从树根结点出发查找*s所在结点。由于while的条件p为非空指针时循环，因此此前应设置 p的初值，显然空(2)是为p没初值root，从而对每个字符*s都可以从树根出发，开始查找结点。若树中已存在当前字符*s的结点，则*s字符的计数值加1，并结束对该字符的查找过程，若树中不存在*s的结点，则会进入树的一个空子树(以p为空表示)，因此空(3)处应填入“p==NULL”或“中!p”。
   插入新的结点时，需要建立其与父结点的关系，在查找结点的过程中parent表示待插入结点的父结点。因此根据二叉排序树的定义，待插入元素的值大于其父结点的值，则作为右子结点插入，否则作为左子结点插入。所以，空(4)、(5)分别填入parent-＞Rch和parent-＞Lch。
转载请注明原文地址:https://kaotiyun.com/show/RnjZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

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