BEGIN result =true ; p:= l^.link; q:=l^.pre ; WHILE (p<>q) AND ((1)_______)DO
IF p^.data=q^.data THEN BEGIN (2)___; (3)____; END； ELSE result=false ; return(result);
END; 【华南师范大学 2000年 五、1 ( 9分)】
68．下列是先序遍历二叉树的非递归子程序，请阅读子程序（C语言与PASCAL语言过程功
能完全相同，任选其一），填充空格，使其成为完整的算法。 C语言函数： PASCAL语言过程 void example(b) PROCEDURE example(b:btree); btree *b; VAR stack:ARRAY[1..20] OF btree; { btree *stack[20], *p； top:integer; p:btree; int top; BEGIN if (b!=null) IF b<>NIL THEN { top=1; stack[top]=b; BEGIN top:=1; while (top>0) stack[top]:=b; { p=stack[top]; top--; WHILE top>0 DO printf(“%d”,p->data); BEGIN if (p->rchild!=null) p:=stack[top];top:=top-1; {(1)___; (2)___; write(p^.data); } IF p^.rchild<>NIL if (p->lchild!=null) THEN BEGIN (3)___; (4)__; (1)__;(2)_; }}}} END; IF p^,lchild<>NIL THEN BEGIN (3)__; 4)__; END END END END; 【同济大学 2001 三、 (10分)】 69．下述是一个由二叉树的前序序列和中序序列构造该二叉树的算法，其中，数组A[1..n]存放前序序列，数组B[1..n]存放中序序列，s为根结点指针，i,j为树s的前序序列在A[1..n]中的开始位置和结束位置，x,y为树s的中序序列在B[1..n]中的开始位置和结束位置。所生成的二叉树采用二叉链表存储结构，其结点的形式为（lchild,data,rchild）。请在算法的空框中填入适当语句，使其成为一个完整的算法。
PROCEDURE creatBT(i,j,x,y: integer; VAR s: link); VAR k,L: integer; BEGIN s:= NIL; IF(1)__THEN
BEGIN new (s); s^.data:=a[i]; k:=x; WHILE(2)_______DO k:=k+1; L:= (3)____;
IF k=x THEN s^.lchild:=NIL; ELSE(4)_______; IF k=y THEN s^.rchild:=NIL; ELSE(5)_______； END
END; 【西安交通大学 1996 五、1 (9分)】
70．已知中序遍历bt所指二叉树算法如下，s为存储二叉树结点指针的工作栈，请在划线处填入一条所缺语句。
PROC inorder (bt:bitreptr); inistack(s); (1)_______; WHILE NOT empty(s) DO
[WHILE gettop(s)<>NIL DO push(s,gettop(s)↑.lchild); (2)_______;
IF NOT empty(s) THEN [visit (gettop(s)^); p:=pop(s); (3)_______ ] ]
ENDP;{inorder} 【北京轻工业学院 1999 一、 (9分)】
71．以下程序是二叉链表树中序遍历的非递归算法，请填空使之完善。二叉树链表的结点类型的定义如下：
typedef struct node /*C语言/
{char data; struct node *lchild,*rchild;}*bitree;
void vst(bitree bt) /*bt为根结点的指针*/ { bitree p; p=bt; initstack(s); /*初始化栈s为空栈*/
while(p || !empty(s)) /*栈s不为空*/ if(p) { push (s,p); (1)___; } /*P入栈*/
else { p=pop(s); printf(“%c”,p->data); (2)____; } /*栈顶元素出栈*/ } 【西南交通大学 2000 一、10】
72．二叉树存储结构同上题，以下程序为求二叉树深度的递归算法，请填空完善之。
int depth(bitree bt) /*bt为根结点的指针*/ {int hl,hr;
if (bt==NULL) return((1)___);
hl=depth(bt->lchild); hr=depth(bt->rchild); if((2)___) (3)_____； return(hr+1);
} 【西南交通大学 2000 一、11】
73．n个结点的完全二叉树存储在数组a中，下面为非递归的先序遍历算法。
PROC preorder(a); BEGIN top:=0; t:=1;
WHILE (t<=n) OR (1)__ _DO
BEGIN WHILE t<=n DO BEGIN write(a[t]); top:=top+1; s[top]:=t; t:= (2)_;END;
IF top>0 THEN BEGIN t:=s[top]*2+1; top:= (3)__; END; END;
END; 【中山大学 1998 四、3 （6分）】
74．后序遍历二叉树的非递归算法，bt是二叉树的根，S是一个栈，maxsize是栈的最大容量。
TYPE bitreptr=^bnodetp;
bnodetp=RECORD data:datatype; lchild,rchild:bitreptr END; TYPE stacktyp=RECORD data:ARRAY[1..maxsize] OF bitreptr；top：0..maxsize；END； PROCEDURE posterorder（bt：bitreptr）； BEGIN S.top:=0；p:=bt； REPEAT
WHILE p<>NIL DO BEGIN S.top:=S.top+1; IF S.top>maxsize THEN stackfull
ELSE BEGIN S.data[S.top]:=p； (1)__;
END
END;
IF S.data[S.top]^.rchild<>NIL THEN (2)__
ELSE BEGIN REPEAT write (S.data[S.top]^.data); S.top=S.top-1;
UNTIL S.top=0 OR S.data[S.top]^.rchild<>S.data[S.top+1]; IF S.data[S.top]^.rchild<>S.data[S.top+1] THEN (3)__;
END；
UNTIL(4)___;
END； 【西北工业大学 1999 六、1 (7分)】 75．由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。
#define MAX 100 typedef struct Node
{char info; struct Node *llink, *rlink; }TNODE; char pred[MAX],inod[MAX]; main(int argc,int **argv)
{ TNODE *root;
if(argc<3) exit 0;
strcpy(pred,argv[1]); strcpy(inod,argv[2]); root=restore(pred,inod,strlen(pred)); postorder(root); }
TNODE *restore(char *ppos,char *ipos,int n) { TNODE *ptr； char *rpos; int k; if(n<=0) return NULL; ptr->info=(1)_______;
for((2)_______ ; rpos ptr->llink=restore(ppos+1, (4)_______,k ); ptr->rlink=restore ((5)_______+k,rpos+1,n-1-k); return ptr; } postorder(TNODE*ptr) { if(ptr=NULL) return; postorder(ptr->llink); postorder(ptr->rlink); printf(“%c”,ptr->info); } 【中科院计算所 2000 三、 (10分)】 76．已给如下关于二叉树的类型说明： TYPE tree=^node ; node=RECORD data :integer; left ,right:tree END; 以下过程实现对二叉树t前序遍历的非递归算法： PROCEDURE preorder(t:tree ); VAR stack: ARRAY [1..100] OF tree; nd: tree; top: integer; BEGIN top:=1; stack[top]:=t; WHILE(1)___ DO BEGIN nd:=stack[top];top:=top -1; write (nd^.data); IF (nd^.right<>NIL) THEN BEGIN top:=top +1; (2)___ END; IF (3)___THEN BEGIN (4) ；stack[top]:= nd^.left；END END END; 【厦门大学 2000 三、1 （8分）】 77．下面是中序线索树的遍历算法，树有头结点且由指针thr指向。树的结点有五个域，分 别为数据域 data，左、右孩子域 lchild、rchild和左、右标志域 ltag,rtag。规定，标志域为1是线索，O是指向孩子的指针。 inordethread(thr) {p=thr->lchild; while ((1)______) { while((2) _____) p= (3) ___; printf(p->data); while((4)_________) { p=(5)___；printf(p->data);} p= (6)_;} } 【南京理工大学 2000 三、1（6分）】 78．下面的算法在中序线索树中找由指针所指结点的后继并由指针指向该后继结点，试补充完整（线索树的结点有五个域data,lchild,rchild,左、右标志域ltag、rtag，并规定标志0指向孩子，1指向线索。 PROC inorder_next(p); (1)__ ; IF p＾.rtag=0 THEN WHILE(2)____DO q:= (3)___； return(q) ENDP; 【南京理工大学 1998 三、1 （6分）】 79．线索二叉树有数据域data，左右孩子域lchild和rchild，左右标志ltag及rtag，规定标志为1对应的孩子域是线索，0则为指向孩子的指针。规定在储存线索二叉树时，完成下面中序线索化过程。（存储线索二叉树，不增加头结点，只在原有的由tree指向的二叉树中增加线索，此处也不考虑c语言的具体语法与约定，线索化前所有的标志tag都是0）。 /* pre是同tree类型相同的指针，初值是null */ thread_inorder (tree) { if(tree!=null) { thread_inorder((1)____); if(tree->lchild==(2)______) { tree->ltag=1; tree->lchild=pre; } if((3)___ == null){ (4)_______; (5)_______;} pre=p; thread-inorder((6)_______); } } 【南京理工大学 2001 三、5 （6分）】 80．如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法空格处填上正确的语句。设线索二叉树的结点数据结构为(lflag,left,data,right,rflag)，其中： lflag= 0，left 指向其左孩子，lflag= 1，left