2. 计算机
  3. 阅读以下说明、C函数和问题，将解答填入答题纸的对应栏内。 【说明】 二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树： •若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值； •若它的右子树非空，则其右子树上所有结点的键

阅读以下说明、C函数和问题，将解答填入答题纸的对应栏内。 【说明】 二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树： •若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值； •若它的右子树非空，则其右子树上所有结点的键

admin2010-01-08  76
问题 阅读以下说明、C函数和问题，将解答填入答题纸的对应栏内。
【说明】
二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树：
•若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值；
•若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值；
•左、右子树本身就是二叉查找树。
设二叉查找树采用二叉链表存储结构，链表结点类型定义如下：
typedef struct BiTnode{
int key_value；    ／*结点的键值，为非负整数*／
struct BiTnode*left，*right；  ／*结点的左、右子树指针*／
}*BSTree；
函数find—key(root，key)的功能是用递归方式在给定的二叉查找树(root指向根结点)中查找键值为key的结点并返回结点的指针；若找不到，则返回空指针。
【C函数】
BSTree find_key(BSTree root，int key)
{
if  (    (1)    )
return NULL；
else
if(key==root->key_valuel
return  (2)  ；
else if(keyreturrl  (3)  ；
else
return (4)  ；
}
[问题1]
请将函数find_key中应填入(1)一(4)处的字句写在答题纸的对应栏内。
[问题2]
若某二叉查找树中有n个结点，则查找一个给定关键字时，需要比较的结点个数取决于(5)    。
选项
答案(1)!root或rool==NuLL (2)root (3)find_key(root->。left，key)(4)find_key(root->fight，key)(5)该关键字对应结点在该二叉查找树所在层次(数)或位置，或者该二叉树中从根结点到该关键字对应结点的路径长度。
解析 根据“说明”中对二叉查找树的定义可以知道在对二叉查找树进行查找时，应该按照以下步骤来进行。(1)首先判断二叉查找树是否为空，如果为空，直接返回NuLL；否则，继续向下走。(2)判断键值key与树根结点的键值比较的大小。(3)如果相等，则返回树根结点。(4)如果大于树根结点，则以树根结点的右子树为根结点，从步骤(1)开始继续循环查找。(5)如果小于树根结点，则以树根结点的左子树为根结点，从步骤(1)开始继续循环查找。(6)递归调用查找函数，如果给定的二叉查找树上不存在与给定的键值相等的结点，则必然进入某一个结点的空的子树时结束。从以上的步骤分析可以看出空(1)处应该是判断root是否为空，故答案为“root==NuLL”或!root；空(2)的时候查找到与key相等的键值，返回该节点指针，故答案为“root”；空(3)处key的值小于根结点的键值，则应该以该根结点的左子树为根结点重新查找，故答案为“find_key(root->1eft，key)”；空(4)处则是处理剩下的最后一种情况，即key的值大于根结点的键值，这时候应该以该根结点的右子树为根结点，递归调用函数，所以答案为“find_key(root->fight，key)”。根据上面的二叉查找树的查找过程中可以看出，查找成功其实是走了一条从根结点到达所找结点的路径。例如要从下面的二叉查找树中查找75，则需要依次与50、67、89、75进行比较，可以看出在树中查找一个关键字，需要比较的结点的个数取决于该关键字对应结点在该二叉查找树中所在层数或位置，或者是该二叉查找树从根结点到该关键字的对应结点的路径长度。
转载请注明原文地址:https://kaotiyun.com/show/jIjZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

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