首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明、C函数和问题,将解答填入答题纸的对应栏内。 【说明】 二叉查找树又称为二叉排序树,它或者是一棵空树,或者是具有如下性质的二叉树: •若它的左子树非空,则其左子树上所有结点的键值均小于根结点的键值; •若它的右子树非空,则其右子树上所有结点的键
阅读以下说明、C函数和问题,将解答填入答题纸的对应栏内。 【说明】 二叉查找树又称为二叉排序树,它或者是一棵空树,或者是具有如下性质的二叉树: •若它的左子树非空,则其左子树上所有结点的键值均小于根结点的键值; •若它的右子树非空,则其右子树上所有结点的键
admin
2010-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(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
程序员下午应用技术考试
软考初级
相关试题推荐
企业实现移动信息化的作用不包括________________。
某企业甲乙两个部门招聘职工中,男女应聘人数和录用人数情况如下表:从上表看出,各部门女性录用率都大于男性录用率。从该企业合计来看,()。
下列快捷功能按钮中,可以在画好的图形内填充颜色的是(49)。
在Word2007中,若用户需要将一篇文章中的字符串“Internet”全部替换为字符串“因特网”,则可以在编辑菜单中选择()命令。
在Excel2003中,A1到E6单元格的值如下图所示,若在A7单元格中输入计算众数的函数“=MODE(A1:E6)”,按回车键后,则.A7单元格显示的值为(47)。
双击某个非可执行程序的文件名将(24)。
为使双击指定类型的文件名就能调用相应的程序来打开处理它,需要将这种文件类型与相应的程序建立文件(23)。
某公司下设4个分公司A、B、C、D,上月各分公司的销售额及其在总公司所占比例如下表所示。由于此表单受潮,有些数据看不清了,但还可以推算出来。根据推算, D公司上月的销售额为(68)万元。
在下列的Excel表中,在C3单元格输入公式“=A2+$C$2”,则C3单元格的值为(55)。
请根据网页显示的效果图和网页中的元素说明,将HTML文本中(n)处的解答填入答题纸对应的解答栏内。说明在Ⅲ浏览器中输入常春藤大学招生办公室主页的网址并回车后,网页显示的效果如图5-1所示。HTML文本<html><he
随机试题
王莹穿的新款服装在学校招来了许多同学异样的目光,第二天就不再穿这件衣服上学了。这种心理现象是()
下列哪项是COPD诊断及病情严重程度评价的客观指标
患者,男性,37岁。因突然右侧剧烈腰痛伴肉眼血尿就诊,既往有风湿性心脏病、心房颤动病史。尿常规示:蛋白(++),红细胞满视野,白细胞5~8个/HP。临床首先考虑
超声诊断早期妊娠,首先见到的是
下列属于胎儿窘迫的表现有
某重症中暑病人,肛温40℃,给予降温处理,你认为降温至肛温多少度,暂停降温措施()。
根据《消费者权益保护法》的规定,下列说法错误的是( )。
ROM是指()。
Whatwillthewomanprobablydo?
Thepoliceknewnothingaboutthecase______yourfatherphonethem.
最新回复
(
0
)