首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和C函数,填充函数中的空缺,将解答填入答题纸的对应栏内。 【说明】 函数Insert_key(*root,key)的功能是将键值key插入到*root指向根结点的二叉查找树中(二叉查找树为空时*root为空指针)。若给定的二叉查
阅读以下说明和C函数,填充函数中的空缺,将解答填入答题纸的对应栏内。 【说明】 函数Insert_key(*root,key)的功能是将键值key插入到*root指向根结点的二叉查找树中(二叉查找树为空时*root为空指针)。若给定的二叉查
admin
2013-07-03
77
问题
阅读以下说明和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
程序员下午应用技术考试
软考初级
相关试题推荐
在Windows环境中,选择某一部分信息(例如一段文字、一个图形)移动到别处,可以首先执行“编辑”菜单下的(5)命令。
图文混排是Word的特色功能之一,下列叙述中,不正确的是(46)。
在Excel中,若A1单元格中的内容为“全国计算机技术与软件专业技术资格(水平)考试”,在A2单元格中输入函数=LEFT(A1,2),则A2单元格显示的内容是______。
关系代数运算是以集合操作为基础的运算,其5种基本运算是并、差、(57)、投影和选择。
在Excel2007中,利用填充柄可以将数据复制到相邻单元格中。若选择含有数值的上下相邻的两个单元格,按住鼠标左键向下拖动填充柄,则数据将以(49)________________填充。
在PowerPoint中,下列关于自定义放映的叙述不正确的是(63)。
下图主板接口中,①处是(28),②处可以接的设备是(29),③处可以接的设备是(30)30.
为什么一般处理“震荡波”病毒时,首先要把被侵入的计算机系统从网络上断开?在计算机系统发现病毒并清除以后,在未接入网络之前,从安全方面考虑,若需重新安装操作系统,通常需要执行以下几项主要工作后,方可接入网络。请给出下列工作的合理顺序。A.安装操作
ASP是(1)网页制作技术。A.动态B.静态从以下备选答案内为程序中(5)~(9)处空缺部分选择正确答案。(5)A.CreatObjectB.ConnectC.ExecuteSQLD.Open()(6)A.<body>
随机试题
为了确诊,还应做主诉牙的治疗设计如下,除外
痛痹的临床特征是
妇女生殖器官疾病的保健的关键是()
A.普通处方B.药师处方C.法定处方D.麻醉药品和第一类精神药品处方E.第二类精神药品处方应当添加患者身份证明编号的处方是()。
如果文档中的内容在一页未满的情况下需要强制换页时,最快捷的方法应是()。
根据证券经纪业务主要环节的操作规范,在证券委托买卖方面,以下表述中,错误的是()。
(2008年考试真题)消极型股票投资战略的理论基础在于()。
关于马赫带的说法正确的是()
简述1947年《中华民国宪法》的内容,并作简要评价。
Geographyisthestudyoftherelationshipbetweenpeopleandtheland.Geographers(地理学家)compareandcontrast【C1】______placeso
最新回复
(
0
)