3.5 习题练习

1 已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其
前缀形式为( )
A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE

2 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则
T中的叶子数为（ ）
A．5 B．6 C．7 D．8

3 在下述结论中，正确的是（ ）
①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换; ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A．①②③ B．②③④ C．②④ D．①④

4 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和
M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）
A．M1 B．M1+M2 C．M3 D．M2+M3

5 一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）
A． 250 B． 500 C．254 D．505 E．以上答案都不对

6 若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（ ）。
A．n-1 B．ën/mû-1 C．é(n-1)/(m-1)ù D． én/(m-1)ù-1 E．é(n+1)/(m+1)ù-1

7 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高
度（）
A．4 B．5 C．6 D．7

8 一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）
A．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEG

9 对于前序遍历与中序遍历结果相同的二叉树为（1）;
对于前序遍历和后序遍历结果相同的二叉树为（2）。
A．一般二叉树 B．只有根结点的二叉树 C．根结点无左孩子的二叉树
D．根结点无右孩子的二叉树 E．所有结点只有左子数的二叉树
F．所有结点只有右子树的二叉树

10 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( )。
A. 0 B. 1 C. 2 D. 不确定

11 （ ）的遍历仍需要栈的支持.
A．前序线索树 B．中序线索树 C．后序线索树

12 二叉树在线索后，仍不能有效求解的问题是（ ）。
A．前（先）序线索二叉树中求前（先）序后继
B．中序线索二叉树中求中序后继
C．中序线索二叉树中求中序前驱
D．后序线索二叉树中求后序后继

13 下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点
序列按其关键字有序（）。
A．二叉排序树 B．哈夫曼树 C．AVL树 D．堆

14 下面几个符号串编码集合中，不是前缀编码的是（ ）。
A．{0,10,110,1111} B．{11,10,001,101,0001}
C．{00,010,0110,1000} D．{b,c,aa,ac,aba,abb,abc

15 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )
A．（100，80， 90， 60， 120，110，130）
B.（100，120，110，130，80， 60， 90）
C.（100，60， 80， 90， 120，110，130）
D. (100，80， 60， 90， 120，130，110)

16 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并
已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。
A. LL B. LR C. RL D. RR

17 从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。

18 一个深度为L的满K叉树有以下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树，如果按层次顺序从1开始对全部结点进行编号，求：1）各层的结点的数目是多少？ 2）编号为n的结点的双亲结点（若存在）的编号是多少？3）编号为n的结点的第i 个孩子结点（若存在）的编号是多少？4）编号为n的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？

19 若一棵树中有度数为1至m的各种结点数为n1,n2,...,nm(nm表示度数为m的结点个数)请推导出该树中共有多少个叶子结点n0的公式。

20 对于具有n个叶子结点，且所有非叶子结点都有左右孩子的二叉树，
(1)试问这种二叉树的结点总数是多少？

(2)试证明 。其中: 表示第i个叶子结点所在的层号(设根结点所在层号为1)。

21 试证明：仅仅已知一棵二叉树的后序遍历序列和先序遍历序列，不能唯一地确定这棵二叉树。

22 设某二叉树的前序遍历序列为:ABCDEFGGI，中序遍历序列为:BCAEDGHFI：
（1）试画出该二叉树；
（2）写出由给定的二叉树的前序遍历序列和中序遍历序列构造出该二叉树的算法。
（3）设具有四个结点的二叉树的前序遍历序列为abcd；S为长度等于四
的由a，b，c，d排列构成的字符序列，若任取S作为上述算法的中
序遍历序列，试问是否一定能构造出相应的二叉树，为什么？试列出具
有四个结点二叉树的全部形态及相应的中序遍历序列。

23 对于二叉树T的两个结点n1和n2，我们应该选择树T结点的前序、中序和
后序中哪两个序列来判断结点n1必定是结点n2的祖先,并给出判断的方法。不需证明判断方法的正确性。

24 假设一个二叉树的两种遍历如下：
前序：ABFGCHDEIJLK 中序：FGBHCDILJKEA
（1）画出这棵二叉树以及它的中序线索树；
（2）写出在中序线索树的情况下，找到结点N的前驱结点的算法
INORDER-PRIOR(N,X)

25 如果一棵huffman树T有n0个叶子结点，那么，树T有多少个结点，要求给
出求解过程。

26 假定用两个一维数组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的后代的算法。

27 假设二元树用左右链表示，试编写一算法，判别给定二元树是否为完全二元
树？

28 假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给
定的树的深度的算法。（注:已知树中结点数）

29 以孩子兄弟链表为存储结构，请设计递归和非递归算法求树的深度。

30 已知一棵二叉树的中序序列和后序序列，写一个建立该二叉树的二叉链表存
储结构的算法。

31 给出中序线索树的结点结构并画出一个具有头结点的中序线索树，使其树结
点至少应有6个。写一算法在不使用栈和递归的情况下前序遍历一中序线索树，并分析其时间复杂性。