2. 计算机
  3. 阅读以下说明和C函数，填充函数中的空缺，将解答填入答题纸的对应栏内。 【说明】 函数Insert_key(*root，key)的功能是将键值key插入到*root指向根结点的二叉查找树中(二叉查找树为空时*root为空指针)。若给定的二叉查

阅读以下说明和C函数，填充函数中的空缺，将解答填入答题纸的对应栏内。 【说明】 函数Insert_key(*root，key)的功能是将键值key插入到*root指向根结点的二叉查找树中(二叉查找树为空时*root为空指针)。若给定的二叉查

admin2013-07-03  65
问题 阅读以下说明和C函数，填充函数中的空缺，将解答填入答题纸的对应栏内。
    【说明】
    函数Insert_key(*root，key)的功能是将键值key插入到*root指向根结点的二叉查找树中(二叉查找树为空时*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(keykey_value)father->left=s：
      else father->right=s；
    return 1：
}
选项
答案(1)p!=NULL (2)p->left (3)p->right (4)sizeof(BiTnode) (5)*root=s
解析 本题考查数据结构中二叉查找树的实现，题目中涉及的考点主要有链表运算和程序逻辑。考生应理解二又查找树的性质，分析程序时首先要明确各个变量所其的作用和代表的含义，并按照语句组分析各段代码的功能，从而完成空缺处的代码填写。
    根据程序段中的注释，whiIe循环所在的程序段用于查找键值为key的结点。此时的循环条件应满足二叉查找树非空。因此，(1)处应填入p!=NuLL或其等价形式。
    根据二叉查找树的性质，若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值。因此，若插入的键值key小于当前结点的键值，则应将其添加到其左子树中。因此，(2)处应填入p->1eft。类似的思路，(3)处应填入p->right使其进入右子树。
    根据程序段中的注释，(4)处用于根据结点类型生成新结点。由于需申请的结点的类型为BiTnode，因此，(4)处应填入sizeof(BiTnode)，指定申请空间的大小。
    若该二叉查找树为空，新结点应作为二叉查找树的根结点进行插入，(5)处即实现该功能，应填入*root=s。
转载请注明原文地址:https://www.kaotiyun.com/show/0njZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

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