2. 从业资格
  3. 阅读以下说明、C 函数和问题，将解答填入答题纸的对应栏内。 【说明】

阅读以下说明、C 函数和问题，将解答填入答题纸的对应栏内。 【说明】

题库2022-08-02  45
问题 阅读以下说明、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）  。
选项
答案
解析 （1） !root，或root=0，或root==NULL    （2） root    （3） find_key(root→left， key)    （4） find_key(root→right， key)    （5）该关键字对应结点在该二叉查找树所在层次（数）或位置，或者该二叉树中从根结点到该关键字对应结点的路径长度本题考查数据结构的应用、指针和递归程序设计。    根据二叉查找树的定义，在一棵二叉查找树上进行查找时，首先用给定的关键字与树根结点的关键字比较，若相等，则查找成功；若给定的关键字小于树根结点的关键字，则接下来到左子树上进行查找，否则接下来到右子树上进行查找。如果在给定的二叉查找树上不存在与给定关键字相同的结点，则必然进入某结点的空的子树时结束查找。因此，空（1）处填入!root表明进入了空树；空（2）处填入root表明返回结点的指针；空（3）处填入find_key(root→left， key)表明下一步到左子树上继续查找；空（4）处填入find_key(root→right， key)表明下一步到右子树上继续查找。    显然，在二叉排序树上进行查找时，若成功，则查找过程是走了一条从根结点到达所找结点的路径。例如，在下图所示的二叉排序树中查找62，则依次与46、54、101和62作了比较。因此，在树中查找一个关键字时，需要比较的结点个数取决于该关键字对应结点在该二叉查找树所在层次（数）或位置。
转载请注明原文地址:https://tihaiku.com/congyezige/2427889.html
本试题收录于： 初级程序员题库软件水平考试初中高级分类

初级程序员

软件水平考试初中高级

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