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

   阅读以下说明、C 函数和问题,将解答填入答题纸的对应栏内。
【说明】
    二叉查找树又称为二叉排序树,它或者是一棵空树,或者是具有如下性质的二叉树:
    若它的左子树非空,则其左子树上所有结点的键值均小于根结点的键值;
    若它的右子树非空,则其右子树上所有结点的键值均大于根结点的键值;
    左、右子树本身就是二叉查找树。
    设二叉查找树采用二叉链表存储结构,链表结点类型定义如下:
    typedef struct BiTnode{
int    key_value;   /*结点的键值,为非负整数*/
    struct BiTnode *left,*right;    /*结点的左、右子树指针*/
}*BSTree;
    函数find_key(root, key)的功能是用递归方式在给定的二叉查找树(root指向根结点)中查找键值为key的结点并返回结点的指针;若找不到,则返回空指针。
 
【函数】
    BSTree find_key(BSTree root, int key)  
    {
    if (     (1)  )
    return NULL;
    else
    if (key == root-> key_value)
  return (2)    ;  
    else if (key < root -> key_value)
  return (3)    ;
    else
  return (4)    ;
}
【问题1】
    请将函数find_key中应填入(1)~(4)处的字句写在答题纸的对应栏内。
【问题2】
    若某二叉查找树中有n个结点,则查找一个给定关键字时,需要比较的结点个数取决于  (5)  。 


相关试题

推荐文章
合作网站内容