习　题　6

一、判断题（下列各题,正确的请在后面的括号内打√；错误的打×）

1.树结构中每个结点最多只有一个直接前驱结点。　　　　　　　　　（　　）

2.完全二叉树一定是满二叉树。　　　　　　　　　　　　　　　　　（　　）

3.在中序线索二叉树中,右线索若不为空,则一定指向其双亲。　　　（　　）

4.一棵完全二叉树中序遍历序列的最后一个结点,必定是该二叉树前序遍历的最后一个结点。　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（　　）

5.二叉树的前序遍历中,任意一个结点均处于其子女结点的前面。　　（　　）

6.由二叉树的前序遍历序列和中序遍历序列,可以推导出后序遍历的序列。　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（　　）

7.在完全二叉树中,若一个结点没有左孩子,则它必然是叶子结点。　　（　　）

8.在哈夫曼编码中,当两个字符出现的频率相同且其编码也相同时,对于这种情况应该做特殊处理。　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（　　）

9.含多于两棵树的森林转换的二叉树,其根结点一定无右孩子结点。　　（　　）

10.具有n个叶子结点的哈夫曼树共有2n－1个结点。　　　　　　　　（　　）

二、填空题

1.在树中,一个结点所拥有的子树数称为该结点的＿＿＿＿。

2.度为零的结点称为＿＿＿＿结点。

3.树中结点的最大层次称为树的＿＿＿＿。

4.对于二叉树来说,第i层上至多有＿＿＿＿个结点。

5.深度为h的二叉树至多有＿＿＿＿个结点。

6.由一棵二叉树的前序序列和＿＿＿＿序列可唯一确定这棵二叉树。

7.有20个结点的完全二叉树,编号为10的结点的父结点的编号是＿＿＿＿。

8.哈夫曼树是带权路径长度＿＿＿＿的二叉树。

9.由二叉树的后序和＿＿＿＿遍历序列,可以唯一确定一棵二叉树。

10.某二叉树的中序遍历序列为:DEBAC,后序遍历序列为:EBCAD。则前序遍历序列为＿＿＿＿。

11.设一棵二叉树结点的先序遍历序列为:ABDECFGH,中序遍历序列为:DEBAFCHG,则二叉树中叶结点是＿＿＿＿。

12.已知完全二叉树的第8层有8个结点,则其叶结点数是＿＿＿＿。

13.由树转换成二叉树时,其根结点无＿＿＿＿。

14.采用二叉链表存储的n个结点的二叉树,一共有＿＿＿＿个指针域。

15.采用二叉链表存储的n个结点的二叉树,共有空指针＿＿＿＿个。

16.前序为ABC且后序为CBA的二叉树共有＿＿＿＿种。

17.三个结点可以组成＿＿＿＿种不同形态的树。

18.将一棵完全二叉树按层次编号,对于任意一个编号为i的结点,其左孩子结点的编＿＿＿＿号为。

19.给定如图6－39所示的二叉树,其前序遍历序列为＿＿＿＿。

20.给定如图6－40所示的二叉树,其层次遍历序列为＿＿＿＿。

图6－39　二叉树1

图6－40　二叉树2

三、选择题

1.树最适合用来表示（　　）。

A.有序数据元素　　　　　　　　　　B.无序数据元素

C.元素之间无联系的数据　　　　　　D.元素之间有分支的层次关系

2.前序为ABC的二叉树共有（　　）种。

A.2　　　　　　　B.3　　　　　　　C.4　　　　　　　D.5

3.根据二叉树的定义,具有3个结点的二叉树有（　　）种树型。

A.3　　　　　　　B.4　　　　　　　C.5　　　　　　　D.6

4.在一棵具有5层的满二叉树中,结点的总数为（　　）。

A.16　　　　　　B.31　　　　　　　C.32　　　　　　　D.33

5.具有64个结点的完全二叉树的深度为（　　）。

A.5　　　　　　　B.6　　　　　　　C.7　　　　　　　D.8

6.任何一棵二叉树的叶结点在前序、中序、后序遍历序列中的相对次序（　　）。

A.不发生改变　　　B.发生改变　　　C.不能确定　　　D.以上都不对

7.A,B为一棵二叉树上的两个结点,在中序遍历时,A在B前的条件是（　　）。

A.A在B右方　　　B.A是B祖先　　　C.A在B左方　　　D.A是B子孙

8.下列4棵树中,（　　）不是完全二叉树。

9.如图6－41所示的二叉树,后序遍历的序列是（　　）。

A.ABCDEFGHI　　B.ABDHIECFG　　C.HDIBEAFCG　　D.HIDEBFGCA

10.如图6－42所示的二叉树,以下选项中是中序序列的为（　　）。

A.DBEHAFCG　　B.DBHEAFCG　　C.ABDEHCFG　　D.ABCDEFGH

图6－41　二叉树3

图6－42　二叉树4

11.某二又树的后序遍历序列为DABEC,中序遍历序列为DEBAC,则前序遍历序列为（　　）。

A.ACBED　　　B.DECAB　　　C.DEABC　　　D.CEDBA

12.具有n（n＞1）个结点的完全二叉树中,结点i（2i＞n）的左孩子结点是（　　）。

A.2i　　　B.2i＋1　　　C.2i－1　　　D.不存在

