（b）或者是由一个根和两个互不相交的、称为左子树和右子树的二叉树组成。 【中科院自动化所1995一、2（6分）】
42. 在中序线索二叉树中，每一非空的线索均指向其祖先结点。【合肥工业大学 2000 二、5 （1分）】 43. 线索二叉树的优点是便于是在中序下查找前驱结点和后继结点。
【上海海运学院1995 ,96,97 一、7（1分）】 44. 二叉树中序线索化后，不存在空指针域。【青岛大学 2000 四、3 （1分）】 45．霍夫曼树的结点个数不能是偶数。【北京邮电大学 2000 一、6 （1分）】 46. 一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。【合肥工业大学2000二、4 (1分)】 47. 哈夫曼树无左右子树之分。【青岛大学 2000 四、8 （1分）】
48．当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。【南京航空航天大学 1995 五、6 （1分）】
49．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
【北京邮电大学 1999 二、5 （2分）】
50. 用链表（llink-rlink）存储包含n个结点的二叉树时，结点的2n个指针区域中有n+1个空指针。( )
【上海海运学院 1999 一、6（1分）】
三、填空题
1．二叉树由_(1)__，__(2)_，_(3)__三个基本单元组成。【燕山大学 1998 一、5 （3分）】 2．树在计算机内的表示方式有_(1)__，_(2)__，_(3)__。【哈尔滨工业大学 2000 二、4 (3分)】 3．在二叉树中，指针p所指结点为叶子结点的条件是______。【合肥工业大学1999 三、7（2分）】
4．中缀式a+b*3+4*（c-d）对应的前缀式为__(1)_，若a=1，b=2，c=3，d=4，则后缀式db/cc*a-b*+的运算结果为_(2)__。【西南交通大学 2000 一、6】
5．二叉树中某一结点左子树的深度减去右子树的深度称为该结点的____。【燕山大学1998一、9(1分)】 6．具有256个结点的完全二叉树的深度为______。【燕山大学 1998 一、4 （1分）】
7．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有______个叶子结点。【厦门大学 2000 六、2 （16%/3分）】
8．深度为k的完全二叉树至少有___(1)____个结点，至多有___(2)____个结点。
【厦门大学 2001 一、4 （14%/5分）】 【南京理工大学 1999 二、5 （4分）】 9．深度为H 的完全二叉树至少有_(1)__个结点；至多有_(2)__个结点；H和结点总数N之间的关系是 (3)__。
【中科院计算所1998 一、3（3分）1999 二、4（3分）】【中国科技大学 1998 一、3(4分）】 10．在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。
【厦门大学 2002 六、3 （4分）】
11．在完全二叉树中，编号为i和j的两个结点处于同一层的条件是______。
【合肥工业大学 2000 三、6 （2分）】
12．一棵有n个结点的满二叉树有__(1)_个度为1的结点、有__(2)_个分支 （非 终端）结点和__(3)_个叶子，该满二叉树的深度为_(4)__。【华中理工大学 2000 一、6 （3分）） 13．假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是______。
【北方交通大学 2001 二、1】
14．在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =______
【北方交通大学 2001 二、6】【南京理工大学 1999 二、4 （2分）】 15．设只含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为______,最小结点数为______。【北京大学 1997 一、1 （4分）】
16．设有N个结点的完全二叉树顺序存放在向量A[1:N]中，其下标值最大的分支结点为______。
【 长沙铁道学院 1997 二、3 (2分)】
17．高度为K的完全二叉树至少有______个叶子结点。【合肥工业大学 1999 二、6（2分）】 18．高度为8的完全二叉树至少有______个叶子结点。【合肥工业大学 2001 三、6（2分）】 19．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是______。
【厦门大学 2002 六、4（4分）】
20．一个有2001个结点的完全二叉树的高度为______。【南京理工大学 1997 三、2（1分）】
21．设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有__(1)_个结点，右子树中有_(2)__个结点。
【南京理工大学 2000 二、9（3分）】
22．一个深度为k的，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依此对结点编号，则编号最小的叶子的序号是__(1)_；编号是i的结点所在的层次号是_(2)__（根所在的层次号规定为1层）。【南京理工大学 2001 二、2（2分）】
23．如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为______。
【南京理工大学 2001 二、3（2分）】
24．如果结点A有 3个兄弟，而且B是A的双亲，则B的度是______。
【西安电子科技大学1999软件 一、4（2分）】
25．高度为h的2-3树中叶子结点的数目至多为______。【西安电子科技大学1999软件 一、6（2分）】 26．完全二叉树中，结点个数为n，则编号最大的分支结点的编号为______。
【北京轻工业学院 2000 一、3 (2分)】
27．设一棵完全二叉树叶子结点数为k,最后一层结点数>2，则该二叉树的高度为______。
【北京科技大学 1998 一、3】
28．对于一个具有n个结点的二元树，当它为一棵_(1)_二元树时具有最小高度，当它为一棵_(2)_时，具有最大高度。【哈尔滨工业大学 2001 一、3 (2分)】
29．具有N个结点的二叉树，采用二叉链表存储，共有______个空链域。【重庆大学 2000 一、8】 30．8层完全二叉树至少有______个结点，拥有100个结点的完全二叉树的最大层数为______。
【西南交通大学 2000 一、1】
31．含4个度为2的结点和5个叶子结点的二叉树，可有______个度为1的结点。
【北京工业大学 2001 一、6 (2分)】
32．一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶结点数为______。【山东大学 2001 三、2 (2分)】
33． n（n大于1）个结点的各棵树中，其深度最小的那棵树的深度是_(1)__。它共有_(2)__个叶子结点和_(3)__个非叶子结点，其中深度最大的那棵树的深度是_(4)__，它共有_(5)__个叶子结点和_(6)__个非叶子结点。【山东大学 2001 三、7 (2分)】
34． 每一棵树都能唯一的转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，对称序列是FEBGCHD，则它的后序序列是_(1)__。设上述二叉树是由某棵树转换而成，则该树的先根次序序列是_(2)__。【山东工业大学 1997 二、 (6分)】
35．先根次序周游树林正好等同于按_(1)__周游对应的二叉树，后根次序周游树林正好等同于按__(2)_周游对应的二叉树。【山东工业大学 1999 二、1 （4分）】 36．二叉树结点的对称序序列为A,B,C,D,E,F,G,后序序列为B,D,C,A,F,G,E,则该二叉树结点的前序序列为_(1)__,则该二叉树对应的树林包括_(2)__棵树。【北京大学 1997 一、2 （4分）】
37．二叉树的先序序列和中序序列相同的条件是______。 【合肥工业大学 2000 三、7（2分）】
38．已知一棵二叉树的前序序列为abdecfhg,中序序列为dbeahfcg，则该二叉树的根为_(1)__，左子树中有_(2)__， 右子树中有_(3)__。【南京理工大学 1996 二、1（6分）】
39．设二叉树中每个结点均用一个字母表示，若一个结点的左子树或右子树为空，用 ．表示，现前序遍历二叉树，访问的结点的序列为ABD.G...CE.H..F．．，则中序遍历二叉树时，访问的结点序列为_(1)__;后序遍历二叉树时，访问的结点序列为_(2)__。【南京理工大学 1999 二、3（4分）】 40．已知二叉树前序为ABDEGCF，中序为DBGEACF，则后序一定是____。【青岛大学2000 六、3(2分）】 41．现有按中序遍历二叉树的结果为abc，问有_(1)__种不同的二叉树可以得到这一遍历结果，这些二叉树分别是_(2)__。【中国矿业大学 2000 一、5（3分）】
42．一个无序序列可以通过构造一棵______树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。【西安电子科技大学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,其中有若干语句或条件空缺请在空缺处填写上适当的语句或条件