首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明、C函数和问题,将解答填入答题纸的对应栏内。 【说明】 二叉查找树又称为二叉排序树,它或者是一棵空树,或者是具有如下性质的二叉树: •若它的左子树非空,则其左子树上所有结点的键值均小于根结点的键值; •若它的右子树非空,则其右子树上所有结点的键
阅读以下说明、C函数和问题,将解答填入答题纸的对应栏内。 【说明】 二叉查找树又称为二叉排序树,它或者是一棵空树,或者是具有如下性质的二叉树: •若它的左子树非空,则其左子树上所有结点的键值均小于根结点的键值; •若它的右子树非空,则其右子树上所有结点的键
admin
2010-01-08
62
问题
阅读以下说明、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(key
returrl (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
程序员下午应用技术考试
软考初级
相关试题推荐
一般来说,收集到的数据经过清洗后,还需要进行分类、排序等工作。这样做的好处主要是(65)________________。
如果表A和表B中有公共字段,且该字段在表B中称为主键,则该字段在表A中称为________________。
在Excel2010的A1单元格中输入函数“=ABS(ROUND(-1.478,2))”,按回车键后,A1单元格中的值为________________。
某班级有40名学生,本次数学考试大多在80分上下。老师为了快速统计平均分,对每个学生的分数按80分为基准,记录其相对分(多出的分值用正数表示,减少的分值用负数表示,恰巧等于80分时用0表示),再统计出各种相对分的人数,如下表:根据上表可推算出,这次考试
在Excel2007中,在单元格A1中输入函数“=POWER(2,3)/MAX(1,2,4)”,按回车键后,则A1单元格中的值为__________。
西部某省考试机构工作人员统计了去年下半年三个地区四种资格的报考人数,将统计表抄录如下(其中有一个数据抄错了): 信息处理技术员小王很快就找出了错误的数据,并进行了纠正。错误的数据是(32),该数据应纠正为(33)。32.
___________接口是目前微机上最流行的I/O接口,具有支持热插拔、连接灵活、独立供电等优点,可以连接常见的鼠标、键盘、打印机、扫描仪、摄像头、充电器、闪存盘、MP3机、手机、数码相机、移动硬盘、外置光驱、Modem等几乎所有的外部设备。
计算机使用了一段时间后,系统磁盘空间不足,系统启动时间变长,系统响应延迟,应用程序运行缓慢,此时,需要对系统进行优化。(28)________________不属于系统优化工作。
在Excel2010中,G3单元格中公式为“=$D$3+E3+F3”,若以序列方式向下填充,则G12单元格的公式为()。
请根据网页显示的效果图和网页中的元素说明,将HTML文本中(n)处的解答填入答题纸对应的解答栏内。说明在Ⅲ浏览器中输入常春藤大学招生办公室主页的网址并回车后,网页显示的效果如图5-1所示。HTML文本<html><he
随机试题
睑外翻的病因中不包括
阿托品在眼科方面用于()
燃气燃烧的方法不包括()。
下列关于中小企业私募债特征说法正确的有()。
《银行业监督管理法》规定。对发生风险的银行业金融机构进行处置的方式有()。
一个人面对同一问题,能想出多种不同类型的答案。这表明他的思维具有()
树是结点的有限集合,一棵树中有()根结点。
设A为3阶矩阵,P=(α1,α2,α3)为3阶可逆矩阵,Q=(α1+α2,α2,α3).已知PTAP=则QTAQ=().
Exactlywherewewillstandinthelongwaragainstdiseasebytheyear2050isimpossibletosay.(46)Butifdevelopmentsinre
使用“调试器”调试程序时,用于显示正在调试的程序文件的窗口是______。
最新回复
(
0
)