13.把一棵树转换为二叉树后,这棵二叉树的形态是（　　）。

A.唯一的　　　　　　　　　　　　　　　B.有多种

C.有多种,但根结点都没有左孩子结点　　D.有多种,但根结点都没有右孩子结点

14.将一棵有100个结点的完全二叉树从上到下,从左到右依次对结点编号,根结点的编号为1,则编号为45的结点的左孩子结点编号为（　　）。

A.46　　　　　B.47　　　　　C.90　　　　　D.91

15.将一棵有100个结点的完全二叉树从上到下,从左到右依次对结点编号,根结点的编号为1,则编号为49的结点的右孩子结点编号为（　　）。

A.98　　　　　B.99　　　　　C.50　　　　　D.100

16.二叉树按某种顺序线索化后,任一结点均有指向其前驱结点和后继结点的线索,这种说法（　　）。

A.正确　　　B.错误　　　C.不确定　　　D.都有可能

17.下列陈述正确的是（　　）。

A.二叉树是度为2的有序树

B.二叉树中结点只有一个孩子结点时无左右之分

C.二叉树中必有度为2的结点

D.二叉树中最多只有两棵子树,并且有左、右子树之分

18.用5个权值{3,2,4,5,1}构造的哈夫曼树的带权路径长度是（　　）。

A.32　　　　B.33　　　　C.34　　　　D.15

19.在树结构中,若结点B有4个兄弟,A是B的父亲结点,则A的度为（　　）。

A.3　　　　B.4　　　　C.5　　　　D.6

20.二叉树的叶结点个数比度为2的结点的个数（　　）。

A.无关　　　B.相等　　　C.多一个　　　D.少一个

四、简答题

1.已知一棵树边的集合如下,请画出此树,并回答问题。

{（L,M）,（L,N）,（E,L）,（B,E）,（B,D）,（A,B）（G,J）,（G,K）,（C,G）,（C,F）,（H,I）,（C,H）,（A,C）}

（1）哪个结点是根结点？　（2）哪些结点是叶结点？　（3）哪个结点是G的双亲？（4）哪些结点是G的祖先？　（5）哪些结点是G的孩子？　（6）哪些结点是E的子孙？（7）哪些结点是E的兄弟？哪些结点是F的兄弟？　（8）结点B和N的层次各是多少？（9）树的深度是多少？　（10）以结点C为根的子树的深度是多少？　（11）树的度数是多少？

2.设如图6－43所示的二叉树是与某森林对应的二叉树,试回答下列问题。

图6－43　二叉树

（1）森林中有几棵树？

（2）每一棵树的根结点分别是什么？

（3）第一棵树有几个结点？

（4）第二棵树有几个结点？

（5）森林中有几个叶结点？

3.二叉树按中序遍历的结果为ABC,试问有几种不同形态的二叉树可以得到这一遍历结果？并画出这些二叉树。

4.分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。

五、应用题

1.已知一棵二叉树的后序遍历和中序遍历的序列分别为ACDBGIHFE和ABCDEFGHI。请画出该二叉树,并写出它的前序遍历的序列。

2.已知一棵二叉树的前序遍历和中序遍历的序列分别为ABDGHCEFI和GDHBAECIF。

请画出此二叉树,并写出它的后序遍历的序列。

3.已知一棵树的层次遍历的序列为ABCDEFGHIJ,中序遍历的序列为DBGEHJACIF。请画出该二叉树,并写出它的后序遍历的序列。

4.把下列一般树转换为二叉树。

5.把下列森林转换为二叉树。

6.把下列二叉树还原为森林。

7.某二叉树的结点数据采用顺序存储,其结构如下。

（1）画出该二叉树。

（2）写出按层次遍历的结点序列。

8.某二叉树的存储如下。

其中,根结点的指针为6,lchild、rchild分别为结点的左、右孩子的指针域,data为数据域。

（1）画出该二叉树。

（2）写出该树的前序遍历的结点序列。

9.如图6－44所示的二叉树,请画出与其对应的中序线索二叉树。

图6－44　二叉树6

10.画出表达式－A＋B－C＋D的标识符树,并求它们的后缀表达式。

11.画出表达式（A＋B/C－D）＊（E＊（F＋G））的标识符树,并求它们的后缀表达式。

12.画出表达式（A＋B＊C/D）＊E＋F＊G的标识符树,并求它们的后缀表达式。

13.给定一个权集W＝{4,5,7,8,6,12,18},试画出对应的哈夫曼树,并计算其带权路径长度WPL。

14.给定一个权集W＝{3,15,17,14,6,16,9,2},试画出对应的哈夫曼树,并计算其带权路径长度WPL。

15.假设用于通信的电文仅由A、B、C、D、E、F、G、H8个字母组成,字母在电文中出现的频率分别为7,19,2,6,32,3,21,10。试为这8个字母设计哈夫曼编码。

六、编程题

以二叉链表为存储结构,设二叉树BT结构如下。

（1）求二叉树中的度数为2的结点。

（2）求二叉树中值最大的元素。

（3）将二叉树各结点存储到一维数组中。

（4）前序输出二叉树中各结点及其结点所在的层号。

（5）求二叉树的宽度。

（6）交换二叉树各结点的左、右子树。

（7）写出在二叉树中查找值为x的结点在树中层数的算法。