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

题目详情

全站导航

首页试卷库试题库

试卷导航

学历类职业资格公务员医卫类建筑工程外语类计算机类财会类

试题导航

学历类职业资格公务员医卫类建筑工程外语类计算机类财会类

阅读以下说明、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作了比较。因此，在树中查找一个关键字时，需要比较的结点个数取决于该关键字对应结点在该二叉查找树所在层次（数）或位置。

初级程序员,章节练习,基础复习,案例分析