●试题三阅读下列函数说明和C函数，将应填入(n)处的字句写在答题纸的对应栏内。【函数3说明】函数DeleteNode(Bitree*r,int e)的功能是：在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点，若删除成功，则函数返回0，否则函数返回-1。二叉查找树结点的类型定义为：typedef struct Tnode{int data;/*结点的键值*/struct Tnode*Lchild,*Rchild;/*指向左、右子树的指针*/}*Bitree;在二叉查找树上删除一个结点时，要考虑三种

阅读下列函数说明和C函数，将应填入______处的语句写在答题纸的对应栏内。

[函数6说明]

函数DelA_InsB(LinkedList La，LinkedList Lb，int key1，int key2，int len)的功能是：将线性表A中关键码为key1的结点开始的len个结点，按原顺序移至线性表B中关键码为key2的结点之前，若移动成功，则返回0；否则返回-1。线性表的存储结构为带头结点的单链表，La为表A的头指针，Lb为表B的头指针。单链表结点的类型定义为：

typedef struct node {

int key；

struct node * next；

} * LinkedList；

[函数6]

int DelA InsB(LinkedList La，LinkedList Lb，int key1，int key2，int len)

{ LinkedListp，q，s，prep，pres；

int k；

if(! La-＞next‖! Lb-＞next‖-＞next‖len＜＝0)return－1；

p=La-＞next；prep=La；

while(p&&p-＞key!=key1){ / * 查找表A中键值为key1的结点 * /

prep=p；p=p-＞next；

}

if(! p)return -1； / * 表A中不存在键值为key1的结点 * /

q＝p；k=1；

while(q&& (1) ){ / * 在表A中找出待删除的len个结点 * /

(2)；k++；

}

if(! q)return-1： / * 表A中不存在要被删除的len个结点 * /

s=Lb-＞next； (3)；

while(s s && s-＞key!=key2){ / * 查找表B中键值为key2的结点 * /

pres=s；s=s-＞next；

}

if(! s)return-1； / * 表B中不存在键值为key2的结点 * /

(4)=q-＞next； / * 将表A中的len个结点删除 * /

q-＞next=(5)；

pres-＞next=p； / * 将len个结点移至表B * /

return 0；

}

阅读下列C函数和函数说明，将应填入(n)处的字句写在对应栏内。

【说明】

函数DeleteNode (Bitree *r, int e)的功能是：在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点，若删除成功，则函数返回0，否则函数返回-1。二叉查找树结点的类型定义为：

typedef struct Tnode{

int data； /*结点的键值*/

struct Tnode *Lchild, *Rchild； /*指向左、右子树的指针*/

}*Bitree：

在二叉查找树上删除一个结点时，要考虑3种情况：

①若待删除的结点p是叶子结点，则直接删除该结点；

②若待删除的结点p只有一个子结点，则将这个子结点与待删除结点的父结点直接连接，然后删除结点p；

③若待删除的结点p有两个子结点，则在其左子树上，用中序遍历寻找关键值最大的结点s，用结点s的值代替结点p的值，然后删除结点s，结点s必属于上述①、②情况之一。

【函数】

int DeleteNode (Bitree *r，int e) {

Bitree p=*r,pp，s，c；

while ( (1) ){ /*从树根结点出发查找键值为e的结点*/

pp=p;

if(e＜p-＞data) p=p-＞Lchild；

else p=p-＞Rchild；

}

if(!P) return-1； /*查找失败*/

if(p-＞Lchild && p-＞Rchild) {/*处理情况③*/

s=(2)；pp=p

while (3) {pp=s；s=s-＞Rchild;}

p-＞data=s-＞data； p=s；

}

/*处理情况①、②*/

if ( (4) ) c=p-＞Lchild；

else c=p-＞Rchild；

if(p==*r) *r=c；

else if ( (5) ) pp-＞Lchild=c；

else pp-＞Rchild=c；

free (p)；

return 0；

}

试题四

阅读下列函数说明和C函数，将应填入 （n） 处的字句写在答题纸的对应栏内。

[函数说明]

函数DeleteNode(Bitree *r,int e)的功能是：在树根结点指针为r的二叉查找（排序）树上删除键值为e的结点，若删除成功，则函数返回0，否则函数返回-1。二叉查找树结点的类型定义为：

