-树和二叉树练习题及答案

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

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

3、非线性结构线性化的过程(V) 19、树的先根遍历序列与其所转化的二叉树的先序遍历序列相同。(X) 20、树的后根遍历序列与其所转化的二叉树的后序遍历序列相同。二、填空.由3个结点所构成的二叉树有5_种形态。.线索二叉树的左线索指向其前驱，右线索指向其后继 。. 一棵具有257个结点的完全二叉树，它的深度为 9。4、如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为69。.设一棵完全二叉树具有1000个结点，则此完全二叉树有500个叶子结点，有499 个度为2的结点，有 1 个结点只有非空左子树，有 0个结点只有非空右子树。答：最快方法：用叶子数曰n/2=500二n0-

4、1=4。另外，最后一结点为2i属于 左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空 右不空的情况，所以非空右子树数=0. 一棵含有n个结点的k叉树，可能达到的最大深度为 0，最小深度为2。.若已知一棵二叉树的前序序列是BEFCGDH,中序序列是FEBGCHD,则它的后序序列 必是 F E G H D C B。.在二叉树中，指针p所指结点为叶子结点的条件是 p-lchild=null & p-rchlid=null 。三、选择题.某二叉树结点的中序序列为A、B、C、D、E、F、G,后序序列为B、D、C、A、F、G、 E,则其左子树中结点数目为（。A） 3B） 2C）

5、 4D） 5.二叉树是非线性数据结构，所以（C ）。A、它不能用顺序存储结构存储；B、它不能用链式存储结构存储；C、顺序存储结构和链式存储结构都能存储；D、顺序存储结构和链式存储结构都不 能使用.具有n（n0）个结点的完全二叉树的深度为（C ）。（A）促（B） L促（C） L3+1（D）l0g2（n）+1】.把一棵树转换为二叉树后，这棵二叉树的形态是（A ）。（A）唯一的（B）有多种（C）有多种，但根结点都没有左孩子（D）有多种，但根结点都没有右孩子.线索二叉树是一种（C ）结构。A.逻辑 B.逻辑和存储C.物理D.线性6、将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结

6、点进 行编号，根结点编号为1，则编号为49的结点的左孩子的编号为（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 ）A、加快查找结点的前驱或后继的速度B、为了能在二叉树中方便的进行插入与删除配为了能方便的找到双亲D、使

7、二叉树的遍历结果唯一.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是 (B )A. 9B. 11C. 15D.不确定.一棵树深度为K的完全二叉树至少有( C )个结点A. 2k - 1B. 2k-1 - 1 C. 2k-1D. 2k.一棵二叉树的前序遍历序列为ABCDEFG,它的中序遍历序列可能是（ B ）A. CABDEFGB. ABCDEFGC. DACEFBGD. ADCFEG.有关二叉树下列说法正确的是（B ）A.二叉树的度为2B. 一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为2. 一个具有1025个结点的二叉树

8、的高h为（ C ）A. 11B. 10C. 11 至 1025 之间D. 10 至 1024 之间. 一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有（B）结点A. 2hB. 2h-1C. 2h+1D. h+1.对于有n个结点的二叉树，其高度为（D）A. nlog2nB. 10g2nC.10g2n+1D.不确定.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac ,它的先序遍历是（D ）。A.acbedB.decab C.deabcD.cedba.若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用 （C）遍历方法最合适。A.前序B.中序C.

9、后序0.按层次.在下列存储形式中，哪一个不是树的存储形式？（D ）A.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法.在下列关于二叉树的叙述中，正确的是（ D ）只有一个结点的二叉树度为0;二叉树的度为2；二叉树的左右子树可任 意交换;深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A.B.C.D.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为（C）A.X的双亲B.X的右子树中最左的结点C.X的左子树中最右结点D.X的左子树中最右叶结点.在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序 （ B ）A.都不相同 B.完全相同C

10、.先序和中序相同，而与后序不同D.中序和后序相同，而与先序不同.在线索化二叉树中，t所指结点没有右子树的充要条件是（A ）。A、 t-Rtag=1B、 t-Rchild=NULLC、t-Rtag=1 且 t-Rchild=NULLD、以上都不对24、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（B）。A. 2hC. 2h+125、如右图所示二叉树的中序遍历序列是A. abcdgef B. dfebagc C. dbaefcg 数至少为（B）。A. 2hC. 2h+125、如右图所示二叉树的中序遍历序列是A. abcdgef B. dfebagc C. dba

11、efcg 26、设a和b为一棵二叉树上的两个结点a是b的左孩子2h-1D. h+1（B）。D. defbagc在中序遍历时，a在b前的条件是（D）。b是a的右孩子a是b左子树上结点或b是a右子树上结点D.以上三项均可27、假定在一棵二叉树中，双分支结点数为15,单分支结点数为30,则叶子结点数为 （C）个。A. 45B. 15C. 16D. 3128、树的基本遍历策略可分为先根遍历和后根遍历；二叉树的遍历策略分为先序、中序 和后序遍历。这里把由树转化得到的二叉树叫做这棵树对应的二叉树。以下结论（A） 是正确的。A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同B.树的后根遍历序列与其对应的

12、二叉树的后序遍历序列相同C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同D.以上都不对29、如下图所示的4棵二叉树，（C）不是完全二叉树。30、设哈夫曼树中的叶子结点总数为m,若用二叉链表作为存储结构，则该哈夫曼树中 总共有6）个空指针域。A. 2m-1B. 2mC. 2m+1D. 4m31、二叉树的第k层的结点数最多为（D ）A. 2k-1B. 2K+1C. 2K-1D. 2k-132、设某棵二叉树中有2000个结点，则该二叉树的最小高度为（C ）。A.9B.10C.11D.1233、一棵有n个结点的树，在把它转换成对应的二叉树后，该二叉树根结点的左子树上 共有（B ）个结点。A. n

13、-2B. n-1C. n+1D. n+2 34、对于一棵深度为4的三叉树，最多有（C ）个结点。A. 30B. 36C. 40D. 5435、设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为(B )。(A) 3(B) 4(C) 5(D) 1四、简答题1.给定二叉树的两种遍历序列，分别是：前序遍历序列：D, A, C, E, B, H, F, G, I； 中序遍历序列：D, C, B, E, H, A, G, I, F,试画出二叉树B。解：方法是：由前序先确定root,由中序可确定root的左、右子树。然后由其左子树 的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继

14、续确定root的左右 孩子。将他们分别作为新的root,不断递归，则所有元素都将被唯一确定，问题得解。 2、已知一棵二叉树，其中序序列DBCAFGE,后序序列DCBGFEA,构造该二叉树。3、给定权值8, 12, 4, 5, 26, 16, 9,构造一棵带权路径长度最短的二叉树，并计算其带权路径长度。WPL=8 X 3+4 X 4+5 X 4+16 X 2+9 X 3+12 X 3+26 X 2 =207注:哈夫曼树的左右子树可以互换。4.把如图所示的树转化成二叉树。4.把如图所示的树转化成二叉树。答：注意全部兄弟之间都要连线（包括度为2的兄弟），并注意原有连线结点一律归入 左子树，新添连线结点一律归入右子树。/ A/ 1.- .、./ CI H DL.- G kM J5、画出和下列二叉树相应的森林。答：注意根右边的子树肯定是森林，而孩子结点的右子树均为兄弟。（100（100/ （40）19216、假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07,0.1