第章树和二叉树练习题及答案

1、(V)1.若二叉树用二叉链表作存贮结构，则在 n 个结点的二叉树链表中只有 n 1 个非空指针域。(X) 2.二叉树中每个结点的两棵子树的高度差等于1。(V)3. 二叉树中每个结点的两棵子树是有序的。(X) 4. 二叉树中每个结点有两棵非空子树或有两棵空子树。(X) 5.二叉树中所有结点个数是 2k-1-1，其中 k 是树的深度。(应 2i-1 )(X) 6. 二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。(X) 7. 对于一棵非空二叉树，它的根结点作为第一层，则它的第 i 层上最多能有 2i1 个结点。(应 2i-1)(V)8. 用二叉链表法存储包含 n 个结点的二叉树，结点的

2、 2n 个指针区域中有 n+1 个 为空指针。(V)9. 具有 12 个结点的完全二叉树有 5 个度为 2 的结点。() 10 、哈夫曼树中没有度为 1 的结点，所以必为满二叉树。() 11、在哈夫曼树中，权值最小的结点离根结点最近。()12 、线索二叉树是一种逻辑结构。(V) 13、深度为 K 的完全二叉树至少有 2K-1个结点。(V)14、具有 n 个结点的满二叉树，其叶结点的个数为(n+1)12。(V)15 、前序和中序遍历用线索树方式存储的二叉树，不必使用栈。(X)16、哈夫曼树是带权路径长度最短的树，路径上权值较大的点离根较远。(V)17、在二叉树结点的先序序列和后序序列中，所有叶子

3、结点的先后顺序完全相同。(V)18、二叉树的遍历操作实际上是将非线性结构线性化的过程V)19、树的先根遍历序列与其所转化的二叉树的先序遍历序列相同(X)20、树的后根遍历序列与其所转化的二叉树的后序遍历序列相同、填空1.由3个结点所构成的二叉树有 _5_ 种形态。2.线索二叉树的左线索指向其 前驱_，右线索指向其 后继_。3._ 一棵具有 257 个结点的完全二叉树，它的深度为 _9_ 。4. 如某二叉树有 20 个叶子结点，有 30 个结点仅有一个孩子，则该二叉树的总结点数为 69Q5. 设一棵完全二叉树具有 1000 个结点，则此完全二叉树有 500 个叶子结点，有 499个度为 2 的结

4、点，有_1_个结点只有非空左子树，有_0_个结点只有非空右子树。答：最快方法：用叶子数=n/2 = 500 , n2=n-1=499。另外，最后一结点为 2i 属于 左叶子，右叶子是空的，所以有 1 个非空左子树。完全二叉树的特点决定不可能有左空 右不空的情况，所以非空右子树数=0.6. 一棵含有 n 个结点的 k 叉树，可能达到的最大深度为，最小深度为_2_Q7.若已知一棵二叉树的前序序列是BEFCGD,H 中序序列是 FEBGCHD 则它的后序序列必是 F E G H D C B_Q8.在二叉树中，指针 p 所 指结点为叶子结点的条件是_ p-lchild=null&C、顺序存储结

5、构和链式存储结构都能存储；D、顺序存储结构和链式存储结构都不能使用3.具有 n(n0)个结点的完全二叉树的深度为(C )。(A) log2(n)(B) IL log2(n)(C) lljog2(n)+1(D) log2(n)+14.把一棵树转换为二叉树后，这棵二叉树的形态是(A)0(A)唯一的(B)有多种(C)有多种， 但根结点都没有左孩子(D)有多种，但根结点都没有右孩子5.线索二叉树是-一种(C)结构。A.逻辑B.逻辑和存储C .物理D .线性6、 将一棵有 100 个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进 行编号，根结点编号为 1,则编号为 49 的结点的左孩子的编号

6、为( A )A、98B、99C 、50D 、487、 设森林 F 中有三棵树，第一、第二和第三棵树的结点个数分别为M1 M2 和 M3 与森林 F 对应的二叉树根结点的右子树上的结点个数是(D)A) M1B ) M1+M2 C ) M3 D ) M2+M38、将一棵有 100 个结点的完全二叉树从根开始，每一层从左到右依次对结点进行编号，根结点编号为 1,则编号最大的非叶结点的编号为(C)A、48B 49C、50D 519. 引入二叉线索树的目的是(A )p-rchlid=null_。三、选择题1 某二叉树结点的中序序列为A、B、CE,则其左子树中结点数目为(C)A) 3B ) 2C2二叉树是

7、非线性数据结构，所以( CD、E、F、G,后序序列为 B、D、C A、F、G)4D) 5)QA、它不能用顺序存储结构存储E、它不能用链式存储结构存储A、加快查找结点的前驱或后继的速度B、为了能在二叉树中方便的进行插入与删除C、为了能方便的找到双亲D、使二叉树的遍历结果唯一10.若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个数是(B )A. 9B. 11C . 15D.不确定11.一棵树深度为 K 的完全二叉树至少有( C )个结点12. 一棵二叉树的前序遍历序列为ABCDEFG 它的中序遍历序列可能是（B ）14. 一个具有 1025 个结点的二叉树的

