序序列进行排序的过程。【西安电子科技大学1999软件 一、4（2分）】 43．利用树的孩子兄弟表示法存储，可以将一棵树转换为______。【重庆大学 2000 一、9】 44．若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的______序列中的最后一个结点。【武汉大学 2000 一、2】 45．先根次序周游树林正好等同于按______周游对应的二叉树；后根次序周游树林正好等同于______周游对应的二叉树。【山东大学 1999 二、１ (４分)】 46. 在一棵存储结构为三叉链表的二叉树中，若有一个结点是它的双亲的左子女，且它的双亲有右子女，则这个结点在后序遍历中的后继结点是______。【中国人民大学 2001 一、4 （2分）】
47．一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为：______。
【厦门大学 2002 六、1 （4分）】
48．具有n个结点的满二叉树，其叶结点的个数是______。【北京大学 1994】
49．设一棵后序线索树的高是50，结点x是树中的一个结点，其双亲是结点y,y的右子树高度是31，x是y的左孩子。则确定x的后继最多需经过______中间结点（不含后继及x本身）
【南京理工大学 2000 二、8（1.5分）】
50．线索二元树的左线索指向其______，右线索指向其______。
【哈尔滨工业大学 2000 二、3 (2分)】
51．设y指向二叉线索树的一叶子，x指向一待插入结点，现x作为y的左孩子插入，树中标志域为ltag和rtag，并规定标志为1是线索，则下面的一段算法将x插入并修改相应的线索，试补充完整：(lchild,rchild分别代表左，右孩子)
x^.ltag:= (1)___; x^.lchild:= (2)___; y^.ltag:= (3)___; y^.lchild:= (4)___; x^.rtag:= (5)___; x^.rchild:= (6)___;
IF (x^.lchild<>NIL) AND (x^lchild^.rtag=1) THEN x^.lchild^.rchild:= (7)___; 【南京理工大学 1997 三、7 （9分）】 52．哈夫曼树是______。【北京理工大学 2001 七、4 （2）】【 长沙铁道学院 1998 二、3 (2分)】
53．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是______。
【西安电子科技大学2001软件 一、3 （2分）】【厦门大学 2002 六、2（4分）】 54．有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是_(1)__，带权路径长度WPL为_(2)__。【南京理工大学 1999 三、6（4分）】
55．有一份电文中共使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为_(1)__，字符c的编码是_(2)__。【中国矿业大学2000 一、7（3分）】
56．设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有______个结点。
【西安电子科技大学1999软件 一、2（2分）】
57．①二叉树用来表示表达式，因为需要保存各子树的值，修改二叉树的结点结构为(Lchild,Data,Val,Rchild)。其中Lchild,Rchild的意义同前，Val用来存放以该结点为根的子树的值，值的类型依具体情况而定。为了简便起见，算法假定所考虑的表达式只有+，-，*，/ 四种二目运算，且已表示成相应的二叉树。算法所计算的表达式值放在根结点的Val域中。
PROC Postorder-eval(t:ptrType) BEGIN IF (t!=NULL)
BEGIN (1)_______; (2)_______;
CASE t^.data:
‘+’: t^.Val:=t^. Lchild^. Val + t^. Rchild ^. Val; BREAK;
‘-’: t^.Val:=t^. Lchild^. Val - t^. Rchild ^. Val; BREAK; ‘*’: t^.Val:=t^. Lchild^. Val * t^. Rchild ^. Val; BREAK; ‘/’: t^.Val:=t^. Lchild^. Val / t^. Rchild ^. Val; BREAK; otherwise: (3)___; BREAK; ENDCASE END END;
②PROC Delete(x:datatype,A:tree) BEGIN tempA:= (4)___;
WHILE (tempA^.Item!=x) AND (tempA!=NULL) DO
IF (x ELSE BEGIN r:=tempA;tempA:=tempA^.Rchild;END;//tempA为要删结点，r为tempA的父亲 IF (6)___ return(x); IF (tempA^.Lchild!=NULL) AND (tempA^.rchild!=NULL) BEGIN t:=tempA; q:=tempA^.Rchild; WHILE (q^.Lchild!=NULL) DO BEGIN t:=q; q:=q^.Lchild; END; t^.Lchild:= (7)___; //删去q q^.Lchild :=tempA^.Lchild; q^.Rchild:=tempA^.Rchild; IF (tempA^.item< r^.item) r^.Lchild := (8)_ ELSE r^.Rchild:=q //用q代替 tempA END; ELSE IF(tempA^.Lchild!=NULL) IF(tempA^.item ELSE r^.Rchild:=tempA^.Lchild ELSE IF(tempA^.Rchild!=NULL) IF(tempA^.item ELSE r^.Lchild:=tempA^.Rchild ELSE //tempA为树叶 IF(10)_ r^.Lchild:=NULL ELSE r^.Rchild:=NULL END; 【中山大学 1999 四、 (20分)】 58．下面的类PASCAL语言递归算法的功能是判断一棵二叉树（采用二叉链表存贮结构）是否为完全二叉树。请把空缺的两部分补写完整。（提示：利用完全二叉树结点序号性质） TYPE link=^node; node=RECORD key:keytype; l,r:link; END; VAR all:boolean; n:integer; root:link; FUNC num(t:link):integer; BEGIN (1)______END; PROC chk(t:link;m{t 所指结点应有序号}:integer) BEGIN (2)_______END; BEGIN {建二叉树，其根由root指出 } n:=num(root);{求结点数} all:=true; chk(root,1); IF all THEN writeln（‘该树为完全二叉树！’）ELSE writeln （’该树非完全二叉树！’） END； 【北京工业大学 1997 二、2 (10分)】 59．将二叉树bt中每一个结点的左右子树互换的C语言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分别为进队，出队和判别队列是否为空的函数，请填写算法中得空白处，完成其功能。 typedef struct node {int data ; struct node *lchild, *rchild; }btnode; void EXCHANGE(btnode *bt) {btnode *p, *q; if (bt){ADDQ(Q,bt); while(!EMPTY(Q)) {p=DELQ(Q); q=(1)___; p->rchild=(2)___; (3)___=q; if(p->lchild) (4)___; if(p->rchild) (5)___; } } }//【北京科技大学 2000 二、(10分)】 60．设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。N2、NL、NR、N0都是全局量，且在调用count(t)之前都置为0. typedef struct node {int data; struct node *lchild,*rchild;}node; int N2,NL,NR,N0; void count(node *t) {if (t->lchild!=NULL) if (1)___ N2++; else NL++; else if (2)___ NR++; else (3)__ ; if(t->lchild!=NULL)(4)____; if (t->rchild!=NULL) (5)____; } /*call form :if(t!=NULL) count(t);*/ 【上海大学 2000 一、3 (10分)】 61．下面是求二叉树高度的类PASCAL（注：编者略）及类C写的递归算法试补充完整 [说明]（1）考生可根据自己的情况任选一个做（都选不给分) （2）二叉树的两指针域为lchild与rchild, 算法中p为二叉树的根，lh和rh 分别为以p为根的二叉树的左子树和右子树的高，hi为以p为根的二叉树的高，hi最后返回。 height(p) {if ((1)___) {if(p->lchild==null) lh=(2)_______; else lh=(3)_______; if(p->rchild==null) rh=(4)_______; else rh=(5)_______; if (lh>rh) hi=(6)__；else hi=(7)_______; } else hi=(8)_______; return hi; }// 【南京理工大学 1997 三、8 （15分）】 62．二叉树以链方式存储，有三个域，数据域data，左右孩子域lchild,rchild。树根由tree指向 。现要求按层次从上到下，同层次从左到右遍历树。下面算法中用到addx(p)，将指针p进队，delx( )将队头元素返回并退队，notempty在队不空时返回true，否则为false，将算法补充完整: PROC processnode(p); IF(1)_______THEN [write(p＾.data); (2)_______ ] ENDP; PROC trave(tree); write(tree＾.data); (3)_______; WHILE notempty() DO [ r:=delx( ); processnode(r＾.lchild); processnode((4)_______)] ENDP; 【南京理工大学 1999 三、5 （4分）】 63 阅读下列程序说明和程序，填充程序中的______ 【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编者略）。 本程序采用非递归的方法，设立一个堆栈stack存放还没有转换过的结点，它的栈顶指针为tp。交换左、右子树的算法为： （1）把根结点放入堆栈。 （2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。 （3）重复（2）直到堆栈为空时为止。 typedef struct node *tree; struct node{int data; tree lchild,rchild;} exchange(tree t) {tree r,p; tree stack [500]; int tp=0; (1)_______ while (tp>=0) {(2)_______ if((3)_______) {r=p->lchild; p->lchild=p->rchild; p->rchild=r stack[(4)_______]=p->lchild; stack[++tp]=p->rchild; } }} 【中科院自动化研究所 1994 二、2 （15分）】 64．下面使用类pascal语言写的对二叉树进行操作的算法，请仔细阅读 TYPE pointer=^tnodetp; tnodetp=RECORD data: char; llink,rlink: pointer；END; linkstack=^linknodet; linknodet=RECORD data:pointer； next;linkstack；END; PROC unknown (VAR t:pointer); VAR p,temp：pointer; BEGIN p:=t; IF p<> NIL THEN [temp:=p^.llink ；p^.llink:=p^.rlink;；p^.rlink:=temp; unknown(p^.llink); unknown(p^.rlink); ] END; ① 指出该算法完成了什么功能 ② 用栈将以上算法改为非递归算法unknown1,其中有若干语句或条件空缺请在空缺处填写上适当的语句或条件 PROC inistack(VAR s:linkstack); (1)_______; s^.next:=NIL; ENDP; FUNC empty (s:linkstack):boolean; IF (2)_______THEN empty:=true ELSE empty:=false; ENDF; FUNC gettop(s:linkstack):pointer; gettop:= (3)_______; ENDF; FUNC pop(VAR s:linkstack)：pointer; VAR p:linkstack; pop:=s^.next^.data; p:=s^.next; (4)_______；(5)_______; ENDF; PROC push (VAR s:linkstack;x:pointer); VAR p:linkstack; new(p); p^.data:=x; (6)_______; s^.next:=p; ENDP; PROC unknown1(VAR t:pointer); VAR p,temp: pointer; finish: boolean; BEGIN inistack(s); finish:=false; p:=t; REPEAT WHILE p<> NIL DO [temp:=p^.llink; p^.llink:=p^.rlink; p^.rlink:=temp; (7)_______; p:=p^.llink; ]; IF (8)____THEN [p:=gettop(s);temp;=pop(s);] ELSE (9)_______ UNTIL (10)___ ENDP; 【北方交通大学 2000 三、 (25分)】 65．具有n个结点的完全二叉树，已经顺序存储在一维数组A[1..n]中，下面算法是将A中顺序存储变为二叉链表存储的完全二叉树。请填入适当的语句在下面的_______上，完成上述算法。 TYPE ar=ARRAY[1..n] OF datatype; pointer=RECORD data:datatype; lchild, rchild: pointer; END; PROCEDURE btree(VAR a: ar; VAR p:pointer); VAR i:integer; PROCEDURE createtree(VAR t: pointer;i: integer) BEGIN (1)_______; t^.data=a[i]; IF(2)_____THEN creattree((3)_______) ELSE t^.lchild:=NIL; IF(4)_____THEN createtree((5)_______) ELSE t^.rchild:=NIL; END; BEGIN j:= (6)__; createtree(p,j) END; 【北京邮电大学 1998 五、 (15分)】 66．设一棵二叉树的结点定义为 A struct BinTreeNode{ B C D E F