01.下列关于树的说法中，正确的是（D).
Ⅰ.对于有n个结点的二叉树，其高度为log2n
Ⅱ.完全二叉树中，若一个结点没有左孩子，则它必是叶结点
Ⅲ.高度为h (h>0)的完全二叉树对应的森林所含的树的个数一定是h
IV.一棵树中的叶子数一定等于与其对应的二叉树的叶子数
A.I和III. B.Ⅳ C.I.和Ⅱ D.Ⅱ
解析：Ⅰ若有n个结点的二叉树是一颗单支树，则其高度为n
Ⅱ完全二叉树中最多存在一个度为1的结点且只有左孩子，若不存在左孩子则一定也不存在右孩子，因此必是叶结点,正确
Ⅲ只有满二叉树对应的森林所含树的个数一定是h,如下图所示
Ⅳ 在树转换为二叉树时，若几个叶子结点具有共同的双亲，则转换为二叉树后只有一个叶结点(最右边的叶结点)，如下图所示
02．利用二叉链表存储森林时，根结点的右指针是（D )。
A.指向最左兄弟 B.指向最右兄弟 C.一定为空 D.不一定为空
解析:森林转换为二叉树，若森林只有一棵树，则根结点的有右指针为空，若存在第二棵树，则二叉链表的根结点的右指针指向的是森林中第二棵树的根结点
03．设森林F中有3棵树，第1、2、3棵树的结点个数分别为M1,M2和M3，与森林F对应的二叉树根结点的右子树上的结点个数是( D )。
A. M1 B.M1+M2 C. M3 D. M2+M3
解析:森林转换二叉树需要将每棵树的根结点全部视为兄弟结点的关系，树2做为树1根结点的右子树，树3作为树2根结点的右子树，因此森林F对应的二叉树根结点的右子树上的结点个数是M2+M3
04．设森林F中有4棵树，第1、2、3、4棵树的结点数分别为a、b、c和d，与森林F对应的二叉树的根结点的左子树上的结点数是( C)。
A. a B.b+c+d C. a-1 D. a+b+c
解析：森林转换为二叉树后，二叉树的根结点为第1棵树的根结点，二叉树的根结点的左子树包含第一棵树的所有孩子，所以不包括根结点
05．设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点数为n，森林F中第一棵树的结点数是( A ).
A. m-n B. m-n-1 C. n+1 D.条件不足，无法确定
解析：森林转换为二叉树时采用孩子兄弟表示法，根结点及其左子树为森林中的第一棵树，右子树为其他剩余的树，所以第一棵树的结点个数为m-n
06．设森林F对应的二叉树是一棵具有16个结点的完全二叉树，则森林F中树的数目和结点最多的树的结点数分别是( D )。
A.2和8 B.2和9 C.4和8 D.4和9
解析：森林转换为二叉树后，二叉树的根结点及其左子树由第一棵树转换得到，二叉树的根结点的右子树由剩余的森林转换得到，以此类推可划分出第2，3...棵树的结点，具有16个结点的完全二叉树的形态如下图所示，沿二叉树的根结点往右下遍历，共有四个结点，可知森林中由四棵树，其中第一棵结点数最多，有9个
07、森林T=(T1,T2,… , Tm）转化为二叉树BT的过程为:若m=0，则BT为空，若m≠ 0,则( B ).
A.将中间子树Tmid ( mid =(1+m)/2)的根作为BT的根; 将(T1,T2,… , Tmid-1)转换为BT的左子树; 将(Tmid+1,…., Tm)转换为BT的右子树
B.将子树T1的根作为BT的根; 将T1的子树森林转换成BT的左子树; 将(T2,T3,…, Tm)转换成BT的右子树
C.将子树T1的根作为BT的根; 将T1的左子树森林转换成BT的左子树; 将T1的右子树森林转换为BT的右子树; 其他以此类推
D.将森林T的根作为BT的根; 将(T1，T2,…,Tm)转化为该根下的结点，得到一棵树，然后将这棵树再转化为二叉树BT
解析：森林转二叉树是将森林中每棵树的根结点视为兄弟结点的关系，再按照“左孩子右兄弟”的规则来进行转化
08．设F是一个森林，B是由F变换来的二叉树。 若F中有n个非终端结点，则B中右指针域为空的结点有（ C ）个。
A. n-1 B. n C. n+1 D. n+2
解析：根据森林与二叉树转换规则“左孩子右兄弟”。二叉树B中右指针域为空代表该结点没有兄弟结点。森林中每棵树的根结点从第二个开始依次连接到前一棵树的根的右孩子，因此最后一棵树的根结点的右指针为空。另外，每个非终端结点，其所有孩子结点在转换之后，最后一个孩子的右指针也为空，所以树B中右指针域为空的结点有n+1个。
09.设某树的孩子兄弟链表示中共有6个空的左指针域、7个空的右指针域，包括5个结点的左、右指针域都为空，则该树中叶结点的个数是( B ).
A.7 B. 6 C. 5 D.不能确定
解析：树的孩子兄弟表示法中，若一个结点没有孩子，则表现为该结点的左指针域为空
10.若T是由有序树T转换而来的二叉树，则T中结点的后根序列就是T中结点的( B )序列。
A.先序 B.中序 C.后序 D.层序
11．某二叉树结点的中序序列为BDAECF，后序序列为DBEFCA，则该二叉树对应的森林包
括 （ C ）棵树。
A.1 B.2 C. 3 D.4
解析：根据中序和后序序列可以确定二叉树的形态，如下图所示，根据二叉树与森林的对应关系，森林中树的棵树即为对应二叉树的根结点A及其右兄弟数，所以森林中有三棵树，根结分别为ACF
12.设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲结点的右孩子，下列结论中正确的是(D).
A.在树T中，X是其双亲结点的第一个孩子 B.在树T中，X一定无右边兄弟
C.在树T中，X一定是叶结点 D.在树T中，X一定有左边兄弟
解析：在二叉树B中，X是其双亲的右孩子，因此在树T中，X必是其双亲结点的右兄弟，在二叉树中X必有左兄弟
13．在森林的二叉树表示中，结点M和结点N是同一父结点的左儿子和右儿子，则在该森林中( B ).
A.M和N有同一双亲 B.M和N可能无公共祖先
C.M是N的儿子 D.M是N的左兄弟
解析：在森林的二叉树表示中，当M和N的父结点是二叉树根结点是，M和N在不同树上
14.【2009统考真题】将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是( B ).
Ⅰ父子关系 Ⅱ．兄弟关系 Ⅲ. u的父结点与v的父结点是兄弟关系
A.只有Ⅱ B.I和Ⅱ C.I和Ⅲ D.I、II和Ⅲ
解析：森林转二叉树转换规则为左孩子右兄弟，在最后生成的二叉树中，父子关系在对应的森林关系中可能是兄弟关系或原本就是父子关系，情形如下：
若u的父结点与v的父节点是兄弟关系，则转换后，结点u和v分别在两者最左父结点的两棵子树中，不可能出现在同一路径中
15.【2011统考真题】已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是( D ).
A.115 B. 116 C.1895 D.1896
解析：树转换为二叉树时，树的每个分支结点的所有子结点中的最右子结点无右孩子，根结点转换后也没有右孩子，因此对应二叉树中无右孩子的结点个数=分支结点树+1=2011-116+1=1896
16.【2014统考真题】将森林F转换为对应的二叉树T，F中叶结点的个数等于( C ).
A.T中叶结点的个数 B.T中度为1的结点个数
C. T中左孩子指针为空的结点个数 D.T中右孩子指针为空的结点个数
解析：森林转换为二叉树相当于用孩子兄弟法来表示森林，变化过程中，原森林某结点的第一个孩子结点作为它的左子树，它的兄弟结点作为它的右子树，森林中的叶节点没有孩子结点，转换为二叉树时，该结点就没有左结点。
17.【2019统考真题】若将一棵树T转化为对应的二叉树BT，则下列对BT的遍历中，其遍历序列与T的后根遍历序列相同的是( B ).
A.先序遍历 B.中序遍历 C.后序遍历 D.按层遍历
18.【2020统考真题】已知森林F及与之对应的二叉树T,若F的先根遍历序列是a,b, c, d, e,f，后根遍历序列是 b, a, d,f, e, c，则T的后序遍历序列是（C )
A. b, a,d,f, e, c B. b,d,f, e, c,a
C. b,f, e, d, c, a D. f, e, d, c, b, a
解析：根据先序遍历和中序遍历可确定二叉树的结构
19.【2021统考真题】某森林F对应的二叉树为T，若T的先序遍历序列是a, b, d, c, e, g,f,中序遍历序列是b, d, a, e,g, c,f，则F中树的棵数是（ C )
A.1 B.2 C. 3 D.4
解析：先序 根左右 a b d c e g f
中序 左根右 b d a e g c f
可知二叉树形态如下，有三棵树acf
