数据结构之【树形结构】复习题

第五章 树形结构

一、选择题

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

A．-A+B*C/DE B.-A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE

2．算术表达式a+b*（c+d/e）转为后缀表达式后为（ B）

A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++

3. 设有一表示算术表达式的二叉树（见下图），

它所表示的算术表达式是（ C ）

A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G)

C. (A*B+C)/(D*E+（F-G）) D. A*B+C/D*E+F-G

4. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ D ）

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

5. 在下述结论中，正确的是（ D ）

①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;

④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A．①②③ B．②③④ C．②④ D．①④

6. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ A ）

A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定

7. 树是结点的有限集合，它（ (1）)根结点，记为T。其余结点分成为m（m>0）个(（2）)的集合T1，T2， …，Ｔm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。一个结点的子结点个数称为该结点的( （3） )。二叉树与树是两个不同的概念，二叉树也是结点的有限集合，它(（4）)根结点。可以把树的根结点的层数定义为1，其他结点的层数等于其父结点所在层数加上1。令T是一棵二叉树，Ki和Kj是T中子结点数小于2的结点中的任意两个，它们所在的层数分别为λKi和λKj，当关系式│λKi-λKj│≤1一定成立时，则称T为一棵（(5)）。供选择的答案：CACAC

（1）(4) A. 有0个或1个 B. 有0个或多个 C. 有且只有一个 D. 有1个或1个以上

（2） A. 互不相交 B.允许相交 C.允许叶结点相交 D.允许树枝结点相交

（3） A. 权 B.维数 C.次数 D.序

（5） A. 丰满树 B.查找树 C.平衡树 D.完全树

8．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B ）

A．9 B．11 C．15 D．不确定

9．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（C ）个

A．4 B．5 C．6 D．7

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

A．M1 B．M1+M2 C．M3 D．M2+M3

11．具有10个叶结点的二叉树中有（ B ）个度为2的结点，

A．8 B．9 C．10 D．ll

12．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ E）

A． 250B． 500 C．254 D．505 E．以上答案都不对

13. 设给定权值总数有n 个，其哈夫曼树的结点总数为( D )

A．不确定 B．2n C．2n+1 D．2n-1

14. 有n个叶子的哈夫曼树的结点总数为（ D ）。

A．不确定 B．2n C．2n+1 D．2n-1

15．若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（C ）。

A．n-1 B．ën/mû-1 C．é(n-1)/(m-1)ù D． én/(m-1)ù-1 E．é(n+1)/(m+1)ù-1

16. 有关二叉树下列说法正确的是（B ）

A．二叉树的度为2 B．一棵二叉树的度可以小于2

C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2

17．二叉树的第I层上最多含有结点数为（ C ）

A．2^I B． 2^I-1-1 C． 2^I-1 D．2^I -1

18. 一个具有1025个结点的二叉树的高h为（ C ）

A．11 B．10 C．11至1025之间 D．10至1024之间

19．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( B )结点

A．2h B．2h-1 C．2h+1 D．h+1

20．对于有n 个结点的二叉树, 其高度为（ D ）

A．nlog₂n B．log₂n C．ëlog₂nû|+1 D．不确定

21. 一棵具有 n个结点的完全二叉树的树高度（深度）是（ A ）

A．ëlognû+1 B．logn+1 C．ëlognû D．logn-1

22．深度为h的满m叉树的第k层有（ A ）个结点。(1=<k=<h)

A．m^k-1 B．m^k-1 C．m^h-1 D．m^h-1

23．在一棵高度为k的满二叉树中，结点总数为（ C ）

A．2^k-1B．2^k C．2^k-1D．ëlog2^kû+1

24．高度为 K的二叉树最大的结点数为（ C ）。

A．2^k B．2^{k-1 C}．2^k -1 D．2^k-1-1

25. 一棵树高为K的完全二叉树至少有（C ）个结点

A．2^k –1 B. 2^k-1 –1 C. 2^k-1D. 2^k

26. 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（C）

A．4 B．5 C．6 D．7

27. 利用二叉链表存储树，则根结点的右指针是（ C ）。

A．指向最左孩子 B．指向最右孩子 C．空 D．非空

28．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( C )次序的遍历实现编号。

A．先序 B. 中序 C. 后序 B D. 从根开始按层次遍历