typedef struct Tnode{

int data;

struct Tnode *Lchild,*Rchild;

}*Bitree;

在二叉查找树上删除一个结点时，要考虑三种情况：

1若待删除的结点p是叶子结点，则直接删除该结点；

2若待删除的结点p只有一个子结点，则将这个子结点与待删除结点的父结点直接连接，然后删除结点p；

3若待删除的结点p有两个子结点，则在其左子树上，用中序遍历寻找关键值最大的结点s,用结点s的值代替结点p的值，然后删除结点s,结点s必属于上述1、2情况之一。

[函数代码]

int DeleteNode(Bitree *r,int e) {

Bitreep = *r, pp, s, c;

while( (1) ) { /*从树根结点出发查找键值为e的结点*/

pp = p;

if ( e< p->data) p = p -> Lchild;

else p = p->Rchild;

}

if(!p) return –1; /* 查找失败 */

if(p->Lchild && p->Rchild) { /* 处理情况3 */

s = (2);pp = p;

while ( (3) ) { pp = s; s = s-> Rchild; }

p->data = s ->data; p = s;

}

/*处理情况1、2*/

if( (4) ) c = p -> Lchild;

elsec = p -> Rchild;

if(p == *r) *r = c;

elseif ( (5) ) pp -> Lchild = c;

elsepp->Rchild = c;

free(p);

return 0;

}

阅读下列函举说明和C代码，将应填入(n)处的字句写在对应栏内。

【说明4.1】

假设两个队列共享一个循环向量空间(如图1-2所示)，其类型Queue2定义如下：

typedef struct {

DateType data [MaxSize];

int front[2],rear[2];

}Queue2;

对于i=0或1，front[i]和rear[i]分别为第i个队列的头指针和尾指针。函数．EnQueue (Queue2*Q，int i，DaleType x)的功能是实现第i个队列的入队操作。

【函数4.1】

int EnQueue(Queue2 * Q, int i, DateType x)

