小木虫 --- 500万硕博科研人员喜爱的学术科研平台
数据结构第6章例题与答案作者: 收集于网络
7.& 树是结点的有限集合，它（ (1）)根结点，记为T。其余结点分成为m（m>0）个(（2）)的集合T1，T2， …，Ｔm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。一个结点的子结点个数称为该结点的( （3） )。二叉树与树是两个不同的概念，二叉树也是结点的有限集合，它(（4）)根结点。可以把树的根结点的层数定义为1，其他结点的层数等于其父结点所在层数加上1。令T是一棵二叉树，Ki和Kj是T中子结点数小于2的结点中的任意两个，它们所在的层数分别为λKi和λKj，当关系式│λKi-λKj│≤1一定成立时，则称T为一棵（(5)）。供选择的答案：
（1）(4) A. 有0个或1个& B. 有0个或多个& C. 有且只有一个&&& D. 有1个或1个以上
（2） A. 互不相交&& B.允许相交&&&& C.允许叶结点相交& D.允许树枝结点相交
（3） A. 权&&&&&&&& B.维数&&&&&&&& C.次数&&&& &&&&&&&D.序
（5） A. 丰满树&&&& B.查找树&&&&&& C.平衡树&& D.完全树 【上海海运学院1999二、2(5分）】
8．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（& ）
A．9&&&&&&&&&&& B．11&&&&&&&& C．15&& &&&&D．不确定 【北京工商大学2001一.7(3分)】
9．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（&&& ）个
A．4&&&&&&&&&&&& B．5&&&&&&&&& C．6&&&&& D．7 &【哈尔滨工业大学 2001 二、2 （2分）】
10．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（&&& ）。【北方交通大学 2001 一、16 （2分）】
A．M1&&&&&&&&& B．M1+M2&&&&&& C．M3&&&&&&&&&& D．M2+M3
11．具有10个叶结点的二叉树中有（& ）个度为2的结点，【北京航空航天大学2000 一、5（2分)】
A．8&&& &&&&&&&B．9&&&&&&&&&&&& C．10&&&&&&&&& D．ll
12．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（&&& ）【西安交通大学 1996 三、2 (3分)】
A． 250&& B． 500&&& C．254&&&& D．505&&&&& E．以上答案都不对&&&
13. 设给定权值总数有n 个，其哈夫曼树的结点总数为(&&& ) 【福州大学 1998 一、5 (2分)】
A．不确定&&&&&&& B．2n&&&&&&&& C．2n+1&&&&&&&& D．2n-1
14. 有n个叶子的哈夫曼树的结点总数为（&&& ）。【青岛大学 2002 二、1 （2分）】
A．不确定&&&&&&&&& B．2n&&&&&&&&& C．2n+1&&&&&&&&& D．2n-1
15．若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（ ）。【中科院计算所1999一、2（2分）】
A．n-1&& &&&B．&n/m&-1&&&&&& C．é(n-1)/(m-1)ù&&&& D． én/(m-1)ù-1&& E．é(n+1)/(m+1)ù-1
16. 有关二叉树下列说法正确的是（&&& ）【南京理工大学 2000 一、11 （1.5分）】
A．二叉树的度为2&&&&&&&&&&&&&&&&&& B．一棵二叉树的度可以小于2&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
C．二叉树中至少有一个结点的度为2&& D．二叉树中任何一个结点的度都为2
17．二叉树的第I层上最多含有结点数为（& ）
【中山大学1998二、7 （2分）】【北京理工大学 2001 六、5（2分）】
A．2I &&&&&&&&&B． 2I-1-1&&&&&&&&&& C． 2I-1&&&&&&&&&&& D．2I &-1
18. 一个具有1025个结点的二叉树的高h为（&&& ）【南京理工大学 1999 一、19 （2分）】
A．11&&&&&&&&& B．10&&&&&&& C．11至1025之间&&&&& D．10至1024之间
19．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( &&&)结点
A．2h&&&& B．2h-1&&&&&&& C．2h+1&&&&&&&& D．h+1&& 【南京理工大学2001一、11(1.5分）】
20．对于有n 个结点的二叉树, 其高度为（&&& ）【武汉交通科技大学 1996 一、5 (4分)】
A．nlog2n&&&&& B．log2n&&&&&&&&& C．&log2n&|+1&&&&&& D．不确定
21. 一棵具有 n个结点的完全二叉树的树高度（深度）是（&&& ）【南京理工大学 1996一、8 （2分）】
A．&logn&+1&&& &&&B．logn+1&&&&&&& C．&logn&&&&&& D．logn-1
22．深度为h的满m叉树的第k层有（& ）个结点。(1=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)_______;
}//& 【南京理工大学 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)_______ ]
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& *
struct node{ tree lchild,}
exchange(tree t)
{tree& r,p; tree& stack [500]; int& tp=0;
&(1)_______
&while (tp>=0)
{(2)_______
if((3)_______)
{r=p-> p->lchild=p-> p->rchild=r
& &stack[(4)_______]=p-> stack[++tp]=p->
}} 【中科院自动化研究所 1994 二、2 （15分）】
64．下面使用类pascal语言写的对二叉树进行操作的算法，请仔细阅读
TYPE pointer=^
tnodetp=RECORD data: llink,rlink: pointer；END;
linkstack=^
linknodet=RECORD data:pointer；linkstack；END;
PROC unknown (VAR t:pointer);
VAR& p,temp：
BEGIN p:=t;
& IF p NIL THEN
[temp:=p^.llink ；p^.llink:=p^.；p^.rlink:=
unknown(p^.llink); unknown(p^.rlink); ]
① 指出该算法完成了什么功能
② 用栈将以上算法改为非递归算法unknown1,其中有若干语句或条件空缺请在空缺处填写上适当的语句或条件
PROC inistack(VAR s:linkstack);
(1)_______; s^.next:=NIL;
FUNC empty (s:linkstack):
&IF (2)_______THEN empty:=true ELSE empty:=
FUNC gettop(s:linkstack):
& gettop:= (3)_______;
FUNC pop(VAR s:linkstack)：
&& pop:=s^.next^. p:=s^. (4)_______；(5)_______;
PROC push (VAR s:x:pointer);
& new(p); p^.data:=x; (6)_______; s^.next:=p;
PROC unknown1(VAR t:pointer);
VAR& p,temp: finish:
& &inistack(s); finish:= &p:=t;
& &&&WHILE p NIL DO
[temp:=p^. p^.llink:=p^. p^.rlink:=
&&&& &&&(7)_______;& p:=p^.&&& ];
& &&&&&&IF (8)____THEN [p:=gettop(s);=pop(s);] ELSE (9)_______
UNTIL (10)___
ENDP; 【北方交通大学 2000 三、 (25分)】
65．具有n个结点的完全二叉树，已经顺序存储在一维数组A[1..n]中，下面算法是将A中顺序存储变为二叉链表存储的完全二叉树。请填入适当的语句在下面的_______上，完成上述算法。
TYPE ar=ARRAY[1..n] OF
pointer=RECORD data: lchild, rchild: END;
PROCEDURE& btree(VAR a: VAR p:pointer);
PROCEDURE& createtree(VAR t: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;
&& j:= (6)__;&& createtree(p,j)
GEND; &【北京邮电大学 1998 五、 (15分)】
66．设一棵二叉树的结点定义为
&&& struct BinTreeNode{
ElemT BinTreeNode *leftchild,* }
现采用输入广义表表示建立二叉树。具体规定如下：
（1）树的根结点作为由子树构成的表的表名放在表的
（2）每个结点的左子树和右子树用逗号隔开。若仅有
右子树没有左子树，逗号不能省略。
（3）在整个广义表输入的结尾加上一个特殊的符号
（例如“#”）表示输入结束。
例如，对于如右图所示的二叉树，其广义表表示为A（B（D，E（G）），C（，F））。
此算法的基本思路是：依次从保存广义表的字符串ls中输入每个字符。若遇到的是字母（假设以字母作为结点的值），则表示是结点的值，应为它建立一个新的结点，并把该结点作为左子女（当k=1）或右子女（当k=2）链接到其双亲结点上。若遇到的是左括号“（”，则表明子表的开始，将k置为1；若遇到的是右括号“）”，则表明子表结束。若遇到的是逗号“，”，则表示以左子女为根的子树处理完毕，接着处理以右子女为根的子树，将K置为2。在算法中使用了一个栈s，在进入子表之前，将根结点指针进栈，以便括号内的子女链接之用。在子表处理结束时退栈。相关的栈操作如下：
&&& MakeEmpty(s) &&&&&置空栈&& &&&&&&&&&&Push(s,p)&&&&& &&元素p入栈
&&& Pop(s)&&&&&&&& &&&退栈&&&&&&&&&& &&&&Top(s)&&&&&&&&& 存取栈顶元素的函数
下面给出了建立二叉树的算法，其中有5个语句缺失，请阅读此算法并把缺失的语句补上。（每空3分）
void CreatBinTree(BinTreeNode *&BT,char ls){
S&&& MakeEmpty(s);
BT=NULL;&&&&&&&&&&&&&&& &&&&//置空二叉树
& BinTreeNode *p;
& &istream ins(ls)；& &&//把串ls定义为输入字符串流对象ins&& ;
ins>>&&&& &&&&&&//从ins顺序读入一个字符
while (ch != ‘#’){&& &&&&&//逐个字符处理，直到遇到‘#’为止
&&& switch(ch){
&&&&&&&& case ‘(’: (1)___；k=1;
&&&&&&&& case ‘)’:& pop(s);&&& &
&&&&&&&& case’,’ : (2)___；&&&&
&&&&&& default :p=new BinTreeN (3)____;p->leftChild=NULL;p->rightChild=NULL;
if(BT==NULL) (4)___；else if (k==1) top(s)->leftChild=p;
else top(s)->rightChild=p;
(5)____; }& }& 【清华大学 2001 六、 (15分)】
67. 判断带头结点的双向循环链表L是否对称相等的算法如下所示，请在划线处填上正确的语句
FUNCTION& equal(l:pointer) :
VAR p,q:& result: B
BEGIN result = p:= l^. q:=l^.
&&&&& WHILE (pq) AND ((1)_______)DO&
&&&&&& &IF& p^.data=q^.data THEN BEGIN (2)___; (3)____; END；
&&&&&&&&&&& &&&&&&&&&&&&&&&&ELSE& result=
&&&&& return(result);
& END; &&【华南师范大学 2000年 五、1 ( 9分)】
68．下列是先序遍历二叉树的非递归子程序，请阅读子程序（C语言与PASCAL语言过程功能完全相同，任选其一），填充空格，使其成为完整的算法。
C语言函数：
void example(b)
&btree& *b;
{ btree *stack[20], *p；
if (b!=null)
{ top=1; stack[top]=b;
while (top>0)
{ p=stack[top]; top--;
printf(“%d”,p->data);
if (p->rchild!=null)
{(1)___; &(2)___;
if (p->lchild!=null)
(3)___; (4)__;
PASCAL语言过程
PROCEDURE example(b:btree);
VAR stack:ARRAY[1..20] OF
&& top: p:
IF bNIL& THEN
&BEGIN& top:=1; stack[top]:=b;
WHILE top>0 DO
&&BEGIN p:=stack[top];top:=top-1;
write(p^.data);
IF p^.rchildNIL
&THEN BEGIN
&(1)__;(2)_; END;
IF p^,lchildNIL
&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: VAR s: link);
&&&& VAR& k,L:
&&&& 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语言/
&& &{ struct& node *lchild,*}*
void vst(bitree bt)& &&&&&&&&&&&&&&&&&/*bt为根结点的指针*/
& &&{ bitree& p= &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为根结点的指针*/
&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& (tmaxsize THEN stackfull
ELSE BEGIN S.data[S.top]:=p； (1)__; END
IF S.data[S.top]^.rchildNIL 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]^.rchildS.data[S.top+1];
&& &&&&&&&&&&&&&&&IF S.data[S.top]^.rchildS.data[S.top+1] THEN (3)__;
UNTIL(4)___;
END； 【西北工业大学 1999 六、1 (7分)】
75．由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。
#define& MAX 100
typedef struct Node
{ struct Node *llink, * }TNODE;
char pred[MAX],inod[MAX];
& &&main(int argc,int **argv)
{ TNODE& *
if(argcrlink=restore ((5)_______+k,rpos+1,n-1-k);
postorder(TNODE*ptr)
{ if(ptr=NULL)
& postorder(ptr->llink);& postorder(ptr->rlink);& printf(“%c”,ptr->info);
&} 【中科院计算所 2000 三、 (10分)】
76．已给如下关于二叉树的类型说明：
& TYPE tree=^
&& &&&&node=RECORD data : left ,right:tree END;
以下过程实现对二叉树t前序遍历的非递归算法：
&& PROCEDURE preorder(t:tree );
&& VAR& stack: ARRAY [1..100] OF nd: top:
BEGIN top:=1; stack[top]:=t;
& WHILE(1)___ DO&&
& &&BEGIN nd:=stack[top];top:=top -1; write (nd^.data);
&&& &&&&&&&&&IF (nd^.rightNIL) THEN BEGIN top:=top +1; (2)___& END;
&& IF (3)___THEN BEGIN& (4)&& &；stack[top]:= nd^.left；END
END; 【厦门大学 2000 三、1 （8分）】
77．下面是中序线索树的遍历算法，树有头结点且由指针thr指向。树的结点有五个域，分别为数据域 data，左、右孩子域 lchild、rchild和左、右标志域 ltag,rtag。规定，标志域为1是线索，O是指向孩子的指针。
&&& inordethread(thr)
&&&& {p=thr->
&&&&& 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);
IF p＾.rtag=0 THEN& WHILE(2)____DO& q:= (3)___；
【南京理工大学 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= }
&& &&&&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 指向其前驱；rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。
prior(node,x)
&{ if (node !=null)
&& if ((1)_____ ) *x=node-> else *x=node->
next(bt, node, x)&&& /*bt是二叉树的树根*/
& {(2)_____;
&& if (node!=bt &&& &node!=null)
&& &&if& (node->rflag)& (3)_______ ；
& else {do t=*x; (4)_______;while& (*x==node); *x=t; }
& &} 【南京航空航天大学 1996 十、 (8分)】
四、应用题
1．从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。【西安电子科技大学2001软件 二、1（5分）】
2．树和二叉树之间有什么样的区别与联系？
【西北工业大学1998一、3(4分)】【厦门大学2000五、2(14%/3分)】【燕山大学2001三、1(5分)】
3．请分析线性表、树、广义表的主要结构特点，以及相互的差异与关联。
【大连海事大学2001三(10分)】
4. 设有一棵算术表达式树，用什么方法可以对该树所表示的表达式求值？
【中国人民大学2001二、3(4分）】
5．将算术表达式（（a+b）+c*(d+e)+f）*(g+h)转化为二叉树。【东北大学 2000 三、1 （4分）】
6. 一棵有n(n>0)个结点的d度树, 若用多重链表表示, 树中每个结点都有d个链域, 则在表示该树的多重链表中有多少个空链域? 为什么? 【长沙铁道学院 1998 四、1 (6分)】
7. 一棵二叉树中的结点的度或为0或为2，则二叉树的枝数为2(n0-1)，其中n0是度为0的结点的个数。
【南京理工大学 1998 六、 (3分)】
类似本题的另外叙述有：
（1）若二叉树中度为1的结点数为0，则该二叉树的总分支数为2（n0-1），其中n0为叶结点数。
【西北工业大学 1998 三、1（5分）】
8．一个深度为L的满K叉树有以下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树，如果按层次顺序从1开始对全部结点进行编号，求：
1）各层的结点的数目是多少？ &2）编号为n的结点的双亲结点（若存在）的编号是多少？
3）编号为n的结点的第i 个孩子结点（若存在）的编号是多少？
4）编号为n的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？
请给出计算和推导过程。【西北工业大学1999五(10分)】【中科院自动化所1996二、1(10分)】
类似本题的另外叙述有：
（1）一棵高度为h的满k叉树有如下性质：根据结点所在层次为0；第h层上的结点都是叶子结点；其余各层上每个结点都有k棵非空子树，如果按层次自顶向下，同一层自左向右,顺序从1开始对全部结点进行编号，试问：
1)各层的结点个数是多少?(3分)& &2)编号为i的结点的双亲结点（若存在）的编号是多少?(3分)
3)编号为i的结点的第m个孩子结点（若存在）的编号是多少？（3分）
4)编号为i的结点有右兄弟的条件是什么？其右兄弟结点的编号是多少？（3分)
【清华大学 1999 八 (12分)】
9．证明任一结点个数为n 的二叉树的高度至少为O(logn).【浙江大学 2000 四、 (5分)】
10．有n个结点并且其高度为n的二叉树的数目是多少?
【西安电子科技大学2000计应用一、3(5分)】
11．已知完全二叉树的第七层有10个叶子结点，则整个二叉树的结点数最多是多少？
【西安电子科技大学2000计应用 一、4 （5分）】
12．高度为10的二叉树，其结点最多可能为多少？【首都经贸大学 1998 一、1 （4分）】
13．任意一个有n个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点有（m-1）个度为2，其余度为1。【西安电子科技大学2001计应用 二、3 （5分）】
14. 已知A[1..N]是一棵顺序存储的完全二叉树，如何求出A[i]和A[j]的最近的共同祖先？&&
【中国人民大学 2001 二、5 （4分）】
15．给定K(K>=1),对一棵含有N个结点的K叉树（N＞０）、请讨论其可能的最大高度和最小高度。
【大连海事大学&& 2001 五、 (８分)】
16．已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个？
【东北大学 1999 一、1 （3分）】
17．一棵共有n个结点的树，其中所有分支结点的度均为K，求该树中叶子结点的个数。
【东北大学 2000 一、3 （4分）】
18． 如在内存中存放一个完全二叉树，在树上只进行下面两个操作：
（1）寻找某个结点双亲 （2）寻找某个结点的儿子；
请问应该用何种结构来存储该二叉树？【东北大学 2001 一、3 （3分）】
19．求含有n个结点、采用顺序存储结构的完全二叉树中的序号最小的叶子结点的下标。要求写出简要步骤。【北京工业大学 2000 二、3 （ 5分）】
20．设二叉树T中有n个顶点，其编号为1，2，3，…,n,若编号满足如下性质：
（1）T中任一顶点v的编号等于左子树中最小编号减1；
（2）对T中任一顶点v,其右子树中最小编号等于其左子树中的最大编号加1。试说明对二叉树中顶点编号的规则（按何种顺序编号）。【山东大学 1992 一、1 （3分）】
21．若一棵树中有度数为1至m的各种结点数为n1,n2,…,nm(nm表示度数为m的结点个数)请推导出该树中共有多少个叶子结点n0的公式。【北京邮电大学分)】【西安交通大学1996四、1(5分)】【南京航空航天大学1998五(10分)】【东南大学1999一 4（8分)】【山东大学分)】
【山东师范大学2001 二3(12分) &&分)】
22．若一棵完全二叉树中叶子结点的个数为n,且最底层结点数≧2，则此二叉树的深度H=？
【北京科技大学 2001 一、6 （2分）】
23．已知完全二叉树有30个结点，则整个二叉树有多少个度为0的结点？【山东师范大学1996五、3(2分)】
24．在一棵表示有序集S的二叉搜索树(binary& search& tree)中,任意一条从根到叶结点的路径将S分为3部分：在该路径左边结点中的元素组成的集合Sl；在该路径上的结点中的元素组成的集合S2；在该路径右边结点中的元素组成的集合S3。S=S1∪S2∪S3。若对于任意的a∈Sl,b∈S2，c∈S3是否总有a≤b≤c?为什么?【清华大学 2000 四(10分)】【武汉大学 2000 三、3】
25．试证明,在具有n(n>=1)个结点的m次树中,有n(m-1)+1个指针是空的。【复旦大学1998四(8分)】
26．对于任何一棵非空的二叉树,假设叶子结点的个数为n0,而次数为2的结点个数为n2,请给出n0和n2之间所满足的关系式n0=f(n2).要求给出推导过程。【复旦大学 1998 五 (8分)】
27．对于任意一棵非空的二叉树T，我们用n0表示T中叶子结点的个数，用n2表示T中有两棵非空子树的结点的个数。（1）给出n0和n2所满足的关系式。（2）证明你在（1）中给出的关系式成立。
【复旦大学 1997 三 (10分)】
28．试求有n个叶结点的非满的完全二叉树的高度;【中科院计算所 2000 五、 (5分)】
29．对于具有n个叶子结点，且所有非叶子结点都有左右孩子的二叉树，
(1)试问这种二叉树的结点总数是多少？（5分）
(2)试证明 =1。其中:li表示第i个叶子结点所在的层号(设根结点所在层号为1)。(10分)
【北方交通大学 1995 三、 (15分)】
30．假设高度为H的二叉树上只有度为0和度为2的结点，问此类二叉树中的结点数可能达到的最大值和最小值各为多少？【北京邮电大学 1996 一、1 （4分）】
31．一棵满k叉树，按层次遍历存储在一维数组中，试计算结点下标的u的结点的第i个孩子的下标以及结点下标为v的结点的父母结点的下标。【北京邮电大学 2001 四、4(5分）】
32．二叉树有n个顶点，编号为1，2，3，… ，n，设：
* T中任一顶点V的编号等于左子树中最小编号减1；
* T中任一顶点V的右子树中的最小编号等于其左子树中的最大编号加1；
试描绘该二叉树。【东南大学 1999 一、2 （7分）】
33．设T是具有n个内结点的扩充二叉树，I是它的内路径长度，E是它的外路径长度。
（1）试利用归纳法证明E=I+2n,&& n>=0.（5分)
（2）利用（1）的结果试说明：成功查找的平均比较次数s与不成功查找的平均比较次数u 之间的关系可用公式表示s=(1+1/n)u-1,n>=1。 【清华大学 1998 四、 (10分)】
34．一棵非空的有向树中恰有一个顶点入度为0,& 其它顶点入度为1,但一个恰有一个顶点入度为0,其它顶点入度为1的有向图却不一定是一棵有向树,请举例说明。【中科院计算所 1999 三、1 （5分）】
35．试给出下列有关并查集（mfsets）的操作序列的运算结果：
union(1,2),union(3,4),union(3,5),union(1,7),union(3,6),union(8,9),
union(1,8),union(3,10),union(3,11),union(3,12),union(3,13),
union(14,15),union(16,0),union(14,16),union(1,3),union(1,14).
(union是合并运算，在以前的书中命名为merge)
（1）对于union(i,j),以i作为j的双亲；&&&&&& （5分)
（2）按i和j为根的树的高度实现union(i,j),高度大者为高度小者的双亲；&&& （5分)
（3）按i和j为根的树的结点个数实现union(i,j),结点个数大者为结点个数小者的双亲。（5分)
【清华大学 2001 一、 (15分)】
36．证明：在任何一棵非空二叉树中有下面的等式成立：叶结点的个数=二度结点的个数+1
【天津大学 1999 四 】
37. 对于一个堆栈，若其入栈序列为1，2，3，…，n，不同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为n的二叉树的个数，且与不同形态的二叉树一一对应。请简要叙述一种从堆栈输入（固定为1，2，3……n）/输出序列对应一种二叉树形态的方法，并以入栈序列1，2，3（即n=3）为例加以说明。【浙江大学 1998年 五、1 (7分)】
38. 如果给出了一个二叉树结点的前序序列和对称序序列，能否构造出此二叉树?若能，请证明之。若不能，请给出反例。如果给出了一个二叉树结点的前序序列和后序序列，能否构造出此二叉树?若能，请证明之。若不能，请给出反例。【北京大学 1998 二、2 （5分)】
类似本题的另外叙述有：
（1） 二叉树的中序与后序序列能唯一地定义一棵二叉树吗? 这里所指序列中的符号代表树结点中的标识符吗？二叉树的前序与后序序列能唯一地定义一棵二叉树吗?为什么?【东南大学1993一、4（8分）】
39．试证明:同一棵二叉树的所有叶子结点，在前序序列。对称序序列以及后序序列中都按相同的相对位置出现（即先后顺序相同），例如前序abc,后序bca对称序bac。【山东工业大学 1997 七、 (10分)】
40. 由二叉树的中序序列及前序序列能唯一的建立二叉树，试问中序序列及后序序列是否也能唯一的建立二叉树，不能则说明理由，若能对中序序列DBEAFGC和后序序列DEBGFCA构造二叉树。
【南京理工大学 1998 四、 (3分)】
41. 证明，由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。设一棵二叉树的前序序列为ABDGECFH，中序序列为：DGBEAFHC 。试画出该二叉树。【浙江大学 1996 六、 (8分)】
类似本题的另外叙述有：
(1) 证明：由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。
【长沙铁道学院1997五、2(10分)】
（2）证明：由二叉树的中序遍历序列和后序遍历序列可唯一地确定出该二叉树。
【华南理工大学 2001 一、3 （4分)】
（3）二叉树已知其中序扫描序列和后序扫描序列如何确定这一棵二叉树,并举例说明.
【山东大学 2001软件与理论 二 、1 （4分）】
42．试证明：仅仅已知一棵二叉树的后序遍历序列和先序遍历序列，不能唯一地确定这棵二叉树。
【大连海事大学&&& 2001 九、 (８分)】
类似本题的另外叙述有：
(1) 由二叉树的前序遍历和后序遍历结果能否唯一确定一棵二叉树？解释你的论断。
【西安电子科技大学2001计应用&&& 二、4 （5分）】
(2) 假定某二叉树的前序遍历序列为ABCDEFGHIJ,后序遍历序列为CEFDBJIHGA,据此两个序列能否唯一确定此二叉树? 若不能,试画出两样具有同样上述遍历序列的二叉树.【武汉交通科技大学分）】
43. ① 试找出满足下列条件的二叉树
1）先序序列与后序序列相同& 2）中序序列与后序序列相同
3）先序序列与中序序列相同& 4）中序序列与层次遍历序列相同&&&&&&&&&&&&&&
② 已知一棵二叉树的中序序列和后序序列分别为DBEAFIHCG和DEBHIFGCA，画出这棵二叉树。
【东北大学 1999 六、 (4分)】
类似本题的另外叙述有：
（1）试画出在先根次序和中根次序下结点排列顺序皆相同的所有类型的二叉树形。
试画出在先根次序和后根次序下结点排列顺序皆相同的所有类型的二叉树形。
【吉林大学 1995 四、1,2 （每题7分)】
（2）找出所有的二叉树，其结点在下列两种遍历下恰好都有同样的遍历序列。
1）先序遍历和中序遍历&& 2）先序遍历和后序遍历【北京理工大学 1999 三(6分)】
（3）找出所有的二叉树，其结点在下列两种遍历下，恰好都是以同样的顺序出现：
1）前序遍历和中序遍历。& 2）前序遍历和后序遍历。【南京航空航天大学 1995 六(5分)】
（4）试找出分别满足下列条件的所有二叉树。
1）先序序列和中序序列相同& 2）中序序列和后序序列相同
3）先序序列和后序序列相同&& 【南京航空航天大学 2001 二、（10分)】
（5）找出所有满足下列条件的二叉树：
1）它们在先序遍历和中序遍历时，得到的结点访问序列相同；
2）它们在后序遍历和中序遍历时，得到的结点访问序列相同；
3）它们在先序遍历和后序遍历时，得到的结点访问序列相同；【东南大学2000一、4(6分）】
44．将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果）
【南京航空航天大学 1998 一、 (10分)】
45. 阅读下列说明和流程图，回答问题（1）和问题（2）。
说明：流程图是用来实现中序遍历，二叉树存放在数组tree中，每个数组元素存放树中一个结点，每个结点的形式为（值，左指针，右指针），分别用tree[i].v，tree[i].l，tree[i].r来表示第i个结点的值，左指针，右指针，其中左，右指针的值为所指结点在数组中的下标，若指针的值为0，表示它指向空树，图中指针root用以指向二叉树的根结点。问题：
& （1）填充流程图中的①、②、③，使其按中序遍历二叉树。
（2）把流程图中的（A）框移至哪个位置（图中Ⅰ～Ⅸ）使流程图的算法从中序遍历变成后序遍历。
【上海海运学院 1997年 四、（13分）】
46．设一棵二叉树的先序、中序遍历序列分别为
先序遍历序列： A B D F C E G H& 中序遍历序列： B F D A G E H C
（1）画出这棵二叉树。
（2）画出这棵二叉树的后序线索树。&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
（3）将这棵二叉树转换成对应的树（或森林）。【南京航空航天大学 1997 二、 (10分)】
47．已知一棵二叉树的对称序和后序序列如下：
对称序：GLDHBEIACJFK&& 后序：& LGHDIEBJKFCA
(1) （2分)给出这棵二叉树：
(2) （2分)转换为对应的森林：
(3) （4分)画出该森林的带右链的先根次序表示法：
&&&&&&&& &&&&Itag=
&&&& (4) (4分) 画出该森林带度数的后根次序表示法：
(5) (4分)在带度数的后根次序表示法中，不包含指针，但仍能完全反映树的结构。写出以结点x为根的子树在后根次序序列中的前驱的求法。（用语言叙述，不用写算法）【山东大学 1998 八、（16分）】
48．设某二叉树的前序遍历序列为:ABCDEFGGI，中序遍历序列为:BCAEDGHFI：
（1）试画出该二叉树；
（2）写出由给定的二叉树的前序遍历序列和中序遍历序列构造出该二叉树的算法。
（3）设具有四个结点的二叉树的前序遍历序列为ａｂｃｄ；Ｓ为长度等于四的由ａ，ｂ，ｃ，ｄ排列构成的字符序列，若任取Ｓ作为上述算法的中序遍历序列，试问是否一定能构造出相应的二叉树，为什么？试列出具有四个结点二叉树的全部形态及相应的中序遍历序列。
【浙江大学 1997 六、 (15分)】
类似本题的另外叙述有：
（1）已知二叉树的先序序列:& CBHEGAF,&& 中序序列: HBGEACF, 试构造该二叉树
【北京理工大学 2001 八、2 （4分）】
（2）已知二叉树按中序排列为BFDAEGC，按前序排列为ABDFCEG，要求画出该二叉树。
【山东师范大学 1996&&& 五、1 (2分)】
（3）已知一棵二叉树的前序序列 A,B,D,C,E,F，中序序列B,D,A,E,F,C. 画出这棵二叉树。
【燕山大学 1999 四、 (5分)】
（4）已知一棵二叉树的前序遍历结果是：ABCDEFGHIJ,中序遍历的结果是：BCEDAGHJIF,试画出这棵二叉树。【厦门大学 1998 六、1 （7分)】
（5）已知二叉树BT各结点的先序、中序遍历序列分别为ABCDEGF和CBAEDF，试画出该二叉树。
【北京工业大学 1998 二、 (6分)】
49. 假设一棵二叉树的前序序列为ABCD,它的中序序列可能是DABC吗?【石油大学1998一、1(5分)】
类似本题的另外叙述有：
（1）一棵前序序列为1，2，3，4，的二叉树，其中序序列可能是4，1，2，3吗？设一棵二叉树的前序序列为1，2，3，4，5，6，7，8，9，其中序序列为2，3，1，5，4，7，8，6，9，试画出该二叉树。
【东南大学 1996一、2 （7分)&& 1998 一、3】
50．一棵非空的二叉树其先序序列和后序序列正好相反，画出这棵二叉树的形状。
【西安电子科技大学2000软件 一、8 （5分）】
51．已知一棵二叉树的后序遍历序列为EICBGAHDF，同时知道该二叉树的中序遍历序列为CEIFGBADH，试画出该二叉树。【重庆大学 2000&&& 二、2】
类似本题的另外叙述有：
（1）已知二叉树ＢＴ各结点的中序和后序序列分别为ＤＦＢＡＣＥＧ和ＦＤＢＧＥＣＡ，试构造出该二叉树ＢＴ，并作简要说明。【北方交通大学 1997 二、 (8分)】
（2）已知二叉树的中序遍历序列为G F B E A N H M，后序遍历的结点序列为G E B F H N M A ，画出此二叉树的形态。【青岛海洋大学 1999 一、5（5分)】
（3）已知二叉树的后序序列为ABCDEFG 和中序序列为ACBGEDF，构造出该二叉树。
【福州大学 1998 三、1 (6分)】
（4）已知某二叉树的后序遍历和中序遍历如下，构造出该二叉树。
后序遍历序列： G D B E I H F C A& 中序遍历序列：D G B A E C H I F
【厦门大学 2000 七、1 （20%/3分)】
（5）已知一个二分树的中序序列和后序序列如下：
中序：A B C D E F G H I J&& 后序：A C D B H J I G F E
试画出此二分树的结构。 【首都经贸大学 1998 二、1 （10分）】
52．假设一棵二叉树的层次序列为ABCDEFGHIJ，中序序列DBGEHJACIF。请画出这棵二叉树。
【武汉大学 2000 三、1】【东南大学 2000 一、1 （6分）】
类似本题的另外叙述有：
（1）假设一棵二叉树的层次次序（按层次递增顺序排列，同一层次自左向右）为ABECFGDHI,中序序列为BCDAFEHIG。请画出该二叉树，并将其转换为对应的森林。【山东大学 2001 四、 (6分)】
53. 已知一个森林的先序序列和后序序列如下，请构造出该森林。
先序序列：ABCDEFGHIJKLMNO
后序序列：CDEBFHIJGAMLONK& 【合肥工业大学 2000 四、1 （5分）】
54． 画出同时满足下列两条件的两棵不同的二叉树。&&&&&&&&&&
(1)按先根序遍历二叉树顺序为ABCDE。&&&&&&&&&&&&&&&&&&&
(2)高度为5其对应的树（森林）的高度最大为4。【东北大学 1997 一、3 （5分）】
55．用一维数组存放的一棵完全二叉树；ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列。
【西安电子科技大学1999计应用 一、6 （5分）】
56．一棵二叉树的先序、中序、后序序列如下，其中一部分未标出，请构造出该二叉树。
先序序列 ：_ _ C D E _ G H I _ K
中序序列 ：C B _ _ F A _ J K I G
后序序列 ：_ E F D B _ J I H _ A& 【厦门大学 2002 七、1 （6分)】
类似本题的另外叙述有：
（1）一棵二叉树的先序、中序和后序序列分别如下，其中有一部分为显示出来。试求出空格处的内容，并画出该二叉树。
&先序序列: _ B &&F &&I C E H &&G
&中序序列：D &&K F I A &&E J C &
&后序序列： &K &&F B H J &&G &&A& 【西安电子科技大学2000计应用&&& 五、2 （5分)】
（2）已知一棵二叉树的先序 中序和后序序列如下，其中空缺了部分，请画出该二叉树。
先序：_ B C _ E F G _ I J K _
中序：C B E D _ G A J _ H _ L
后序：_ E _ F D _ J _ L _ H A& 【合肥工业大学 2001 四、1 （5分)】
（3）已知含有8个结点的一棵二叉树，按先序、中序、后序进行遍历后，有些结点序号不清楚如下图示。要求构造出一棵符合条件的二叉树。
先根序遍历& _ 2 3 _ 5 _ 7 8
中根序遍历& 3 _ 4 1 _ 7 8 6
后根序遍历& _ 4 2 _ _ 6 5 1 &&【东北大学 1996 一、3 （5分）】
57．M 叉树的前序和后序遍历分别与由它转换成的二叉树的哪种遍历相对应？
【中国人民大学 2000 一、2 （4分）】
58．证明：在二叉树的三种遍历序列中，所有叶子结点间的先后关系都是相同的。要求每步论断都指出根据。【北京工业大学 2001 二、3 （5分）】
59. 下表中M﹑N分别是一棵二叉树中的两个结点，表中行号i=1，2，3，4分别表示四种M﹑N的相对关系，列号j=1，2，3分别表示在前序、中序、后序遍历中M,N之间的先后次序关系。要求在i，j所表示的关系能够发生的方格内打上对号。例如：如果你认为n是m的祖先，并且在中序遍历中n能比m先被访问，则在（3，2）格内打上对号
先根遍历时n先被访问
中根遍历时n先被访问
后根遍历时n先被访问
N在M的左边
N在M的右边
N是M的祖先
N是M的子孙
【南京理工大学 2001 四、 (10分)】
60．用一维数组存放的一棵完全二叉树如下图所示：
写出后序遍历该二叉树时访问结点的顺序。
【北京工业大学 1996 一、4 （6分）】
61．设树形T在后根次序下的结点排列和各结点相应的次数如下：
后根次序：ＢＤＥＦＣＧＪＫＩＬＨＡ
次　　数：００００３０００２０２４
请画出Ｔ的树形结构图。 【吉林大学 2001 一、2 （4分）】
62．已知二叉树采用二叉链表方式存放，要求返回二叉树T的后序序列中的第一个结点的指针，是否可不用递归且不用栈来完成？请简述原因。【西北大学 2001 &三& 6】
63．对于二叉树T的两个结点n1和n2，我们应该选择树T结点的前序、中序和后序中哪两个序列来判断结点n1必定是结点n2的祖先,并给出判断的方法。不需证明判断方法的正确性。
【复旦大学 1999 五 (10分)】
64．设二叉树的存储结构如下(每题5分,共15分)
&&&&&&&&& LINK&&&& 0& 0& 2& 3&& 7& 5&& 8& 0& 10& 1
&&&&&&&&& INFO&&&& J& H& F& D &&B& A &&C& E &&G& I
&&&&&&&&& RLINK& &&0& 0& 0& 9&& 4& 0&& 0& 0&& 0& 0
其中,T为树根结点的指针,LLINK、RLINK分别指向结点的左右子女,INFO为其数据域,请完成下列各题:
（1）画出二叉树T的逻辑结构. （2）写出按前序、中序和后序周游二叉树T得到的结点序列.
（3）画出二叉树T的后序线索树。& 【山东工业大学 1995 六、（15分）】
65．在二叉树的前序遍历和中序遍历的递归算法中，最后一个递归调用语句在调用时所保留的参数有什么作用？如何清除最后这个递归语句？【北京邮电大学 1994 三、 (8分)】
66．在二叉树的Ｌlink-Rlink存储表示中，引入“线索”的好处是什么？
【山东大学 1999 六、１(２分）】
67．按下面要求解下图中二叉树的有关问题：&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
(1)对此二叉树进行后序后继线索化 ；(2)将此二叉树变换为森林；
(3)用后根序遍历该森林，；写出遍历后的结点序列。【北京邮电大学 1996 五、 (10分)】
类似本题的另外叙述有：
（1）已知一棵二叉树的先序遍历序列为：AEFBGCDHIKJ，中序遍历序列为：EFAGBCHKIJD。试写出此二叉树的后序遍历序列，并用图画出它的后序线索二叉树。【同济大学 2000 一、 (10分)】
P68．对下图所示二叉树分别按前序﹑中序﹑后序遍历，
给出相应的结点序列，同时给二叉树加上中序线索。
【青岛海洋大学 1999年一、1 （5分）】&&&&&&&&&&&&&&&&&&&&&&&
69. 假设一个二叉树的两种遍历如下：
前序：ABFGCHDEIJLK&&&& &中序：FGBHCDILJKEA
（1）画出这棵二叉树以及它的中序线索树；
（2）写出在中序线索树的情况下，找到结点N的前驱结点的算法INORDER-PRIOR(N,X)
【上海海运学院 1996 四、 (10分)】
70．已知一棵二叉树的中序（或中根）遍历结点排列为DGBAECHIF，后序（或后根）遍历结点排列为GDBEIHFCA，
（1）试画出该二叉树；
（2）试画出该二叉树的中序穿线（或线索）树；
（3）试画出该二叉树（自然）对应的森林；【吉林大学 2000 一、1 （5分）】
71．设二叉树BT的存储结构如下:
&&&&&&&&&&&&&&&&&& 1&&& 2&&&& 3&&&& 4&&&& 5&&&& 6&&& 7&&&& 8&&&& 9&&& 10
其中BT为树根结点的指针，其值为6,Lchild,Rchild分别为结点的左、右孩子指针域,data为结点的数据域。试完成下列各题:
（l）画出二叉树BT的逻辑结构;
（2）写出按前序、中序、后序遍历该二叉树所得到的结点序列;
（3）画出二叉树的后序线索树。【中国矿业大学 2000 二、 (15分)】
72．请说明是否存在这样的二叉树，即它可以实现后序线索树进行后序遍历时不使用栈；而对前序线索树进行前序遍历时，又有什么样的二叉树可不使用栈。【西安电子科技大学 1996 二、1 (5分）】
73．一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为多少？
【西安电子科技大学 2000计应用 一、2 （5分）】
74．在前序线索树上，要找出结点p的直接后继结点，请写出相关浯句。结点结构为(ltag,lc,data,rtag,rc)。【西北大学 2000 二、6 （5分）】
75．对于后序线索二叉树，怎样查找任意结点的直接后继；对于中序线索二叉树，怎样查找任意结点的直接前驱？【西北工业大学 1998 一、4 （4分）】
76．将下列树的孩子—兄弟链表改为后根遍历全线索链表。【清华大学 1994 二、 (10分)】
77. 已知一棵二叉树的前序遍历为ABECDFGHIJ，中序遍历为EBCDAFHIGJ。试画出这棵树和它的中序线索树。假定用于通讯的电文仅有8个字母C1，C2，…，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，试为这8个字母设计哈夫曼编码树。【上海海运学院1998四(10分)】
78．设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。【首都经贸大学 1997 一、5 （4分)】
类似本题的另外叙述有：
（1）设有正文MNOPPPOPMMPOPOPPOPNP，字符集为M，N，O，P，设计一套二进制编码，使得上述正文的编码最短。【首都经贸大学 1998 一、5 （4分）】
79．给定集合{15,3,14,2,6,9,16,17}
(1)（3分）用□表示外部结点，用○表示内部结点，构造相应的huffman树：
(2) (2分)计算它的带权路径长度：
(3)（3分)写出它的huffman编码：
(4)（3分)huffman编码常用来译码，请用语言叙述写出其译码的过程。
【山东大学 1998 七、】【山东工业大学 2000 七、 (11分)】
类似本题的另外叙述有：
（1） 如果通信字符a,b,c,d出现频度分别为：7，5，2，4请画出哈夫曼树并给出相应的哈夫曼编码。【青岛大学 2001 七、1 （5分)】
（2）给定一组数列（15,8,10,21,6,19,3）分别代表字符A,B,C,D,E,F,G出现的频度，试叙述建立哈夫曼树的算法思想，画出哈夫曼树，给出各字符的编码值，并说明这种编码的优点。
【青岛大学 2000 七、 (10分)】
（3）设通信中出现5中字符A、B、C、D、E对应的频率为0.2,0.1,0.5,0.15,0.25构造哈夫曼树，并给出对应字符的编码。【青岛大学 2002 四、2 （10分）】
（4） 设A、B、C、D、E、F六个字母出现的概率分别为7,19,2,6,32,3。试写出为这六个字母设计的HUFFMAN编码, 并画出对应的HUFFMAN树.【山东工业大学 1995 四(10分)】
（5）设用于通信的电文由8个字母组成, 字母在电文中出现的频率分别为:7,19,2,6,32,3,21,10。试为这8个字母设计哈夫曼编码.使用0-7的二进制表示形式是另一种编码方案,试比较这两种方案的优缺点。【
本栏目更多导读：