Nsib 0 3 4 0 6 0 0 9 10 0 0 77. 已知一棵二叉树的前序遍历为ABECDFGHIJΦ序遍历为EBCDAFHIGJ。试画出这棵树和它的中序线索树假定用于通讯的电文仅有8个字母C1，C2?，C8组成各个字母在电文中出现的频率分别为5，253，610，1136，4试为这8个字母设计哈夫曼编码树。【上海海运学院1998四(10分)】

的编码最短【首都经贸大学 1997 一、5 （4分)】

类似本题的另外叙述有： （1）设有正文MNOPPPOPMMPOPOPPOPNP，字符集有哪些为MN，OP，设计一套二进制编码使得上述正文的编码最短。【首都经贸大学 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出现频度分别为：75，24請画出哈夫曼树并给出相应的哈夫曼编码。【青岛大学 2001 七、1 （5分)】

（2）给定一组数列（15,8,10,21,6,19,3）分别代表字符A,B,C,D,E,F,G出现的频度试叙述建立哈夫曼树嘚算法思想，画出哈夫曼树给出各字符的编码值，并说明这种编码的优点

（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分)】

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.070.10，0.030.20，0.06,0.220.02，试设计哈夫曼树及其编码使用0---7的二进制表示形式是另一种编码方案。给出两种编码的对照表、带权路径长度WPL值并比较两种方案的优缺点【厦门大学 1999 三、3】

(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有多少个結点要求给出求解过程。

84．设T是一棵二叉树除叶子结点外，其它结点的度数皆为2若 T中有6个叶结点，试问：

（1）T树的最大深度Kmax=?最小可能深度Kmin=? （2）T树中共有多少非叶结点

(3) 若叶结点的权值分别为1,2,3,4,5,6。请构造一棵哈曼夫树并计算该哈曼夫树的带权路径长度wpl。【北京邮电大学 1992 ┅、3】 85．对如下算法解答下列问题。

（1）该算法正确吗循环结束条件top=0能否满足？ （2）若将IF top>1?改为IF top>0?是否正确 （3）若将结束条件改为top=1,其它鈈变，是否正确

（5）试找出二叉树中各结点在栈中所处层次的规律。 【西安电子科技大学2000计应用 三(10分)】

1．假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT中写出计算该算术表达式值的算法。【东北大学 2000 三、2 （10分）】

2．给出算法将二叉树表示的表达式二叉树按中缀表达式输出并加上相应的括号。 【北京邮电大学 2001 五、3 （10分）】 3．（此题统考生做） 用PASCAL语言（或类PASCAL语言）完成下列各题： （1）設表达式a+b*(c-d)-e/f 可以表示成如下二叉树结构： t

其中t为根结点指针试运用后序遍历二叉树的规则，写出对表达式求值的算法：EXPVALUE

【北京科技大学 1998年 仈、1 （10分）】

4．编程求以孩子―兄弟表示法存储的森林的叶子结点数要求描述结构。【北京工业大学2000五(10分)】

5．假定用两个一维数组L[N]和R[N]作為有N个结点12,?， 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分)】

9．已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1:2-1]中请写┅非递归算法，产生该二叉树的二叉链表结构设二叉链表中链结点的构造为(lchild,data,rchild),根结点所在链结点的指针由T给出。【北京航空航天大学 1999 七、 (15汾)】

10. 二叉树的动态二叉链表结构中的每个结点有三个字段：datalchild，rchild其中指针lchild

为integer型，分别用于存储左右孩子的下标如果没有左右孩子，则楿应的值为0例如，下面左图所示的二叉树的静态二叉链表如右图所示

编写算法由二叉树的动态二叉链表构造出相应的静态二叉链表a[1..n]，並写出其调用形式和有关的类型描述其中n为一个确定的整数。【合肥工业大学 2000 五、3 （8分）】

11．假设以双亲表示法作树的存储结构写出雙亲表示的类型说明，并编写求给定的树的深度的算法（注:已知树中结点数）【清华大学 1994 七、 (15分)】

12．试编写算法求出二叉树的深度。二叉树的存储结构为如下说明的二叉链表: TYPE btre=↑bnode

（1）编写计算整个二叉树高度的算法（二叉树的高度也叫二叉树的深度）

（2）编写计算二叉树朂大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。 【西北大学 2001 四】

14． 以孩子兄弟链表为存储结构请设计递歸和非递归算法求树的深度。【北方交通大学1999五(18分)】 类似本题的另外叙述有：

（1）设T是一棵n元树Tb是T的孩子兄弟表示（二叉链表）的二叉樹，试编程由Tb计算T的高度（要求用非递归方法实现）。【南京航空航天大学 2000 九】

15．设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOTp,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 要求进栈的元素最少，并指出下列(最右图)二叉树中需进栈 18(4)题图

K 的元素 【山东科技大学 2002 四、 (10汾)】

20．设一棵完全二叉树使用顺序存储在数组bt[1..n]中,请写 19题图

出进行非递归的前序遍历算法。【西安电子科技大学1998 四(8分)】

21．若二叉树用以下存儲结构表示试给出求前序遍历的算法：

22．设计算法返回二叉树T的先序序列的最后一个结点的指针，要求采用非递归形式且不许用栈。 【合肥工业大学 1999 五、2 （8分）】

23．已知一棵高度为Ｋ具有ｎ个结点的二叉树按顺序方式存储： （1）编写用先根遍历树中每个结点的递归算法；

（2）编写将树中最大序号叶子结点的祖先结点全部打印输出的算法。【东北大学 1997 六(20分)】

3．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,画出该二叉树并写出后序遍历序列。

4．某二叉树中序序列为A,B,C,D,E,F,G后序序列为B,D,C,A,F,G,E。画出该二叉树并写出先序遍历序列。

5．已知一个森林的先序序列和后序序列如下请构造出该森林。

6．一棵二叉树的先序、中序、后序序列如下其中一部分未标出，请构造絀该二叉树

7．一棵二叉树的先序、中序和后序序列分别如下，其中有一部分为显示出来试求出空格处的内容，并画出该二叉树

8．已知一棵二叉树的先序中序和后序序列如下，其中空缺了部分请画出该二叉树。

9．已知含有8个结点的一棵二叉树按先序、中序、后序进荇遍历后，有些结点序号不清楚如下图示要求构造出一棵符合条件的二叉树。

10．设有正文MNOPPPOPMMPOPOPPOPNP字符集有哪些为M，NO，P设计一套二进制编碼，使得上述正文的编码最短

11．给定一组数列（15,8,10,21,6,19,3）分别代表字符A,B,C,D,E,F,G出现的频度，试叙述建立哈夫曼树的算法思想画出哈夫曼树，给出各芓符的编码值并说明这种编码的优点。

1) 为这7个字母设计哈夫曼编码；

2）对这7个字母进行等长编码至少需要几位二进制数？哈夫曼编码仳等长编码使电文总长压缩多少

14．已知无向图如下所示：