首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明、C函数和问题,将解答填入答题纸的对应栏内。 【说明】 二叉查找树又称为二叉排序树,它或者是一棵空树,或者是具有如下性质的二叉树: •若它的左子树非空,则其左子树上所有结点的键值均小于根结点的键值; •若它的右子树非空,则其右子树上所有结点的键
阅读以下说明、C函数和问题,将解答填入答题纸的对应栏内。 【说明】 二叉查找树又称为二叉排序树,它或者是一棵空树,或者是具有如下性质的二叉树: •若它的左子树非空,则其左子树上所有结点的键值均小于根结点的键值; •若它的右子树非空,则其右子树上所有结点的键
admin
2010-01-08
83
问题
阅读以下说明、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
程序员下午应用技术考试
软考初级
相关试题推荐
某学校起草的对信息化教学资源的格式要求中,________________有错误。
________________是按照科学的城市发展理念,利用新一代信息技术,通过人、物、城市功能系统之间的无缝连接与协同联动,实现自感知、自适应、自优化,形成安全、便捷、高效、绿色的城市形态。
对数据分析处理人员的素质要求不包括()。
下列关于Windows7屏幕保护程序的叙述中,不正确的是__________。
在Excel2007中,在单元格A1中输入函数“=LEN(”信息处理技术员”)”,按回车键后,则A1单元格中的值为__________。
计算机操作系统的主要功能是______。
某公司下设4个分公司A、B、C、D,上月各分公司的销售额及其在总公司所占比例如下表所示。由于此表单受潮,有些数据看不清了,但还可以推算出来。根据推算, D公司上月的销售额为(68)万元。
在Windows7运行时,为强行终止某个正在持续运行且没有互动反应的应用程序,可按组合键Ctrl+Alt十Del启动(24)________________,选择指定的进程和应用程序,结束其任务。
请根据图2-13网页的显示效果,解释该ASP程序中用下画线标出的语句的含义,即填写(1)、(3)、(4)、(6)、(10)空缺处的解释内容。在index.asp文档中使用了<styletype="text/css">语句。其中,CSS是指(10),
阅读下列说明和HTML文本,分析其中嵌入的JavaScrlpt脚本,将应填入<u>(n)</u>处的语句写在对应栏内。[说明]本题实现用鼠标拖拽图片在Web页内移动的功能。将鼠标放在图片上,按下左键,移动鼠标便可带动图片一起移动。[
随机试题
若施工中施工图纸或设计变更与工程量清单项目特征表述不一致,发承包双方应(),依据合同约定重新确定综合单价。
美育作为一门独立的学科的出现是以哪一部著作的诞生为标志的()
射野输出因子(OUT)是描述射野输出剂量随射野增大而增加的关系,它定义为
初产妇,23岁。妊娠40周,临产8小时后出现烦躁不安,呼吸加快,下腹疼痛,拒按,胎心听不清,查体见下腹部近肚下方一环状凹陷,导尿为血尿,该患者最可能的诊断是
混悬液型气雾剂属于乳浊液型气雾剂属于
A.软膏剂B.贴剂C.凝胶膏剂D.膏药E.橡胶膏剂由背衬层、药物贮库层、黏胶层和防黏层组成的薄片状贴膏剂是()。
《2000年国际贸易术语解释通则》中,C组贸易术语与其他组的贸易术语的区别是( )。
关于个人教育贷款,以下理解有误的是()。
你发现一个同事在工作中遇到了困难,而你又具有解决这个困难的能力。在这种情况下,你通常采取的做法是()。
IfoursolarsystemhasaHell,it’sVenus.Theairischokedwithfoulandcorrosivesulfur,heavedfromancientvolcanoesand
最新回复
(
0
)