29．树的后根遍历序列等同于该树对应的二叉树的( ).

A. 先序序列B. 中序序列 C. 后序序列

30．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( C )遍历方法最合适。

A．前序 B．中序 C．后序 D．按层次

31．在下列存储形式中，哪一个不是树的存储形式？（ D ）】

A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法

32．一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（B ）

A．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEG

33．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（A ）。

A．CBEFDA B． FEDCBA C． CBEDFA D．不定

34．已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ D ）。

A．acbed B．decab C．deabc D．cedba

35. 某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则前序序列是：B

A．E,G,F,A,C,D,B B．E,A,C,B,D,G,F C．E,A,G,C,F,B,D D．上面的都不对

36. 上题的二叉树对应的森林包括多少棵树（ B ）

A．l B．2 C．3 D．概念上是错误的

37．二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是： C

A、 E B、 F　C、 G　 D、 H

38．将一棵树t 转换为孩子—兄弟链表表示的二叉树h，则t的后根序遍历是h 的

A．前序遍历 B．中序遍历 C．后序遍历（ B ）

39. 某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号为1，2，… ，n，且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1。这时是按( B)编号的。

A.中序遍历序列 B.前序遍历序列 C.后序遍历序列 D.层次顺序

40．下面的说法中正确的是（ B ）.

（1）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变；

（2）按二叉树定义，具有三个结点的二叉树共有6种。

A．(1)(2) B．(1) C．(2) D．(1)、(2)都错

41．对于前序遍历与中序遍历结果相同的二叉树为（1）F;

对于前序遍历和后序遍历结果相同的二叉树为（2）。B

A．一般二叉树B．只有根结点的二叉树C．根结点无左孩子的二叉树

D．根结点无右孩子的二叉树E．所有结点只有左子数的二叉树 F．所有结点只有右子树的二叉树

42．C一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）

A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点D．是任意一棵二叉树

43．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ B ）

A．都不相同　　B．完全相同C．先序和中序相同，而与后序不同　

D．中序和后序相同，而与先序不同

44．某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（C）的二叉树。

A．空或只有一个结点 B．任一结点无左子树 C．高度等于其结点数 D．任一结点无右子树

45．在完全二叉树中，若一个结点是叶结点，则它没（ C ）。

A．左子结点 B．右子结点　 C．左子结点和右子结点 D．左子结点，右子结点和兄弟结点

46．在下列情况中，可称为二叉树的是（ B ）

A．每个结点至多有两棵子树的树B. 哈夫曼树C．每个结点至多有两棵子树的有序树

D. 每个结点只有一棵右子树 E．以上答案都不对

47. 一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：( D )

A．不确定 B. 0 C.1 D. 2

48. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：(B )。

A. 0 B. 1 C. 2 D. 不确定

49. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( C)

A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点 D.X的左子树中最右叶结点

50. 引入二叉线索树的目的是（ A ）

A．加快查找结点的前驱或后继的速度B．为了能在二叉树中方便的进行插入与删除

C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一

二、判断题

×1. 二叉树是度为2的有序树。

×2.完全二叉树一定存在度为1的结点。

×3. 对于有N个结点的二叉树，其高度为log₂n。

√4．深度为K的二叉树中结点总数≤2^k-1。

