首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和C函数,填充函数中的空缺,将解答填入答题纸的对应栏内。 【说明】 函数Insert_key(*root,key)的功能是将键值key插入到*root指向根结点的二叉查找树中(二叉查找树为空时*root为空指针)。若给定的二叉查
阅读以下说明和C函数,填充函数中的空缺,将解答填入答题纸的对应栏内。 【说明】 函数Insert_key(*root,key)的功能是将键值key插入到*root指向根结点的二叉查找树中(二叉查找树为空时*root为空指针)。若给定的二叉查
admin
2013-07-03
36
问题
阅读以下说明和C函数,填充函数中的空缺,将解答填入答题纸的对应栏内。
【说明】
函数Insert_key(*root,key)的功能是将键值key插入到*root指向根结点的二叉查找树中(二叉查找树为空时*root为空指针)。若给定的二叉查找树中已经包含键值为key的结点,则不进行插入操作并返回0;否则申请新结点、存入key的值并将新结点加入树中,返回1。
提示:
二叉查找树又称为二叉排序树,它或者是一棵空树,或者是具有如下性质的二叉树:
.若它的左子树非空,则其左子树上所有结点的键值均小于根结点的键值;
.若它的右子树非空,则其右子树上所有结点的键值均大于根结点的键值;
.左、右子树本身就是二叉查找树。
设二叉查找树采用二叉链表存储结构,链表结点类型定义如下:
typedef struct BiTnode{
int key_value; /*结点的键值,为非负整数*/
struct BiTnode * left,* right; /*结点的左、右子树指针*/
}BiTnode,*BSTree;
【C函数】
int Insert_key(BSTree * root,int key)
{
BiTnode * father=NULL,* p= * root, * s;
while(
(1)
&&key!=p->key_value){ /*查找键值为key的结点*/
father=p;
if(key<p->key_value)p=
(2)
; /*进入左子树*/
else p=
(3)
; /*进入右子树*/
}
if(p)return 0; /*二叉查找树中已存在键值为key的结点,无须再插入*/
s=(BiTnode*)malloc(
(4)
); /*根据结点类型生成新结点*/
if(!s)return-1;
s->key_value=key;s->left=NULL;s->right=NULL;
if( ! father)
(5)
; /*新结点作为二叉查找树的根结点*/
else /*新结点插入二叉查找树的适当位置*/
if(key
key_value)father->left=s:
else father->right=s;
return 1:
}
选项
答案
(1)p!=NULL (2)p->left (3)p->right (4)sizeof(BiTnode) (5)*root=s
解析
本题考查数据结构中二叉查找树的实现,题目中涉及的考点主要有链表运算和程序逻辑。考生应理解二又查找树的性质,分析程序时首先要明确各个变量所其的作用和代表的含义,并按照语句组分析各段代码的功能,从而完成空缺处的代码填写。
根据程序段中的注释,whiIe循环所在的程序段用于查找键值为key的结点。此时的循环条件应满足二叉查找树非空。因此,(1)处应填入p!=NuLL或其等价形式。
根据二叉查找树的性质,若它的左子树非空,则其左子树上所有结点的键值均小于根结点的键值。因此,若插入的键值key小于当前结点的键值,则应将其添加到其左子树中。因此,(2)处应填入p->1eft。类似的思路,(3)处应填入p->right使其进入右子树。
根据程序段中的注释,(4)处用于根据结点类型生成新结点。由于需申请的结点的类型为BiTnode,因此,(4)处应填入sizeof(BiTnode),指定申请空间的大小。
若该二叉查找树为空,新结点应作为二叉查找树的根结点进行插入,(5)处即实现该功能,应填入*root=s。
转载请注明原文地址:https://kaotiyun.com/show/0njZ777K
本试题收录于:
程序员下午应用技术考试题库软考初级分类
0
程序员下午应用技术考试
软考初级
相关试题推荐
某互联网公司建立的用户画像(标签化的用户信息)包括人口属性和行为特征两大类,()属于行为特征。
图文混排是Word的特色功能之一,下列叙述中,不正确的是(46)。
(1)是固化在主板ROM内的程序,为计算机提供最底层、最直接的硬件访问和控制。
在Excel2007中,利用填充柄可以将数据复制到相邻单元格中。若选择含有数值的上下相邻的两个单元格,按住鼠标左键向下拖动填充柄,则数据将以(49)________________填充。
操作系统的功能不包括______。
某咨询顾问公司派小强统计本市各品牌汽车的占有率,以下4种统计方法中,小强应采用______方法,使估算结果较为可信。
许多书上都说,人一次只能记住或处理5~9(7±2)条信息。为了检验这个结论是否正确,宜采用()调查方法。经过多次调查统计研究发现,人一次平均只能记住或处理4条信息。经考证,原来7±2的说法只是一位专家在一个讲演稿中的估计,并不是真正的调研报告,但却
小张为本企业录入一篇领导讲话文稿。文稿中引用了该企业2008年的销售额和各产品的利润等数据。小张考虑到目前是2010年,从信息的实效性出发,决定对文稿中的这部分内容进行处理,则______做法最为恰当。
()是移动互联网的组成部分。
综合布线系统由6个子系统组成,将图1-1中(1)~(6)处空缺子系统的名称填写在答题纸对应的解答栏内。制作交叉双绞线(一端按EIA/TIA568A线序,另一端按EIA/TIA568B线序)时,其中一端的线序如图1-2(a)所示,另一端线序如图1—2
随机试题
出现某些难以控制的不必要的担心,这属于()
法律关系主体包括()或其他组织。
()被视为最具权威性的股份指数,也被认为是反映美国政治、经济和社会最灵敏的指标。
新设立的风景名胜区与自然保护区不得重合或者交叉。()
根据对联的类别,“海纳百川,有容乃大;壁立千仞,无欲则刚”是()。
随着老龄化的加速,我国养老问题日益引人关注。最新的统计资料表明,我国企业退休人员已超过6000万人,基本养老金人均每月1700多元,能够维持基本生活需要;农村老人主要依靠自身劳作、每月55元或更多的养老金,以及子女能够提供的赡养费等勉强过日子,生不起病。城
当怀揣着航海计划的哥伦布同西班牙王室讨价还价时,伊莎贝尔女王在谈判中接受了这个普通百姓的热切要求。为了资助哥伦布的远航,女王甚至卖掉了自己王冠上的珠宝。但是,她由此赢回了更加辉煌的王冠,那是世界霸主的桂冠。为本文段加一个标题,最适合的是()。
将一个表面积为18平方厘米的正方体沿对角线切成两块对称的三棱柱(见右图),并将这两块三棱柱重新拼接成一个大的三棱柱。则这个大三棱柱的表面积最大为()平方厘米。
神经冲动在神经元之间的传递是借助()实现的。
Mancannotgoonincreasinghisnumberatthepresentrate.Inthe【C1】______30yearsmanwillfaceaperiodofcrisis.【C2】______
最新回复
(
0
)