先根遍历时n先被访问 中根遍历时n先被访问 后根遍历时n先被访问 N在M的左边 N在M的右边 N是M的祖先 N是M的子孙 【南京理工大学 2001 四、 (10分)】

60．用一维数组存放的一棵完全二叉树如下图所示：

A B C D E F G H I J K L 写出后序遍历该二叉树时访问结点的顺序。

【北京工业大学 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分)】

68．对下图所示二叉树分别按前序﹑中序﹑后序遍历，

A 给出相应的结点序列，同时给二叉树加上中序线索。

E 【青岛海洋大学 1999年一、1 （5分）】 B C K F D I G L J M H O N P

第67题图

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

Lchild Data Rchild 0 0 J H 0 0 2 F 0 3 D 7 B 5 A 8 C 0 10 1 I 0 0 E G 9 4 0 0 0 其中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分)】 Data A Ltag 0 Fch 2 Rtag 0 B 0 0 0 C 0 5 0 D 0 7 0 E 0 8 0 F 0 0 0 G 0 11 0 H 0 0 0 I 0 0 0 J 0 0 0 K 0 0 0 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分)】

五、算法设计题