√5. 二叉树以后序遍历序列与前序遍历序列反映的同样的信息(他们反映的信息不独立）。

√6. 二叉树的遍历结果不是唯一的.

√7. 二叉树的遍历只是为了在应用中找到一种线性次序。

√9. 一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。

×10. 二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道该树的根结点是那一个，则可以确定这棵二叉树。

×11. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。

×13．用树的前序遍历和中序遍历可以导出树的后序遍历。

√14．采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。

×15. 用一维数组存储二叉树时，总是以前序遍历顺序存储结点。

√22．完全二叉树中，若一个结点没有左孩子，则它必是树叶。

×23. 二叉树只能用二叉链表表示。

×24. 一棵有n个结点的二叉树，从上到下，从左到右用自然数依次给予编号，则编号为i的结点的左儿子的编号为2i(2i< n)，右儿子是2i+1（2i+1<n）。

25. 给定一棵树，可以找到唯一的一棵二叉树与之对应。

×26. 一棵树中的叶子数一定等于与其对应的二叉树的叶子数。

×39．度为二的树就是二叉树。

×40．深度为k具有n个结点的完全二叉树，其编号最小的结点序号为 ë2^k-2û+1。

41.下面二叉树的定义只有一个是正确的，请在正确的地方画“√”。

（1）它是由一个根和两株互不相交的、称为左子树和右子树的二叉树组成。

（2）（a）在一株二叉树的级i上，最大结点数是2^i-1（i≥1）

（b）在一棵深度为k的二叉树中，最大结点数是2^k-1+1（k≥1）。

√（3）二叉树是结点的集合，满足如下条件：

（a）它或者是空集；

（b）或者是由一个根和两个互不相交的、称为左子树和右子树的二叉树组成。

×46. 一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。

×47. 哈夫曼树无左右子树之分。

×48．当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。

√49．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。

√50. 用链表（llink-rlink）存储包含n个结点的二叉树时，结点的2n个指针区域中有n+1个空指针。( )

三、填空题

1．二叉树由_(1)根节点__，__(2)左子树_，_(3)右子树__三个基本单元组成。

4．中缀式a+b*3+4*（c-d）对应的前缀式为__(1)++a*b3*4-cd_，若a=1，b=2，c=3，d=4，则后缀式db/cc*a-b*+的运算结果为_(218)__。

5．二叉树中某一结点左子树的深度减去右子树的深度称为该结点的__平衡因子__。

6．具有256个结点的完全二叉树的深度为_9_____。

7．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有__12____个叶子结点。

8．深度为k的完全二叉树至少有___(1)2^k-1____个结点，至多有___(2) 2^k-1____个结点。

9．深度为H 的完全二叉树至少有_(1) 2^？H-1____个结点；至多有_(2) 2^H-1____个结点；H和结点总数N之间的关系是(3)_H=[log₂N] +1_向下取整。

10．在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。

11．在完全二叉树中，编号为i和j的两个结点处于同一层的条件是_[log₂i]= [log₂j]_____。

12．一棵有n个结点的满二叉树有_0_(1)_个度为1的结点、有__(2)（n-1）/2_个分支（非 终端）结点和__(3)（n+1）、2_个叶子，该满二叉树的深度为_(4) [log₂n]+1 向下取整__。

13．假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是__n____。

14．在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =__N2+1____

15．设只含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为_2^k+1-1______,最小结点数为____k+1__。

16．设有N个结点的完全二叉树顺序存放在向量A[1:N]中，其下标值最大的分支结点为___[N/2]向下取整___。

17．高度为K的完全二叉树至少有__2^k-2____个叶子结点。

18．高度为8的完全二叉树至少有___64___个叶子结点。

19．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是___99___。

30．8层完全二叉树至少有__128____个结点，拥有100个结点的完全二叉树的最大层数为___7___。

31．含4个度为2的结点和5个叶子结点的二叉树，可有___0至多个___个度为1的结点。

四、应用题

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

树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。

树和二叉树的区别有三：一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分枝的情况下， 也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。

2．树和二叉树之间有什么样的区别与联系？

3．已知一棵二叉树的对称序和后序序列如下：

对称序：GLDHBEIACJFK 后序： LGHDIEBJKFCA

(1) 出这棵二叉树：

(2) 转换为对应的森林：

4．设某二叉树的前序遍历序列为:ABCDEFGGI，中序遍历序列为:BCAEDGHFI：

（1）试画出该二叉树；

（2）写出由给定的二叉树的前序遍历序列和中序遍历序列构造出该二叉树的算法。

（1）已知二叉树的先序序列: CBHEGAF, 中序序列: HBGEACF, 试构造该二叉树

（2）已知二叉树按中序排列为BFDAEGC，按前序排列为ABDFCEG，要求画出该二叉树。

（3）已知一棵二叉树的前序序列A,B,D,C,E,F，中序序列B,D,A,E,F,C. 画出这棵二叉树。

（4）已知一棵二叉树的前序遍历结果是：ABCDEFGHIJ,中序遍历的结果是：BCEDAGHJIF,试画出这棵二叉树。

（5）已知二叉树BT各结点的先序、中序遍历序列分别为ABCDEGF和CBAEDF，试画出该二叉树。