首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明、C函数和问题,将解答填入答题纸的对应栏内。 【说明】 二叉查找树又称为二叉排序树,它或者是一棵空树,或者是具有如下性质的二叉树: •若它的左子树非空,则其左子树上所有结点的键值均小于根结点的键值; •若它的右子树非空,则其右子树上所有结点的键
阅读以下说明、C函数和问题,将解答填入答题纸的对应栏内。 【说明】 二叉查找树又称为二叉排序树,它或者是一棵空树,或者是具有如下性质的二叉树: •若它的左子树非空,则其左子树上所有结点的键值均小于根结点的键值; •若它的右子树非空,则其右子树上所有结点的键
admin
2010-01-08
36
问题
阅读以下说明、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://jikaoti.com/ti/WkW7FFFM
本试题收录于:
程序员下午应用技术考试题库软考初级分类
0
程序员下午应用技术考试
软考初级
相关试题推荐
以下关于windows7文件名的叙述中,(20)________________是正确的。
在Excel2010中,设单元格A1、B1、C1、A2、B2、C2中的值分别为1、2、3、4、5、6,若在单元格D1中输入函数“=MAX(A1:A2,B1:C2)”,按回车键后,则D1单元格中的值为(
某金融企业正在开发移动终端非现场办公业务,为控制数据安全风险,采取的数据安全措施中并不包括______。
在Excel中,若A1单元格中的内容为“全国计算机技术与软件专业技术资格(水平)考试”,在A2单元格中输入函数=LEFT(A1,2),则A2单元格显示的内容是______。
电子商务有多种模式。()模式是个人消费者从在线商家处购买商品或服务。
在Excel2010中,G3单元格中公式为“=$D$3+E3+F3”,若以序列方式向下填充,则G12单元格的公式为()。
为什么一般处理“震荡波”病毒时,首先要把被侵入的计算机系统从网络上断开?在计算机系统发现病毒并清除以后,在未接入网络之前,从安全方面考虑,若需重新安装操作系统,通常需要执行以下几项主要工作后,方可接入网络。请给出下列工作的合理顺序。A.安装操作
阅读下列说明和HTML文本,分析其中嵌入的JavaScrlpt脚本,将应填入<u>(n)</u>处的语句写在对应栏内。[说明]本题实现用鼠标拖拽图片在Web页内移动的功能。将鼠标放在图片上,按下左键,移动鼠标便可带动图片一起移动。[
/etc/dhcpd.conf文件中的配置语句:hostCIU_DHCP{hardwareethemet52.54.AB.3B.B6.45fixed-address192.168.1.15;}表示的是什么意思?当配置文件配置好以后,还
随机试题
FC型光纤连接器是()式的。
抗癫痫药物需服用多久()。
含牙囊肿的定义是
患儿,疳证,见足踝浮肿,甚则颜面四肢浮肿,面色无华,四肢欠温,小便不利,大便溏薄,舌淡红,苔薄白。治宜()
消费行为研究的主要内容包括()。
下列油漆工程量计算规则中,正确的说法是()。【2006年真题】
贴水出售的债券的到期收益率与该债券的票面利率之间的关系是( )。
票据权利的保全是指票据债权人请求票据债务人履行其票据债务行为。()
最近出版されたこの著者の本はすべて読みました。出版
Educationisalongprocessthatnotonlyprovidesuswithbasicskillssuchasliteracyandnumeracy,butisalsoessentialin
最新回复
(
0
)