向一棵B树插入关键码的过程中,若最终引起树根结点的分裂,则新树比原树的高度减少1。()

题目
判断题
向一棵B树插入关键码的过程中,若最终引起树根结点的分裂,则新树比原树的高度减少1。()
A

B

如果没有搜索结果或未解决您的问题,请直接 联系老师 获取答案。
相似问题和答案

第1题:

已知二叉树T的结点形式为(lling,data,count,rlink),在树中查找值为X的结点,若找到,则记数(count)加1,否则,作为一个新结点插入树中,插入后仍为二叉排序树,写出其非递归算法。


参考答案:
  [算法描述]
  void SearchBST(BiTree &T,int target){
  BiTree s,q,f; //以数据值target,新建结点s
  s=new BiTNode;
  s->data.x=target;
  s->data.count=0;
  s->lchild=s->rchild=NULL;
  if(!T){
  T=s;
  return ;
  } //如果该树为空则跳出该函数
  f=NULL;
  q=T;
  while (q){
  if (q->data.x==target){
  q->data.count++;
  return ;
  } //如果找到该值则计数加一
  f=q;
  if (q->data.x>target) //如果查找值比目标值大,则为该树左孩子
  q=q->lchild;
  else //否则为右孩子
  q=q->rchild;
  } //将新结点插入树中
  if(f->data.x>target)
  f->lchild=s;
  else
  f->rchild=s;
  }

第2题:

当向一棵m阶的B—树做插入操作时,若一个结点中的关键字个数等于______,则必须分裂为2个结点。

A.m

B.m-1

C.m+l

D.[m/2]


正确答案:A

第3题:

下面关于B树运算的叙述中,正确的是

A.若插入过程中根结点发生分裂,则B树的高度加1

B.每当进行插入运算,就往B树的最下面一层增加一个新结点

C.若要删除的关键码出现在根结点中,则不能真正删除,只能做标记

D.删除可能引起B树结点个数减少,但不会造成B树高度减小


正确答案:A

第4题:

阅读以下说明和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所示。图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*/


正确答案:father=(void*)0 
keyword!=p->key
p
sizeof(BSTNode)
*rootptr
father->left=p
father->right=p 

第5题:

以下关于B树运算的叙述中,哪一条是正确的?

A.若插入过程中根节点发生分裂,则B树的高度加1

B.每当进行插入运算,就在B树的最下面一层增加一个新节点

C.若要删除的关键码出现在根节点中,则不能真正删除,只能做标记

D.删除可能引起B树节点个数减少,但不会造成B树高度减少


正确答案:A
解析:如果插入过程中根节点发生分裂,由于根节点没有双亲,这时就要建立一个新的根节点,整个B树增加了一层。

第6题:

以下关于B树运算的叙述中,哪一条是正确的?

A.若插入过程中根结点发生分裂,则B树的高度加1

B.每当进行插入运算,就在B树的最下面一层增加一个新结点

C.若要删除的关键码出现在根结点中,则不能真正删除,只能做标记

D.删除可能引起B树结点个数减少,但不会造成B树高度减少


正确答案:A
解析:如果插入过程中根结点发生分裂,由于根结点没有双亲,这时就要建立一个新的根结点,整个B树增加了一层。

第7题:

当向一棵m阶的B-树做插入操作时,若一个结点中的关键字个数等于______,则必须分裂为2个结点。

A.m

B.m-1

C.m+1

D.m/2


正确答案:A

第8题:

以下关于B树运算的叙述中,哪一条是正确的?

A.若插入过程中根结点发生分裂,则B树的高度加1

B.每当进行插入运算,就在B树的最下面一层增加一个新结点

C.若要删除的关键码出现在根结点中,则不能真正删除,只能做标记

D.删除可能引起B树结点个数减少,但不会造成B树高度减小


正确答案:C

第9题:

阅读下列说明、图和C代码。

[说明5-1]

B树是一种多叉平衡查找树。一棵m阶的B树,或为空树,或为满足下列特性的m叉树:

①树中每个结点最多有m棵子树;

②若根结点不是叶子结点,则它至少有两棵子树;

⑧除根之外的所有非叶子结点至少有[m/2]棵子树;

④所有的非叶子结点中包含下列数据信息:

