首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明、C函数和问题,将解答填入答题纸的对应栏内。 【说明】 二叉查找树又称为二叉排序树,它或者是一棵空树,或者是具有如下性质的二叉树: •若它的左子树非空,则其左子树上所有结点的键值均小于根结点的键值; •若它的右子树非空,则其右子树上所有结点的键
阅读以下说明、C函数和问题,将解答填入答题纸的对应栏内。 【说明】 二叉查找树又称为二叉排序树,它或者是一棵空树,或者是具有如下性质的二叉树: •若它的左子树非空,则其左子树上所有结点的键值均小于根结点的键值; •若它的右子树非空,则其右子树上所有结点的键
admin
2010-01-08
77
问题
阅读以下说明、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)________________。
某商场购进了一批洗衣机,加价25%销售了60%后,在此基础上再打8折销完,则这批洗衣机的总销售收入相对于进价总额的利润率为________________。
在Excel2010中,设A1单元格中的值为20,A2单元格中的值为60,若在C1单元格中输入函数“=AVERAGE(A1,A2)”,按回车键后,,则C1单元格中的值为(
企业建立生产和库存管理系统的目的不包括()。
西部某省考试机构工作人员统计了去年下半年三个地区四种资格的报考人数,将统计表抄录如下(其中有一个数据抄错了): 信息处理技术员小王很快就找出了错误的数据,并进行了纠正。错误的数据是(32),该数据应纠正为(33)。33.
在Word2007中,若用户需要将一篇文章中的字符串“Internet”全部替换为字符串“因特网”,则可以在编辑菜单中选择()命令。
在Excel中,设单元格A1中的值为100,B1中的值为200,A2中的值为300,B2中的值为400,若在A3单元格中输入函数“=SUM(A1:B2)”,按回车键后,A3单元格中的值为()。
电子商务有多种模式。()模式是个人消费者从在线商家处购买商品或服务。
某公司下设4个分公司A、B、C、D,上月各分公司的销售额及其在总公司所占比例如下表所示。由于此表单受潮,有些数据看不清了,但还可以推算出来。根据推算, D公司上月的销售额为(68)万元。
请根据图2-13网页的显示效果,解释该ASP程序中用下画线标出的语句的含义,即填写(1)、(3)、(4)、(6)、(10)空缺处的解释内容。请根据图2-13网页的显示效果,将ASP程序中(2)、(5)、(7)、(8)、(9)空缺处的代码补充完整。A
随机试题
口酸是因
下列关于主要诊断选择原则正确的是
A.局麻药B.麻醉性镇痛药C.皮质类固醇激素类药物D.神经破坏性药物E.抗癫痫药物椎管内注入,常用于手术后镇痛的是
关于鼻咽癌哪一项是错误的
前列腺增生出现的症状不决定于
王某与张某签订了一份书面合同,约定由王某在签约后3日借给张某2万元,张某于2年后偿还该2万元并支付10%的利息,该行为属于何种民事法律行为?
矸石场属于()性设施。
学校对故意不完成教育教学任务给教育教学工作造成损失的教师,可以给予()。
五年级学生分成两队参加广播操比赛,排成甲、乙两个实心方阵,其中甲方阵最外层每边的人数为8。如果两队合并,可以另排成一个空心的丙方阵,丙方阵最外层每边的人数比乙方阵最外层每边的人数多4人,且甲方阵的人数正好填满丙方阵的空心。五年级一共有多少人?()
孙中山资产阶级民主主义思想的集大成者是三民主义,其核心内容是()
最新回复
(
0
)