软题库 移动APP 扫码下载APP 随时随地移动学习 培训课程
当前位置:信管网 >> 在线考试中心 >> 信息系统项目管理师题库 >> 试题查看
试卷名称 2012年下半年程序员考试下午真题试题(案例分析)
考试中心《2012年下半年程序员考试下午真题试题(案例分析)》在线考试
试卷年份2012年下半年
试题题型【分析简答题】
试题内容

阅读以下说明和C函数,填充函数中的空缺,将解答填入答题纸的对应栏内。
【说明】
函数Insert_key(*root ,key)的功能是将键值 key 插入到*boot指向根结点的二叉查找树中(二叉查找树为空时 *root 为空指针)。若给定的二叉查找树中已经包含键值为 key 的结点,则不进行插入操作井返回 0;否则申请新结点、存入 key 的值并将新结点加入树中,返回1。
提示:
二叉查找树又称为二叉排序树,它或者是一棵空树,或者是具有如下性质的二叉树:
若它的左子树非空,则其左子树上所有结点的键值均小于根结点的键值;
若它的右子树非空,则其右子树上所有结点的键值均大于根结点的键值;
左、右子树本身就是二叉查找树。
设二叉查找树采用二叉链表存储结构,链表结点类型定义如下:
Typedef struct BiTnode{
int    key_value;                            /*结点的键值,为非负整数*/
Struct BiTnode*left,*right;                  /*结点的左、右子树指针*/
}BiTnode,*BSTree;
【C 函数】
int   Insert_key   ( BSTree  *root ,int  key  )
{
     BiTnode  *father  =  NULL ,*p =  *root ,*s;

     while   ((1)&& key  != p->key_value   )    {            /*查找键值为key的结点*/
             father  =  p;
             if   (   key   < p->key_value)     p  =(2); /*进入左子树*/
             else           p =(3);                      /*进入右子树*/
     }
           
      if (p)   return  0;    /*二叉查找树中己存在键值为 key 的结点,无需再插入*/
 
      s = (BiTnode *)malloc ((4)); /*根据结点类型生成新结点*/
      if  (!s)  return  -1;
      s->key_value  =  key;     s->left  =  NULL;      s->right  =  NULL;
  
      if (   !father  )
        (5);   /*新结点作为二叉查找树的根结点*/
      else     /*新结点插入二叉查找树的适当位置*/
                    if   (   key  <  father->key_value)   father->left   =    s;
                    else father->right   =  s;
       return  1;
}


相关试题

推荐文章
合作网站内容