8、高 h 为（15 . 一棵二叉树高度为 h,所有结点的度或为 0,或为 2,则这棵二叉树最少有（B ） 结点A. 2hB . 2h-1C . 2h+1D . h+116 .对于有 n 个结点的二叉树，其高度为（D）A . nlog2nB . log2nC log2n+1D .不确定17.已知某二叉树的后序遍历序列是dabec.中序遍历序列是debac,它的先序遍历是 (D)。A . acbedB. decabC. deabcD .cedba18 .若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用 （ C ）遍历方法最合适。A.前序B.中序C.后序D.按层次19 .在下列

9、存储形式中，哪一个不是树的存储形式？（D ）A.双亲表示法B .孩子链表表示法 C .孩子兄弟表示法 D .顺序存储表示法20 .在下列关于二叉树的叙述中，正确的是（A. 2k- 1k-1B. 2k-1C. 2D. 2A. CABDEFGB . ABCDEFGC. DACEFBGD . ADCFEG13.有关二叉树下列说法正确的是（A.二叉树的度为 2BB ）.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D .二叉树中任何一个结点的度都为2A. 11B. 10C . 11 至 1025 之间D . 10 至 1024 之间只有一个结点的二叉树度为0；二叉树的度为 2 ;二叉树的左

10、右子树可任 意交换；深度为 K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。A.B C D 21.若 X 是二叉中序线索树中一个有左孩子的结点，且 X 不为根，则 x 的前驱为（C ）A.X 的双亲B.X的右子树中最左的结点C.X 的左子树中最右结点D.X 的左子树中最右叶结点22. 在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ B ）A.都不相同B.完全相同C .先序和中序相同，而与后序不同D .中序和后序相同，而与先序不同23. 在线索化二叉树中，t 所指结点没有右子树的充要条件是（ A ）。At-Rtag=1B、t-Rchild=NULLC t-Rtag

11、=1 且 t-Rchild=NULLD、以上都不对24、 设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点 数至少为（B）。A. 2hB. 2h-1C. 2h+1D. h+125、如右图所示二叉树的中序遍历序列是（B）。A. abcdgef B. dfebagc C . dbaefcgD. defbagc26、 设 a 和 b 为一棵二叉树上的两个结点，在中序遍历时，a 在 b 前的条件是（D）A. a 是 b 的左孩子B. b 是 a 的右孩子27、 假定在一棵二叉树中，双分支结点数为15,单分支结点数为 30,则叶子结点数为 （C）个。A. 45B. 1

12、5C. 16D. 3128、树的基本遍历策略可分为先根遍历和后根遍历；二叉树的遍历策略分为先序、中序和后序遍历。这里把由树转化得到的二叉树叫做这棵树对应的二叉树。以下结论（A）是正确的。A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D. 以上都不对30、设哈夫曼树中的叶子结点总数为m 若用二叉链表作为存储结构，则该哈夫曼树中总共有（B）个空指针域。A. 2m-1B. 2mC.2m+1D. 4mC. a 是 b 左子树上结点或 b 是 a 右子树上结点D.以上三项均可31、二叉树

13、的第 k 层的结点数最多为（D )A. 2k-1B. 2K+1C.2K-1D. 2K-132、设某棵二叉树中有 2000 个结点，则该二叉树的最小高度为（ C ）0 0A. 9B. 10C. 11D. 1233、一棵有 n 个结点的树，在把它转换成对应的二叉树后，该二叉树根结点的左子树上共有(B )个结点34、对于一棵深度为 4 的三叉树，最多有(C )个结点A. 30B. 36C. 40D. 5435、设结点 A 有 3 个兄弟结点且结点 B 为结点 A 的双亲结点，则结点 B 的度数数为(B )(A) 3(B) 4(C) 5(D) 1四、简答题1. 给定二叉树的两种遍历序列，分别是：前序遍

14、历序列：D, A, C, E, B，H, F, G, I ；中序遍历序列：D, C, B, E, H, A, G I , F,试画出二叉树 Bo解：方法是：由前序先确定 root，由中序可确定 root 的左、右子树。然后由其左子树 的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root 的左右孩子。将他们分别作为新的 root，不断递归，则所有元素都将被唯一确定，问题得解。2、 已知一棵二叉树，其中序序列DBCAFGE 后序序列 DCBGFEA构造该二叉树。3、给定权值8 , 12 , 4, 5, 26, 16, 9，构造一棵带权路径长度最短的二叉树，并计算其带权路径长度。

15、A. n-2B. n-1C. n+1D. n+2解:WPL=8 X 3+4X4+5X4+16X2+9X3+12X3+26X2 =207注:哈夫曼树的左右子树可以互换。4.把如图所示的树转化成二叉树。左子树，新添连线结点一律归入右子树。5、画出和下列二叉树相应的森林。答：注意全部兄弟之间都要连线（包括度为2 的兄弟），并注意原有连线结点一律归入解:答：注意根右边的子树肯定是森林，而孩子结点的右子树均为兄弟6、假设用于通信的电文仅由 8 个字母组成，字母在电文中出现的频率分别为0.07 ,0.19，0.02 , 0.06 , 0.32 , 0.03 , 0.21 , 0.10。试为这8 个字母设计哈夫曼编码。解：哈夫