Nsib 0 3 4 0 6 0 0 9 10 0 0 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的二进制表示形式是另一种编码方案,试比较这两种方案的优缺点。【南京航空航天大学 1999 四、 (10分)】
（6）假设用于通讯的电文由8个字符组成，其出现的频率为5,29,7,8,14,23,3,11。试为这8个字符设计哈夫曼编码。【燕山大学 1999 五、 (5分)】
（7）假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成。它们在电文中出现的频度分别为{0.31,0.16,0.10,0.08,0.11,,0.20,0.04},
1) 为这7个字母设计哈夫曼编码；
2）对这7个字母进行等长编码，至少需要几位二进制数？哈夫曼编码比等长编码使电文总长压缩多少？【北京邮电大学 2001 四、2 （5分)】
（8）试构造一棵二叉树,包含权为1,4,9,16,25,36,49,64,81,100等10个终端结点,且具有最小的加权路径长度WPL。【北方交通大学 1993年 五（12分)】
（9）带权结点为{5,6,7,8,9}，构造Huffman树，计算带权路径长度。【西北大学2001年三、3】
（10）以数据集{2,5,7,9,13}为权值构造一棵哈夫曼树，并计算其带权路径长度。
【西安电子科技大学1999计应用 一、4 （5分）】
（11）假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为
7,19,2,6,32,3，21,10。试为这8个字母设计哈夫曼编码。使用0∽7的二进制表示形式是另一 种编码方案。对于上述实例，比较两种方案的优缺点。【大连海事大学 1996 五、2 (8分)】。
（12）设用于通讯的电文仅由8个字母组成，他们在电文中出现的频率分别为0.30，0.07，0.10，0.03，0.20，0.06,0.22，0.02，试设计哈夫曼树及其编码。使用0---7的二进制表示形式是另一种编码方案。给出两种编码的对照表、带权路径长度WPL值并比较两种方案的优缺点。【厦门大学 1999 三、3】
(13) 给定一组权值2,3,5,7,11,13,17,19,23,29，31，37，41，试画出用Huffman算法建造的Huffman树。【吉林大学 2000 一、2 （4分)】
(14) 以数据集{3,4,5,8,12,18,20,30}为叶结点，构造一棵哈夫曼树，并求其带权路径长度。【山东师范大学 1996 五 5(2分)】
80． 给定权W1,W2,?，Wm 。说明怎样来构造一个具有最小的加权路径长度的k叉树。试对于权1,4,9,16,25, 36,49,64,81,100来构造最优的三叉树，并给出其最小加权路径长度。【北方交通大学1994年 四(12分）】
81．已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT的存储结构的初态和终态。【北京工业大学 1998 五、 (10分)】 82．什么是前缀编码？举例说明如何利用二叉树来设计二进制的前缀编码。【中山大学1999三、1 (3分)】
83．如果一棵huffman树T有n0个叶子结点，那么，树T有多少个结点，要求给出求解过程。
【复旦大学 1999 四、 (10分)】
84．设T是一棵二叉树，除叶子结点外，其它结点的度数皆为2，若 T中有6个叶结点，试问：
（1）T树的最大深度Kmax=?最小可能深度Kmin=? （2）T树中共有多少非叶结点？
(3) 若叶结点的权值分别为1,2,3,4,5,6。请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wpl。【北京邮电大学 1992 一、3】 85．对如下算法，解答下列问题。
PROCEDURE inorder(T:bitree); BEGIN top:=1; s[top]:=T; REPEAT
WHILE s[top]<>NIL DO BEGIN s[top+1]:=s[top]^.lchild; top:=top+1; END;
IF top>1 THEN BEGIN top:=top-1;WRITE
(s[top]^.data);s[top]:=s[top]^.rchild;END;
UNTIL top=0 END;
（1）该算法正确吗？循环结束条件top=0能否满足？ （2）若将IF top>1?改为IF top>0?是否正确？ （3）若将结束条件改为top=1,其它不变，是否正确？
（4）若仅将结束处条件改为(top=1)AND (s[top]=NIL),是否正确？
（5）试找出二叉树中各结点在栈中所处层次的规律。 【西安电子科技大学2000计应用 三(10分)】
五、算法设计题
1．假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT中，写出计算该算术表达式值的算法。【东北大学 2000 三、2 （10分）】
2．给出算法将二叉树表示的表达式二叉树按中缀表达式输出，并加上相应的括号。 【北京邮电大学 2001 五、3 （10分）】 3．（此题统考生做） 用PASCAL语言（或类PASCAL语言）完成下列各题： （1）设表达式a+b*(c-d)-e/f 可以表示成如下二叉树结构： t
- + / a * e f b -
c d
其中t为根结点指针，试运用后序遍历二叉树的规则，写出对表达式求值的算法：EXPVALUE
【北京科技大学 1998年 八、1 （10分）】
4．编程求以孩子—兄弟表示法存储的森林的叶子结点数。要求描述结构。【北京工业大学2000五(10分)】
5．假定用两个一维数组L[N]和R[N]作为有N个结点1，2,?， N的二元树的存储结构。L[i]和R[i]分别指示结点 i的左儿子和右儿子；L[i]=0（R[i]=0）表示i的左（右）儿子为空。试写一个算法，由L和R建立一个一维数组T[n]，使T[i]存放结点i的父亲；然后再写一个判别结点U是否为结点V的后代的算法。【哈尔滨工业大学 1999 七 (14分)】 类似本题的另外叙述有：
（1）假定用两个一维数组L[1..n]和R[1..n]作为有n个结点的二叉树的存储结构，L[i]和R[i]分别指示结点i的左孩子和右孩子，0表示空。写一算法，建立一维数组T[1..n]，使T中第i(i=1,2,...,n)个分量指示结点i的双亲，然后判别结点u是否为v的子孙的算法。【华南师范大学2000 六(17分)】
6．要求二叉树按二叉链表形式存储，
（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。
完全二叉树定义为：深度为K，具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1至N的结点一一对应。此题以此定义为准。【西北大学 2000 六 (12分)】 类似本题的另外叙述有：
（1）试写一算法判断某二叉树是否是完全二叉树。【青岛海洋大学 1999 六(15分)】 （2）编程，判断一棵二叉链表表示的二叉树是否是完全二叉树。【南京航空航天大学2001十(10分)】 （3）编写算法判断一棵二叉树BT是否是完全二叉树。【北方交通大学 1997 八 (20分)】 （4）假设二元树用左右链表示，试编写一算法，判别给定二元树是否为完全二元树？
【哈尔滨工业大学 2000 十一 (14分)】
（5）设二叉树以二叉链表为存储结构，试给出判断一棵二叉树是否为满二叉树的算法，用类pascal语言写为函数形式。【南开大学 1997 四 (16分)】 （6）试写一算法判别某二叉树是否是完全二叉树。【北京邮电大学 1994 九 (20分)】 7．有n个结点的完全二叉树存放在一维数组A[1..n]中，试据此建立一棵用二叉链表表示的二叉树 ，根由tree指向。 【南京理工大学 1998 七、1 （6分）】
8．设任意非空二叉树中结点按层次顺序依次编号为1,2,?,n(n>0),其存储结构采用下图所示形式，其中i表示结点的编号, L(i)的值是i的左儿子的编号，R(i)的值是i的右儿子的编号。若L(i),R(i)的值为0，表示结点i无左儿子或右儿子。试设计算法：
（1）求出二叉树的高度。 （2）求出每个结点的层号（根结点层号为1），并填入D(i)中。（可采用任何高级语言，但要注明你所采用的语言名称）。【山东大学 1992 三、 (13分)】
h
9．已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1:2-1]中，请写一非递归算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。【北京航空航天大学 1999 七、 (15分)】
10. 二叉树的动态二叉链表结构中的每个结点有三个字段：data，lchild，rchild。其中指针lchild
下标 1 B D C A F G 2 3 4 5 6 7 data A B C D E F G lchild 2 3 0 5 0 0 0 rchild 6 4 0 0 0 7 0 E 和rchild的类型为bitre。静态二叉链表是用数组作为存储空间，每个数组元素存储二叉树的一个结点，也有三个字段：data，lchild，rchild。所不同的是，lchild和rdhild 为integer型，分别用于存储左右孩子的下标，如果没有左右孩子，则相应的值为0。例如，下面左图所示的二叉树的静态二叉链表如右图所示。
编写算法由二叉树的动态二叉链表构造出相应的静态二叉链表a[1..n]，并写出其调用形式和有关的类型描述。其中n为一个确定的整数。【合肥工业大学 2000 五、3 （8分）】
11．假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法。（注:已知树中结点数）【清华大学 1994 七、 (15分)】
12．试编写算法求出二叉树的深度。二叉树的存储结构为如下说明的二叉链表: TYPE btre=↑bnode
bnode=RECORD data:datatype; lch,rch:btre END; 【北京轻工业学院1997一(15分)【】南京航空航天大学1997十(10)】【北京理工大学2000
四3(4）】
13．二叉树采用二叉链表存储：
（1）编写计算整个二叉树高度的算法（二叉树的高度也叫二叉树的深度）。
（2）编写计算二叉树最大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。
【西北大学 2001 四】
14． 以孩子兄弟链表为存储结构，请设计递归和非递归算法求树的深度。【北方交通大学1999五(18分)】
类似本题的另外叙述有：
（1）设T是一棵n元树，Tb是T的孩子兄弟表示（二叉链表）的二叉树，试编程，由Tb计算T的高度（要求用非递归方法实现）。【南京航空航天大学 2000 九】
15．设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。【吉林大学 2000 二、3 （12分）】【中山大学 1994 六（15分）】
16．已知一棵二叉树按顺序方式存储在数组A[1..n]中。设计算法，求出下标分别为i和j的两个结点的最近的公共祖先结点的值。【武汉大学 2000 五 1】
17．设计这样的二叉树，用它可以表示父子、夫妻和兄弟三种关系，并编写一个查找任意父亲结点的所有儿子的过程。【燕山大学 2001 四、5 （8分）】
18．在二叉树中查找值为x的结点，试编写算法（用C语言）打印值为x的结点的所有祖先，假设值为x的结点不多于一个，最后试分析该算法的时间复杂度（若不加分析，直接写出结果，按零分算）。
【上海交通大学 1998 五】 类似本题的另外叙述有：
（1）在二叉树中查找值为x的结点，请编写一算法用以打印值为x的结点的所有祖先，假设值为x的结点不多于1个。注：采用非递归算法。【西安电子科技大学1996 六(10分)】 （2）设二叉树中结点的数据域的值互不相同，试设计一个算法将数据域值为x 的结点的所有祖先结点的数据域打印出来。【北方交通大学 1996 八(20分)】
（3）设二叉树根指针为t,且树中结点值各不相同，写出算法disp_f(t,x),查找树中值为t的结点，并显示出其所有祖先结点的值。【首都经贸大学 1998 三、4 （20分)】
A （4）若一棵二叉树中没有数据域值相同的结点，设计算法
B C 打印数据域值为x的所有祖先结点的数据域。如果根结点的
D E A 数据域值为x或不存在数据域值为x的结点，则什么也不打
X B C 印。例如右图所示的二叉树，则打印结点序列为A、C、E。 F G 【北京工业大学 1995 五、 (16分)】 D E F H I 19．利用栈的基本操作写出先序遍历二叉树的非递归算法 G H I 要求进栈的元素最少，并指出下列(最右图)二叉树中需进栈 K 18(4)题图
的元素。 【山东科技大学 2002 四、 (10分)】
20．设一棵完全二叉树使用顺序存储在数组bt[1..n]中,请写 19题图 出进行非递归的前序遍历算法。【西安电子科技大学1998 四(8分)】
21．若二叉树用以下存储结构表示，试给出求前序遍历的算法：
TYPE Tree:=ARRAY[1..max] OF RECORD data:char;parent:integer; END;
A C B D F E