首页
登录
从业资格
阅读以下说明、C 函数和问题,将解答填入答题纸的对应栏内。 【说明】
阅读以下说明、C 函数和问题,将解答填入答题纸的对应栏内。 【说明】
题库
2022-08-02
22
问题
阅读以下说明、C 函数和问题,将解答填入答题纸的对应栏内。【说明】 二叉查找树又称为二叉排序树,它或者是一棵空树,或者是具有如下性质的二叉树: 若它的左子树非空,则其左子树上所有结点的键值均小于根结点的键值; 若它的右子树非空,则其右子树上所有结点的键值均大于根结点的键值; 左、右子树本身就是二叉查找树。 设二叉查找树采用二叉链表存储结构,链表结点类型定义如下: typedef struct BiTnode{int key_value; /*结点的键值,为非负整数*/ struct BiTnode *left,*right; /*结点的左、右子树指针*/}*BSTree; 函数find_key(root, key)的功能是用递归方式在给定的二叉查找树(root指向根结点)中查找键值为key的结点并返回结点的指针;若找不到,则返回空指针。 【函数】 BSTree find_key(BSTree root, int key) { if ( (1) ) return NULL; else if (key == root-> key_value) return (2) ; else if (key < root -> key_value) return (3) ; else return (4) ;}【问题1】 请将函数find_key中应填入(1)~(4)处的字句写在答题纸的对应栏内。【问题2】 若某二叉查找树中有n个结点,则查找一个给定关键字时,需要比较的结点个数取决于 (5) 。
选项
答案
解析
(1) !root,或root=0,或root==NULL (2) root (3) find_key(root→left, key) (4) find_key(root→right, key) (5)该关键字对应结点在该二叉查找树所在层次(数)或位置,或者该二叉树中从根结点到该关键字对应结点的路径长度本题考查数据结构的应用、指针和递归程序设计。 根据二叉查找树的定义,在一棵二叉查找树上进行查找时,首先用给定的关键字与树根结点的关键字比较,若相等,则查找成功;若给定的关键字小于树根结点的关键字,则接下来到左子树上进行查找,否则接下来到右子树上进行查找。如果在给定的二叉查找树上不存在与给定关键字相同的结点,则必然进入某结点的空的子树时结束查找。因此,空(1)处填入!root表明进入了空树;空(2)处填入root表明返回结点的指针;空(3)处填入find_key(root→left, key)表明下一步到左子树上继续查找;空(4)处填入find_key(root→right, key)表明下一步到右子树上继续查找。 显然,在二叉排序树上进行查找时,若成功,则查找过程是走了一条从根结点到达所找结点的路径。例如,在下图所示的二叉排序树中查找62,则依次与46、54、101和62作了比较。因此,在树中查找一个关键字时,需要比较的结点个数取决于该关键字对应结点在该二叉查找树所在层次(数)或位置。
转载请注明原文地址:https://www.tihaiku.com/congyezige/2427889.html
本试题收录于:
初级程序员题库软件水平考试初中高级分类
初级程序员
软件水平考试初中高级
相关试题推荐
()是指对要达到项目目标准备采取的技术手段、具体步骤及解决关键性问题的方法等在内
对关键复杂的墙板进行拆分,解决钢筋绑扎、顺序问题等,并对该部分进行施工图深化属于
基于BIM的深化设计通过各专业工程师与设计公司的分工合作优化能够针对设计存在问题
对已经绘制好的风管进行“修改类型”的操作,可能会发生什么问题?()A.弯头形状变
项目后评价的步骤为()。A.提出问题→筹划准备→深入调查,搜集资料→分析研究→编
业主单位在设计阶段通过组织(),可以提前发现概念设计、方案设计中潜在的风险和问题
病例:根据下列家系图,回答问题。 [YZ610_378_1.gif]对该家系图
病例:根据下列家系图,回答问题。 [YZ610_378_1.gif]对该家系图
根据下列家系图,回答问题。 [YZ610_320_1.gif]关于该家系图中各
根据下列家系图,回答问题。 [YZ610_320_1.gif]对该家系图中各符
随机试题
[originaltext]W:Hey,Mike!DidyouattendMr.Johnson’sseminarontheHistory
某地区灰岩,饱和单轴抗压强度为45MPa,岩体完整性系数KV为0.65,下列完整
压缩试验土样侧向()。A.无变形 B.有变形 C.无限制 D.不一定
A.抑制壁细胞的酸泵 B.阻断H受体 C.中和胃酸 D.抗幽门螺杆菌 E
A、甲基橙 B、甲基红 C、酚酞 D、石蕊
某医院原计划采购普通医用口罩和N95口罩共480箱,采购时因为供货量的问题,将的
下列代理情形中,属于滥用代理权的有()。A.超越代理权限的行为 B.自己代理
采用ABS融资方式进行项目融资的物质基础是( )。A.债权发行机构的注册资金
(2016年)根据《声环境质量标准》,下列区域中,属于1类声环境功能区的是()A
早期妊娠诊断,下列哪项是错误的A.阴道壁和子宫颈呈紫蓝色 B.黑加征阳性 C
最新回复
(
0
)