(n,A0,K1,A1,K2,A2, …,Kn,An)其中:Ki(i=1,2,…,n)为关键字,且Ki<Ki+1(i=1,2,…,n-1);Ai(i=0,1,…,n)为指向子树根结点的指针,且指针Ai-1,所指子树中所有结点的关键字均小于Ki,Ai+1,所指子树中所有结点的关键字均大于Ki,n为结点中关键字的数目。

⑤所有的叶子结点都出现在同一层次上,并且不带信息(可以看作是外部结点或查找失败的结点,实际上这些结点不存在,指向这些结点的指针为空)。

例如,一棵4阶B树如下图所示(结点中关键字的数目省略)。

B树的阶M、bool类型、关键字类型及B树结点的定义如下:

define M 4 /*B树的阶*/

typedef enum {FALSE=0,TRUE=1}bool;

typedef int ElemKeyType;

typedef struct BTreeNode {

int numkeys; /*结点中关键字的数日*/

struct BTreeNode*parent; /*指向父结点的指针,树根的父结点指针为空*/

struct BTreeNode *A[M]; /*指向子树结点的指针数组*/

ElemKeyType K[M]; /*存储关键字的数组,K[0]闲置不用*/

}BTreeNode;

函数SearchBtree(BTreeNode*root,ElemKcyTypeakey,BTreeNode:*pb)的功能是:在给定的一棵M阶B树中查找关键字akey所在结点,若找到则返回TRUE,否则返回 FALSE。其中,root是指向该M阶B树根结点的指针,参数ptr返回akey所在结点的指针,若akey不在该B树中,则ptr返回查找失败时空指针所在结点的指针。例如,在上图所示的4阶B树中查找关键字25时,ptr返回指向结点e的指针。

注;在结点中查找关键字akey时采用二分法。

[函数5-1]

bool SearchBtree(BTreeNode* root, ElemKeyType akey, BTreeNode **ptr)

{

int lw, hi, mid;

BTreeNode*p = root;

*ptr = NULL;

while ( p ) {

1w = 1; hi=(1);

while (1w <= hi) {

mid = (1w + hi)/2;

if (p -> K[mid] == akey) {

*ptr = p;

return TRUE;

}

else

if ((2))

hi=mid - 1;

else

1w = mid + 1;

}

*ptr = p;

p = (3);

}

return FALSE;

}

[说明5-2]

在M阶B树中插入一个关键字时,首先在最接近外部结点的某个非叶子结点中增加一个关键字,若该结点中关键字的个数不超过M-1,则完成插入;否则,要进行结点的“分裂”处理。所谓“分裂”,就是把结点中处于中间位置上的关键字取出来并插入其父结点中,然后以该关键字为分界线,把原结点分成两个结点。“分裂”过程可能会一直持续到树根,若树根结点也需要分裂,则整棵树的高度增加1。

例如,在上图所示的B树中插入关键字25时,需将其插入结点e中。由于e中已经有3个关键字,因此将关键字24插入结点e的父结点b,并以24为分界线将结点e分裂为e1和e2两个结点,结果如下图所示。

函数Isgrowing(BTreeNode*root,ElemKeyTypeakey)的功能是:判断在给定的M阶B树中插入关键字akey后,该B树的高度是否增加,若增加则返回TRUE,否则返回FALSE。其中,root是指向该M阶B树根结点的指针。

在函数Isgrwing中,首先调用函数SearchBtree(即函数5-1)查找关键字akey是否在给定的M阶B树中,若在,则返回FALSE(表明无需插入关键字akey,树的高度不会增加);否则,通过判断结点中关键字的数目考查插入关键字akey后该B树的高度是否增加。

[函数5-2]

bool Isgrowing(BTreeNode* root, ElernKeyType akey)

