判断题在查找树中插入一个新结点，总是插入到叶结点下面。A 对B 错

在平衡的二叉排序树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。()

A.左子树的叶子结点

B.左子树的分支结点

C.右子树的叶子结点

D.右子树的分支结点

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

试题三（共15分）

阅读以下说明和C函数，填充函数中的空缺，将解答填入答题纸的对应栏内。

【说明】

函数Insert _key (*root,key)的功能是将键值key插入到*root指向根结点的二叉查找树中（二叉查找树为空时*root为空指针）。若给定的二叉查找树中已经包含键值为key的结点，则不进行插入操作并返回0；否则申请新结点、存入key的值并将新结点加入树中，返回l。

提示：

二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树：

●若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值；

●若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值；

●左、右子树本身就是二叉查找树。

设二叉查找树采用二叉链表存储结构，链表结点类型定义如下：

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< father->key_value)father->left = s;

elsefather->right = s;

retum 1：

}

此题为判断题(对，错)。

m阶的B树的生成是从空树开始的，逐个插入关键字。每次插入一个结点是向B树______。

A．添加一个叶结点

B．向叶结点添加一个关键字

C．根结点加入一个关键字

D．最低层的某个非终端结点添加一个关键字

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

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

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

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

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