{ /*若第i个队列不满，则元素x入队列，并返回1；否则，返回0*/

if(i＜0‖i＞1) return 0;

if(Q-＞rear[i]==Q-＞front[(1)]

return 0;

Q-＞data[(2)]=x;

Q-＞rear[i]=[(3)];

return 1;

}

【说明4.2】

函数BTreeEqual(BinTreeNode*T1，BinTtneNode*T2)的功能是递归法判断两棵二叉树是否相等，若相等则返回1，否则返回0。函数中参数T1和T2分别为指向这两棵二叉树根结点的指针。当两棵树的结构完全相同，并且对应结点的值也相同时，才被认为相等。

已知二叉树中的结点类型BinTreeNode定义为：

struct BinTreeNode {

char data;

BinTreeNode * left, * right;

};

其中dau为结点值域，leR和risht分别为指向左、右子女结点的指针域，

【函数4.2】

int BTreeEqual(BinTreeNode * T1, BinTreeNode * T2)

{

if(Ti == NULL && T2 == NULL)return 1 /*若两棵树均为空，则相等*/

else if((4))return 0; /*若一棵为空一棵不为空，则不等*/

else if((5)) return 1; /*若根结点值相等并且左、右子树*/

/*也相等，则两棵树相等，否则不等*/

else return 0;

}

阅读下列说明和c函数代码，将应填入 (n) 处的字句写在答题纸的对应栏内。

【说明】

对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点，且每个结点仅访问一次的过程。函数InOrder。()借助栈实现二叉树的非递归中序遍历运算。

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

typedef struct BtNode{

ElemTypedata； ／*结点的数据域，ElemType的具体定义省略*／

struct BtNode*ichiid，*rchild； ／*结点的左、右弦子指针域*／

)BtNode，*BTree；

在函数InOrder()中，用栈暂存二叉树中各个结点的指针，并将栈表示为不含头结点

的单向链表(简称链栈)，其结点类型定义如下：

typedef struct StNode{ ／*链栈的结点类型*／

BTree elem； ／*栈中的元素是指向二叉链表结点的指针*／

struct StNode*link；

}S％Node；

假设从栈顶到栈底的元素为en、en-1、…、e1，则不含头结点的链栈示意图如图5—5

所示。

【C函数】

int InOrder(BTree root) ／*实现二叉树的非递归中序遍历*／

{

BTree ptr； ／*ptr用于指向二又树中的结点*／

StNode*q； ／*q暂存链栈中新创建或待删除的结点指针+／

StNode*stacktop=NULL； ／*初始化空栈的栈顶指针stacktop*／

ptr=root； ／*ptr指向二叉树的根结点*／

while( (1 ) I I stacktop!=NULL){

while(ptr!=NULL){

q=(StNode*)malloc(sizeof(StNode))；

if(q==NULL)

return-1；

q->elem=ptr；(2) ；

stacktop=q； ／*stacktop指向新的栈顶*／

ptr=(3 ) ； ／*进入左子树*／

}

q=stacktop； (4) ； ／*栈顶元素出栈*／

visit(q)； ／*visit是访问结点的函数，其具体定义省略*／

ptr= (5) ； ／*进入右子树*／

free(q)； ／*释放原栈顶元素的结点空间*／

}

return 0；

}／*InOrder*／

阅读下列函数说明和C代码，将应填入(n) 处的字句写在对应栏内。

【说明】

函数print(BinTreeNode*t; DateType &x)的功能是在二叉树中查找值为x的结点，并打印该结点所有祖先结点。在此算法中，假设值为x的结点不多于一个。此算法采用后序的非递归遍历形式。因为退栈时需要区分右子树。函数中使用栈ST保存结点指针ptr以及标志tag，Top是栈顶指针。

【函数】

void print( BinTreeNode * t; DateType &x) {

stack ST; int i, top; top = 0;//置空栈

while(t! = NULL &&t-＞ data!= x || top!=0)

{ while(t!= NULL && t-＞ data!=x)

{

/*寻找值为x的结点*/

(1);

ST[top]. ptr = t；

ST[top]. tag = 0;

(2);

}

if(t!= Null && t -＞ data == x) { /*找到值为x的结点*/

for(i=1;(3);i ++)

printf("%d" ,ST[top]. ptr -＞data);

else {

while((4))

top--;

if(top＞0)

{

ST[top]. tag = 1;

(5);

}

}

}

阅读以下说明和C语言函数，将应填入(n)处的字句写在答题纸的对应栏内。

【说明】

一棵非空二叉树中“最左下”结点定义为：若树根的左子树为空，则树根为“最左下”结点；否则，从树根的左子树根出发，沿结点的左

子树分支向下查找，直到某个结点不存在左子树时为止，该结点即为此二叉树的“最左下”结点。例如，下图所示的以 A为根的二叉树的“最

左下”结点为D，以C为根的子二叉树中的“最左下”结点为C。

二叉树的结点类型定义如下：

typedef stmct BSTNode{

int data；

struct BSTNode*lch,*rch；//结点的左、右子树指针

}*BSTree；

函数BSTree Find Del(BSTree root)的功能是：若root指向一棵二叉树的根结点，则找出该结点的右子树上的“最左下”结点*p，并从

树于删除以*p为根的子树，函数返回被删除子树的根结点指针；若该树根的右子树上不存在“最左下”结点，则返回空指针。

【函数】

BSTrce Find_Del(BSTreeroot)

{ BSTreep,pre；

if ( !root ) return NULL； /*root指向的二叉树为空树*/

(1)； /*令p指向根结点的右子树*/

if ( !p ) return NULL；

(2)； /*设置pre的初值*/

while(p-＞lch){ /*查找“最左下”结点*/

pre=p；p=(3)；

}

if ((4)==root) /*root的右子树根为“最左下”结点*/

pre-＞rch=NULL；

else

(5)=NULL； /*删除以“最左下”结点为根的子树*/

reurn p；

}

阅读下列函数说明和C函数，将应填入(n)处的字句写在对应栏内。

[说明]

二叉树的二叉链表存储结构描述如下：

lypedef struct BiTNode

{ datatype data;

street BiTNode *lchiht, *rchild; /*左右孩子指针*/ } BiTNode, *BiTree;

下列函数基于上述存储结构，实现了二叉树的几项基本操作：

(1) BiTree Creale(elemtype x, BiTree lbt, BiTree rbt)：建立并返回生成一棵以x为根结点的数据域值，以lbt和rbt为左右子树的二叉树；

(2) BiTree InsertL(BiTree bt, elemtype x, BiTree parent)：在二叉树bt中结点parent的左子树插入结点数据元素x；

(3) BiTree DeleteL(BiTree bt, BiTree parent)：在二叉树bt中删除结点parent的左子树，删除成功时返回根结点指针，否则返回空指针；

(4) frceAll(BiTree p)：释放二叉树全体结点空间。

[函数]

BiTree Create(elemtype x, BiTree lbt, BiTree rbt) { BiTree p;

if ((p = (BiTNode *)malloc(sizeof(BiTNode)))= =NULL) return NULL;

p-＞data=x;

p-＞lchild=lbt;

p-＞rchild=rbt;

(1);

}

BiTree InsertL(BiTree bt, elemtype x,BiTree parent)

{ BiTree p;

if (parent= =NULL) return NULL;

if ((p=(BiTNode *)malloc(sizeof(BiTNode)))= =NULL) return NULL;

p-＞data=x;

p-＞lchild= (2);

p-＞rchild= (2);

if(parent-＞lchild= =NULL) (3);

else{

p-＞lchild=(4);

parent-＞lchild=p;

}

return bt;

}

BiTree DeleteL(BiTree bt, BiTree parent)

{ BiTree p;

if (parent= =NULL||parent-＞lchild= =NULL) return NULL;

p= parent-＞lchild;

parent-＞lchild=NULL;

freeAll((5));

return bt;

阅读以下函数说明和C语言函数，将应填入(n)处的字句写在对应栏内。

[说明]

已知r[1...n]是n个记录的递增有序表，用折半查找法查找关键字为k的记录。若查找失败，则输出“failure",函数返回值为0；否则输出“success”，函数返回值为该记录的序号值。

[C函数]

int binary search(struct recordtype r[],int n,keytype k)

{ intmid,low=1,hig=n;

while(low＜=hig){

mid=(1);

if(k＜r[mid].key) (2);

else if(k==r[mid].key){

printf("succesS\n");

(3);

}

else (4);

}

printf("failure\n");

(5);

}

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

}

阅读以下说明和C语言函数，将应填入(n)处。

[说明]

二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：若它的左子树非空，则左子树上所有结点的值均小于根结点的值；若它的右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身就是两棵二义排序树。

函数insert_BST(char *str)的功能是：对给定的字符序列按照ASCⅡ码值大小关系创建二叉排序树，并返回指向树根结点的指针。序列中重复出现的字符只建一个结点，并由结点中的Count域对字符的重复次数进行计数。

二叉排序树的链表结点类型定义如下：

typedef struct BSTNode{

char Elem; /*结点的字符数据*/

int Count; /*记录当前字符在序列中重复出现的次数*/

struct BSTNode *Lch,*Rch; /*接点的左、右子树指针*/

}*BiTree;

[函数]

BiTree insert_BST(char *str)

{ BiTree root,parent,p;

char (1); /*变量定义及初始化 */

root=(BiTree)malloc(sizeof(struct BSTNode));

if(!root||*s=='\0') return NULL;

root-＞Lch=root-＞Rch=NULL; foot-＞Count=1; root-＞Elem=*s++;

for(; *s!='\0';s++) {

(2); parent=NULL;

while (p){ /*p从树跟结点出发查找当前字符*s所在结点 */

parent = p;

if(*s==p-＞Elem)/*若树中已存在当前字符结点，则当前字符的计数值加1*/

{p-＞Count++; break;}

else /*否则根据字符*s与结点*p中字符的关系，进入*p的左子树或右子树*/

if (*s＞p-＞Elem) p=p-＞Rch;

else p=p-＞Lch;

}/*while*/

if( (3)) {/* 若树中不存在字符值为*s的结点，则申请结点并插入树中 */

p=(BiTree)malloc(sizeof(struct BSTNode));

if(!p)return NULL;

p-＞Lch=p-＞Rch=NULL; p-＞Count=1; p-＞Elem=*s;

/*根据当前字符与其父结点字符值的大小关系，将新结点作为左子树或右子树插入*/

if(p-＞Elem＞parent-＞Elem) (4)=p;

else (5)=p;

}

}/*for*/

return root；

}

阅读下列函数说明和C函数，将应填入(n)处的字句写在对应栏内。

【说明】

函数DeleteNode(Bitree*r，inte)的功能是：在树根节点指针为r的二叉查找(排序)树上删除键值为e的节点，若删除成功，则函数返回0，否则函数返回-1。二叉查找树节点的类型定义为：

typedef struct Tnode{

int data;/*节点的键值*/

struct Tnode *Lchild,*Rchiid;/*指向左、右子树的指针*/

}*Bitree;

在二叉查找树上删除一个节点时，要考虑3种情况。

①若待删除的节点p是叶子节点，则直接删除该节点。

②若待删除的节点p只有一个子节点，则将这个子节点与待删除节点的父节点直接连接，然后删除节点。

③若待删除的节点p有两个子节点，则在其左子树上，用中序遍历寻找关键值最大的节点 s，用节点s的值代替节点p的值，然后删除节点s，节点s必属于上述①、②情况之一。

【函数5-5】

int DeleteNode(Bitree *r,int e){

Bitree p=*r,pp,s,c;

while( (1) {/*从树根节点出发查找键值为e的节点*/

pp=p;

if(e＜p-＞data)p=p-＞Lchild;

else p=p-＞Rehild;

}

if(!p)retrn -1;/*查找失败*/

if(p-＞Lchild && p-＞Rchild){/*处理情况③*/

s=(2); pp=p;

while( (3)){pp=s;s=s-＞Rchild;}

p-＞data=s-＞data;p=s;

}

/* 处理情况①、②*/

if((4))c=p-＞Lchild;

else c=p-＞Rchild;

if(p== *r)*r=c;

else if((5))pp-＞Lchild=c;

else pp-＞Rchild=c;

free(p);

return 0;

}

阅读下列函数说明和C函数，将应填入(n)处的字句写在对应栏内。

【说明】

函数DelA_InsB(LinkedList La，LinkedList Lb，int key1，int key2，int len)的功能是：将线性表A中关键码为key1的结点开始的len个结点，按原顺序移至线性表B中关键码为key2的结点之前，若移动成功，则返回0；否则返回-1。线性表的存储结构为带头结点的单链表，La为表A的头指针，Lb为表B的头指针。单链表结点的类型定义为

typedef struct node {

int key;

struct node * next;

} *LinkedList;

【函数】

int DelA_InsB ( LinkedList La, LinkdeList Lb,int key1,int key2,,int len)

{ LinkedList p,q,s,prep,pres;

int k;

if( ! La-＞next || ! Lb-＞ next ||| en ＜=0)return-1;

p = La -＞ next;prep = La;

while(p&&p- ＞key != key1) { /*查找表A中键值为key1的结点*/

prep = p;p = p -＞ next;

}

if( ! p) return - 1; /*在表A中不存在键值为key1的结点*/

q=p;k=1;

while(q &&(1))} /*表A中不存在要被删除的len个结点*/

(2);k++;

}

if( ! q)return -1; /*表A中不存在要被删除的len个结点*/

s = Lb -＞ next;(3);

while(s && s -＞ key != key2) { /*查找表B中键值为key2的结点*/

pres =s;s =s-＞next;

}

if( ! s) return - t; /*表B中不存在键值为key2的结点*/

(4)=q-＞ next; /*将表A中的len个结点删除*/

q-＞next=(5);

pres -＞ next = p; /*将len个结点移至表B */

return 0;

}

阅读下列函数说明和C函数，将应填入(n)处。

【函数3说明】

函数DeleteNode(Bitree * r，int e)的功能是：在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点，若删除成功，则函数返回0，否则函数返回-1。二叉查找树结点的类型定义为：

typedef struct Tnode{

int data； /*结点的键值*/

struct Tnode * Lchild，*Rchild； /*指向左、右子树的指针*/

} * Bitree；

在二叉查找树上删除一个结点时，要考虑三种情况：

①若待删除的结点p是叶子结点，则直接删除该结点；

②若待删除的结点p只有一个子结点，则将这个子结点与待删除结点的父结点直接连接，然后删除结点P；

③若待删除的结点p有两个子结点，则在其左子树上，用中序遍历寻找关键值最大的结点s，用结点s的值代替结点p的值，然后删除结点s，结点s必属于上述①、②情况之一。

【函数3】

int DeleteNode(Bitree * r，int e){

Bitree p=*r，pp，s，c；

while((1)){ /*从树根结点出发查找键值为e的结点*/

pp=p；

if(e＜p-＞data)p=p-＞Lchild；

else p=p-＞Rchild；

{

if(!p)return-1； /*查找失败*/

if(p-＞Lchild &&p-＞Rchild){/*处理情况③*/

s=(2)； pp=p；

while((3)){pp=s；s=s-＞Rchild；}

p-＞data=s-＞data；p=s；

}

/*处理情况①、②*/

if((4))c=p-＞Lchild；

else c=p-＞Rchild；

if(p==*r)*r=c；

else if((5))pp-＞Lchild＝c；

else pp-＞Rchild＝c；

free(p)；

return 0；

}

阅读以下说明和C语言函数，将应填入(n)处的字句写在对应栏内。

[说明]

完成以下中序线索化二叉树的算法。

[函数]

Typedef int datatype;

Typedef struct node {

Int ltag, rtag;

Datatype data;

*lchild,* rchild;

}bithptr;

bithptr pre;

void inthread ( p );

{if

{inthread ( p-＞lchild );

if ( p-＞lchild==unll ) (1);

if ( P-＞RCHILD=NULL) p-＞rtag=1;

if (2)

{if (3) pre-＞rchild=p;

if ( p-＞1tag==1 )(4);

}

INTHREAD ( P-＞RCHILD );

(5);

}

}

阅读以下函数说明和C语言函数，将应填入(n)处的字句写在对应栏内。

[说明]

已知一棵二叉树用二叉链表存储，t指向根结点，p指向树中任一结点。下列算法为输出从t到P之间路径上的结点。

[C程序]

define Maxsize 1000

typedef struct node{

TelemType data;

struct node*1child,*rchild;

}BiNode,*BiTree;

void Path(BiTree t,BiNode*P)

{ BiTree*stack[Maxsize],*stackl[Maxsize],*q;

int tag[Maxsize],top=0,topl;

q=t;

/*通过先序遍历发现P*/

do(while(q!=NULL && q!=p)

/*扫描左孩子，且相应的结点不为P*/

{ (1);

stack[top]=q;

tag[top]=0;

(2);

}

if(top＞0)

{ if(stack[top]==P) break; /*找到P，栈底到栈顶为t到P*/

if(tag[top]==1)top--;

else{q=stack[top];

q=q-＞rchild;

tag[top]=1;

}

}

} (3);

top--; topl=0;

while(top＞0){

q=stack[top]; /*反向打印准备*/

topl++;

(4);

top--;

}

while((5)){ /*打印栈的内容*/

q=stackl[topl];

printf(q-＞data);

topl--;

}

}

阅读下列函数说明和C函数，将应填入(n)处的字句写对应栏内。

[说明]

二叉树的二叉链表存储结构描述如下：

typedef struct BiTNode

{ datatype data;

struct BiTNode *lchild, * rchild; /*左右孩子指针*/

}BiTNode,* BiTree;

对二叉树进行层次遍历时，可设置一个队列结构，遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从队首取出一个元素，执行下面两个操作：

(1) 访问该元素所指结点；

(2) 若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队。

此过程不断进行，当队列为空时，二叉树的层次遍历结束。

下面的函数实现了这一遍历算法，其中Visit(datatype a)函数实现了对结点数据域的访问，数组queue[MAXNODE]用以实现队列的功能，变量front和rear分别表示当前队首元素和队尾元素在数组中的位置。

[函数]

void LevelOrder(BiTree bt) /*层次遍历二叉树bt*/

{ BiTree Queue[MAXNODE];

int front,rear;

if(bt= =NULL)return;

front=-1;

rear=0;

queue[rear]=(1);

while(front (2) ){

(3);

Visit(queue[front]-＞data); /*访问队首结点的数据域*/

if(queue[front]—＞lchild!：NULL)

{ rear++;

queue[rear]=(4);

}

if(queue[front]-＞rchild! =NULL)

{ rear++;

queue[rear]=(5);

}

}

}

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

【说明】

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

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

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

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

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

typedefstructBiTnode{

intkey_value;/*结点的键值，为非负整数*/

structBiTnode*left,*right;/*结点的左、右子树指针*/

}*BSTree;

函数find_key(root,key)的功能是用递归方式在给定的二叉查找树(root指向根结点)中查找键值为key的结点并返回结点的指针;若找不到，则返回空指针。

【函数】

BSTreefind_key(BSTreeroot,intkey)

{

if((1))

returnNULL;

else

if(key==root->key_value)

return(2);

elseif(keykey_value)

return(3);

else

return(4);

}

【问题1】

请将函数find_key中应填入(1)~(4)处的字句写在答题纸的对应栏内。

【问题2】

若某二叉查找树中有n个结点，则查找一个给定关键字时，需要比较的结点个数取决于(5).

阅读以下说明和 C 代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 【说明】 函数 GetListElemPtr(LinkList L，int i)的功能是查找含头结点单链表的第i个元素。若找到，则返回指向该结点的指针，否则返回空指针。 函数DelListElem(LinkList L，int i，ElemType *e) 的功能是删除含头结点单链表的第 i个元素结点，若成功则返回 SUCCESS ，并由参数e 带回被删除元素的值，否则返回ERROR 。 例如，某含头结点单链表 L 如图 4-1 (a) 所示，删除第 3 个元素结点后的单链表如 图 4-1 (b) 所示。图4-1

define SUCCESS 0 define ERROR -1 typedef int Status; typedef int ElemType; 链表的结点类型定义如下: typedef struct Node{ ElemType data; struct Node *next; }Node ,*LinkList; 【C 代码】 LinkList GetListElemPtr(LinkList L ，int i) { /* L是含头结点的单链表的头指针，在该单链表中查找第i个元素结点: 若找到，则返回该元素结点的指针，否则返回NULL */ LinkList p; int k; /*用于元素结点计数*/ if (i<1 ∣∣ !L ∣∣ !L->next) return NULL; k = 1; P = L->next; / *令p指向第1个元素所在结点*/ while (p && （1） ) { /*查找第i个元素所在结点*/ （2） ; ++k; } return p; } Status DelListElem(LinkList L ，int i ，ElemType *e) { /*在含头结点的单链表L中，删除第i个元素，并由e带回其值*/ LinkList p，q; /*令p指向第i个元素的前驱结点*/ if (i==1) （3） ； else p = GetListElemPtr(L ，i-1); if (!p ∣∣ !p->next) return ERROR; /*不存在第i个元素*/ q = (4) ； /*令q指向待删除的结点*/ p->next = q->next; /*从链表中删除结点*/ (5) ； /*通过参数e带回被删除结点的数据*/ free(q); return SUCCESS; }

●试题一

阅读下列说明和流程图，将应填入(n)的语句写在答题纸的对应栏内。

【流程图说明】

下面的流程(如图1所示)用N-S盒图形式描述了在一棵二叉树排序中查找元素的过程，节点有3个成员：data，left和right。其查找的方法是：首先与树的根节点的元素值进行比较：若相等则找到，返回此结点的地址；若要查找的元素小于根节点的元素值，则指针指向此结点的左子树，继续查找；若要查找的元素大于根节点的元素值，则指针指向此结点的右子树，继续查找。直到指针为空，表示此树中不存在所要查找的元素。

【算法说明】

【流程图】

将上题的排序二叉树中查找元素的过程用递归的方法实现。其中NODE是自定义类型：

typedef struct node{

int data；

struct node*left；

struct node*right；

}NODE；

【算法】

NODE*SearchSortTree(NODE*tree，int e)

{

if(tree!=NULL)

{

if(tree->data<e)

(4) ；∥小于查找左子树

else if(tree->data<e)

(5) ；∥大于查找左子树

else return tree；

}

return tree；

}