{ BTreeNode *t, *f;

if( !SearchBtree((4) )


正确答案:(1)p->numkeys;或其等价形式 (2)p->K[mid]>akey或其等价形式 (3)p->A[hi]或p->A[1w-1]或其等价形式 (4)rootakey&f (5)t&&t->numkeys==M-1或其等价形式
(1)p->numkeys;或其等价形式 (2)p->K[mid]>akey,或其等价形式 (3)p->A[hi],或p->A[1w-1],或其等价形式 (4)root,akey,&f (5)t&&t->numkeys==M-1,或其等价形式 解析:本题考查C程序设计。
B树是一种多叉平衡查找树,由B树的定义可知,在B树上进行查找的过程是:首先在根结点所包含的关键字中查找给定的关键字,若找到则成功返回:否则确定待查找的关键字所在的子树并继续进行查找,直到查找成功或查找失败(指针为空)为止。树的内部结点中关键字存储在数组中并按照递增顺序排列,因此可以用二分法查找某个关键字是否在指定的结点中。
二分法查找元素的过程是:首先令待查找的元素与查找表中间位置上的元素进行比较,若相等,则查找成功,否则,根据待查元素与表中间位置元素的大小关系,下一步到查找表的前半区间或后半区间继续进行二分查找。如果在确定的任何一个子区间都找不到指定的元素,则确定查找失败。若查找区间用一对下标1w和hi确定,则1w≤hi表示有效的查找区间,查找失败时所确定的查找区间为1w>hi。
例如,上图中的结点c包含了关键字60、70、80,那么在c结点中找不到元素65,由于65介于60和70之间,因此下一步必将进入h结点继续查找。
每个结点中的关键字数目由BTreeNode中的numkeys域表示,结点中的查找表存储在数组K[]中,由于下标0未用,因此numkeys个关键字存储在K11)~K[numkeys]中。显然开始在p所指向的结点中进行查找时,确定查找表的下标为1和结点的numkeys域,因此函数5-1的空(1)处应填入“p->numkeys”。
若用1w和hi指示出查找区间,则由于查找表元素的递增排列特性,当待查找的元素小于表中间位置的元素时,下一步应在前半区间查找,即查找区间的一对下标为1w、 mid-1,也就是说函数5-1的空(2)处应填入“akeyp->K[mid]。
如果在当前结点中找不到指定的关键字akey,则1w>hi,由结点中的指针A[hi]或 A[1w-1]指示出下一层的子树结点,因此函数5-1的空(3)处应填入“p>A[hi]”或“p-> A[1w-1]”。
下面分析函数5-2的功能及运算过程。函数5-2用于判断在B树中插入一个关键字时,树的高度是否增加。若指定的关键字已经在B树的某结点中,就不需要插入该关键字,显然树也不会长高。
实现函数调用时实参要向形参传递信息,C语言采取传值调用方式,根据实参向形参的值传递原则,函数4-2中的空(4)处应填入“root,akey,&f"。
根据题目中给出的描述,在M阶B树中插入一个关键字时,首先在最接近外部结点的某个非叶子结点中增加一个关键字,若该结点中关键字的个数不超过M-1,则完成插入;否则,要进行结点的“分裂”处理。所谓“分裂”,就是把结点中处于中间位置上的关键字取出来并插入其父结点中,然后以该关键字为分界线,把原结点分成两个结点。“分裂”过程可能会一直持续到树根,若树根结点也需要分裂,则整棵树的高度增加1。
显然考查插入关键字akey后树的高度是否增加,只需沿其祖先结点关系一直考查直到树根为止,判断依据就是每个待考查的结点中目前已有的关键字个数,因此函数5-2中的空(5)处应填入“t&&t->numkeys==M-1”。

第10题:

下面关于B树运算的叙述中,正确的是

A.若插入过程甲根结点发生分裂,则B树的高度加1

B.每当进行插入运算,就往B树的最下面一层增加一个新结点

C.若要删除的关键码出现在根结点中,则不能真正删除,只能做标记

D.删除可能引起B树结点个数减少,但不会造成B树高度减小


正确答案:A
解析:在B树里插入一个关键码的方法是:对于叶结点处于第i层的B树,插入的关键码总是在第i-1层。若i-1已满,则须把结点分裂为两个,并把中间的一个关键码插到结点的双亲结点上,若双亲结点也是满的,就需要再分裂再向上插。删除过程也类似。每当进行插入运算,就往B数的i-1增加一个新结点;若要删除的关键码出现在根结点中时,将把根结点与它的子女合并,形成新的结点;删除不但可能引起B树结点个数减少,而且会造成B树高度减小。

更多相关问题