首页
登录
从业资格
阅读以下说明和C代码,填补代码中的空缺,将解答填入答题纸的对应栏内。 【说明】
阅读以下说明和C代码,填补代码中的空缺,将解答填入答题纸的对应栏内。 【说明】
考试题库
2022-08-02
2
问题
阅读以下说明和C代码,填补代码中的空缺,将解答填入答题纸的对应栏内。【说明】 二叉查找树又称为二叉排序树,它或者是一棵空树,或者是具有如下性质的二叉树。(1)若它的左子树非空,则左子树上所有结点的值均小于根结点的值。(2)若它的右子树非空,则右子树上所有结点的值均大于根结点的值。(3)左、右子树本身就是两棵二叉查找树。 二叉查找树是通过依次输入数据元素并把它们插入到二叉树的适当位置上构造起来的,具体的过程是:每读入一个元素,建立一个新结点,若二叉查找树非空,则将新结点的值与根结点的值相比较,如果小于根结点的值,则插入到左子树中,否则插入到右子树中;若二叉查找树为空,则新结点作为二叉查找树的根结点。 根据关键码序列{46,25,54,13,29,91}构造一个二叉查找树的过程如图4-1所示。
设二叉查找树采用二叉链表存储,结点类型定义如下:typedef int KeyType;typedef struct BSTNode{ KeyType key; struct BSTNode *left,*right;}BSTNode,*BSTree; 图4-1(g)所示二叉查找树的二叉链表表示如图4-2所示。
函数int InsertBST(BSTree *rootptr,KeyType kword)功能是将关键码kword插入到由rootptr指示出根结点的二叉查找树中,若插入成功,函数返回1,否则返回0。【C代码】int lnsertBST(BSTree*rootptr,KeyType kword)/*在二叉查找树中插入一个键值为kword的结点,若插入成功返回1,否则返回0; *rootptr为二叉查找树根结点的指针*/{ BSTree p,father; (1) ; /*将father初始化为空指针*/ p=*rootptr; /*p指向二叉查找树的根节点*/ while(p&& (2) ){ /*在二叉查找树中查找键值kword的结点*/ father=p; if(kword<p->key) p=p->left; else p=p->right;}if( (3) ) return 0; /*二叉查找树中已包含键值kword,插入失败*/ p=(BSTree)malloc( (4) ); /*创建新结点用来保存键值kword*/If(!p)return 0; /*创建新结点失败*/p->key=kword;p->left=NULL;p->right=NULL; If(!father) (5) =p; /*二叉查找树为空树时新结点作为树根插入*/else if(kword<father->key) (6) ; /*作为左孩子结点插入*/else (7) ; /*作右孩子结点插入*/ return 1; }/*InsertBST*/
选项
答案
解析
1)father=0/father=NULL
2)keyword!=p->key
3)p
4)sizeof(BSTNode)
5)*rootptr
6)father->left=p
7)father->right=p
本题考查C程序设计的基本结构和数据结构的实现。
根据二叉查找树的定义,其左子树中结点的关键码均小于树根结点的关键码,其右子树中结点的关键码均大于跟结点的关键码,因此,将一个新关键码插入二叉查找树时,若等于树根或某结点的关键码,则不再插入,若小于树根,则将其插入左子树中,否则将其插入右子树中。
根据注释,空(1)处需将father设置为空指针,应填入“father=NULL”或其等价形式。
空(2)所在语句用于查找新关键码的插入位置,p指向当前结点。查找结果为两种:若找到,则p指向的结点的关键码等于新关键码,若没有找到,则p得打空指针值。因此空(2)处应填入“p->key!=kword”或其等价形式,在得到结果前使得查找过程可以继续,并且用father记录新插入结点的父结点指针。
空(3)处应填入“p”或其等价形式,表明查找到了kword相同的结点,无须在插入该关键码。
空(4)处应填入“sizeof(BSTNODE)”,在申请新结点空间时提供结点所需的字节数。
空(5)处应填入“*rootptr”,使得新结点作为树根结点时,树根结点的指针作为二叉链表的标识能得到更新。
根据注释,空(6)应填入“father->left=p”、空(7)应填入“father->right=p”。
转载请注明原文地址:https://tihaiku.com/congyezige/2427016.html
本试题收录于:
初级程序员题库软件水平考试初中高级分类
初级程序员
软件水平考试初中高级
相关试题推荐
网页中代码"inputtype=textname="foo"size=20
负责解释执行JavaScript代码的是()。A.Web服务器 B.Web浏览
在网页中创建一个如下图所示的表单控件的HTML代码是()。 A.<input
下面的XML代码段中,语法正确的是()。A.<!-xml示例-!><?xml
在网页中创建Email链接,代码正确的是()。A.<ahref=“call
()不是蠕虫病毒。A.冰河 B.红色代码 C.熊猫烧香 D.爱虫病毒
阅读一下说明,回答问题1至问题3,将解答填入答题纸的对应栏内。 【说明】
阅读一下说明,回答问题1至问题4.将解答填入答题纸对应的解答栏内。 【说明】
阅读以下说明,回答问题1至问题4,将解答填入对应的解答栏内。 【说明】
阅读下列说明信息,回答问题1至问题5。将答案填入答题纸对应的解答栏内。 【说明
随机试题
[originaltext]Togetadriver’slicense,youmusttakeaseriesoftests.T
Pub-talkA)Pub-talk,themostpopularactivityinallpubs,isanative
Whatispopculture?Well,popis【C1】______forpopular.Thebeginningofpop
Thesesessionswithacounsellorare______[br][originaltext]COUNSELLORHello,
Becauseofhispoorhealth,ittookhimalongtimetothrow______hisbadcold.
Althougharchitecturehasartisticqualities,itmustalsosatisfyanumberofi
临床上反锁是指A.上后牙舌尖舌斜面位于下后牙颊尖颊斜面的颊侧,面无咬合接触 B
肢体活动的目的不包括A.预防肌肉萎缩 B.预防坠积性肺炎 C.防止关节强直
共用题干 某通信企业推出一种新业务,为给这项业务定价,该企业测算或预计并获得了
下列有关实质性程序的范围的说法中,错误的是( )。A.实施控制测试的结果会影响
最新回复
(
0
)