课堂练习

1. 【NOIP2013】已知一棵二叉树有10个节点，则其中至多有()个节点有2个子节点。
   A.4
   B.5
   C.6
   D.7
   【答案】A
   【分析】对于任意一棵二叉树，度为2的结点数肯定比度为0的结点少1，在一棵含10个结点的二叉树中，度为2的结点数至多为4，如果超过4，则总结点数将超过10。完全二叉树满足度为2的结点数最多的情况。
2. 【NOIP2013】已知一棵二叉树有2013个节点，则其中至多有()个节点有2个子节点。
   A.1006
   B.1007
   C.1023
   D.1024
   【答案】A
   【分析1】对于任意一棵二叉树，度为2的结点数肯定比度为0的结点少1，在一棵含2013个结点的二叉树中，度为2的结点数至多为1006，如果超过1006，则总结点数将超过2013。
   【分析2】设度为0的结点数为$n_{0}$ ，度为1的结点数为$n_{1}$ ，度为2的结点数为$n_{2}$ ，由题意：$n_{0}+n_{1}+n_{2}=2013$ ，在二叉树中有$n_{0}=n_{2}+1$ ，所以有$2 \times n_{2}+n_{1}=2012$ ；所以$n_{1}$的值为偶数，最小值为0，可以得到$n_{2}=1006$ ，选A。
3. 【NOIP2011】如果根结点的深度记为1，则一棵恰有2011个叶结点的二叉树的深度最少是()。
   A.10
   B.11
   C.12
   D.13
   【答案】C
   【分析1】因为恰好是2011个叶节点，所以总节点个数最少要有4021个，深度最少，那就是每一层都要排满。既然排满那么前i的节点总数就是$2^{i}-1$ ，又因为$2^{11}-1<4021$且$2^{12}-1>4021$所以是12层。
   【分析2】如果这棵二叉树是完全二叉树，那么深度应该是最少的。必须是12层的完全二叉树的叶子结点才能达到2011个。
4. 【NOIP2010】如果树根算是第一层，那么一颗n层的二叉树最多有()个结点。
   A.$2^{n}-1$
   B.$2^{n}$
   C.$2^{n}+1$
   D.$2^{n+1}$
   【答案】A
   【分析】当该树为满二叉树时，这棵树拥有最多的结点，一颗n层二叉树有$2^{n}-1$ 结点。也可以用代入法。
5. 【NOIP2009】一个包含n个分支结点(非叶结点)的非空二叉树，它的叶结点数目最多为()。
   A.$2n+1$
   B.$2n-1$
   C.$n-1$
   D.$n+1$
   【答案】D
   【分析1】假设一颗树的边数为v，叶结点个数为x，则所有边分为两类：两端是分支结点$(n - 1)$条)或有一端是叶子结点(x条)，$x+n-1=v$ ，$v<=2 \times n$ ，所以叶结点数量最多为$n+1$ 。
   【分析2】题目要求叶结点数目最多，那么可以知道分支结点的度为2，假设叶结点数为x，结点数=边数+1；$x+n=2 \times n+1$ ，$x=n+1$ 。
   【分析3】题中$n=n_{1}+n_{2}$ ，因为$n_{0}=n_{2}+1$ ，所以$n_{0}=n-n_{1}+1<=n+1$ 。
6. 【NOIP2009】最优前缀编码，也称Huffman编码。这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码，以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码()。
   A.(00,01,10,11)
   B.(0,1,00,11)
   C.(0,10,110,111)
   D.(1,01,000,001)
   【答案】B
   【分析】Huffman编码不允许一个编码是另一个的前缀。B选项，当给00进行编码时，会出现编码不唯一的情况，可以由第三个00进行编码，也可以由2个第一个0进行编码。
7. 【NOIP2011】现有一段文言文，要通过二进制哈夫曼编码进行压缩。简单起见，假设这段文言文只由4个汉字"之""乎""者""也"组成，它们出现的次数分别为700、600、300、200。那么，"也"字的编码长度是()。
   A.1
   B.2
   C.3
   D.4
   【答案】C
   【分析】哈夫曼编码采取贪心思想，它实际上是构建了一棵二叉树，每次取出权重最小的两个点合并成新的点，新点权重为原来权重的和。最后这个点编码长度就是所在深度 - 1。这题最后的二叉树形态如下图所示，此时200对应的点深度为4，其编码长度为3。

        1800
      /    \
    700    1100
          /   \
        300    800
              /  \
            200  600

8. 【NOIP2016】一棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点(根结点的下标为1，若某结点的下标为i，则其左孩子位于下标2i处、右孩子位于下标(2i+1)处)，则图中所有结点的最大下标为()。
   A.6
   B.10
   C.12
   D.15
   【答案】D
   【分析】下标最大的结点为最下最右的结点。$2^{4}-1=15$ ，顺序存储会浪费空间，适合存储完全二叉树结构。各层结点的编号为(自左到右)，第一层：1；第二层：2,3；第三层：6,7；第四层：15。
9. 【NOIP2016】一棵二叉树如右图所示，若采用二叉树链表存储该二叉树(各个结点包括结点的数据、左孩子指针、右孩子指针)。如果没有左孩子或者右孩子，则对应的为空指针。那么该链表中空指针的数目为()。
   A.6
   B.7
   C.12
   D.14
   【答案】B
   【分析】每个叶子结点有2个空指针，只有一个孩子的结点有1个空指针，统计计算即可。
10. 【NOIP2010】完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置上，则第k号结点的父结点如果存在的话，应当存放在数组中的()号位置。
    A.2k
    B.2k+1
    C.k/2下取整
    D.$(k+1)/2$
    【答案】C
    【分析】其实就是父结点的编号是多少，稍微寻找一下规律便知道，当k是偶数，父结点是$\frac{k}{2}$ ，当k是奇数，父结点是$\frac{k - 1}{2}$ ，结合一下就是$\left\lfloor\frac{k}{2}\right\rfloor$ 。
11. 【NOIP2008】完全二叉树共有2N-1个结点，则它的叶结点数是()。
    A.N-1
    B.N
    C.2N
    D.$2^{N}-1$
    【答案】B
    【分析1】二叉树中度为2的结点数比度为0的结点数少1，两者数量之和为奇数；完全二叉树中度为1的结点数或0或1；此完全二叉树的结点总数为2*N-1，该数为奇数，说明度为1的结点数为0；因此度为2的结点数是N-1，度为0(叶结点)的结点数为N。
    【分析2】代入法，$N = 1$ 时，叶子结点个数为1；$N = 2$ 时，叶子结点个数为2。
12. 【NOIP2009】一个包含n个分支结点(非叶结点)的非空满k叉树，$k>=1$ ，它的叶结点数目为()。
    A.nk+1
    B.nk-1
    C.$(k+1)n-1$
    D.$(k-1)n+1$
    【答案】D
    【分析1】m层满k叉树拥有$\frac{1 - k^{m}}{1 - k}$个结点，非叶结点有$\frac{1 - k^{m - 1}}{1 - k}$个，叶结点有$k^{m - 1}$个。$\frac{1 - k^{m}}{1 - k}-\frac{1 - k^{m - 1}}{1 - k}=k^{m - 1}$ 。
    【分析2】结点数=边数+1，假设叶结点数为x，可以得到$x+n=k \times n+1$ ，$x=(k - 1) \times n+1$ 。
13. 【NOIP2015】如果根的高度为1，具有61个结点的完全二叉树的高度为()。
    A.5
    B.6
    C.7
    D.8
    【答案】B
    【分析】如果根的高度为1，那么高度为i的满二叉树的结点数是$2^{i}-1$ ，因为题中是完全二叉树，且$2^{5}-1<61<2^{6}-1$ ，所以层数为6。
14. 【NOIP2014】一棵具有5层的满二叉树中结点数为()。
    A.31
    B.32
    C.33
    D.16
    【答案】A
    【分析】n层的满二叉树中结点数为$2^{n}-1$ 。
15. 【NOIP2018】根结点深度为0，一棵深度为h的满$k(k>1)$叉树，即除最后一层无任何子结点外，每一层上的所有结点都有k个子结点的树，共有()个结点。
    A.$(k^{h + 1}-1)/(k - 1)$
    B.$k^{h - 1}$
    C.$k^{h}$
    D.$(k^{h - 1})/(k - 1)$
    【答案】A
    【分析1】考查数据结构基本知识，对于k叉树，每一层的结点个数依次为$1,k,k^{2},k^{3},\cdots,k^{h}$ 。由等比数列和公式可知，答案为$\frac{k^{h + 1}-1}{k - 1}$ 。
    【分析2】代入法，本题可以通过画二叉树$k = 2$ ，三叉树$k = 3$来排除选项。
16. 【NOIP2013】二叉树的()第一个访问的结点是根结点。
    A.先序遍历
    B.中序遍历
    C.后序遍历
    D.以上都是
    【答案】A
    【分析】二叉树先序遍历第一个访问的结点是根结点。
17. 【NOIP2013】二叉查找树具有如下性质：每个结点的值都大于其左子树上所有结点的值、小于其右子树上所有结点的值。那么，二叉查找树的()是一个有序序列。
    A.先序遍历
    B.中序遍历
    C.后序遍历
    D.宽度优先遍历
    【答案】B
    【分析】二叉树每个结点的值，大于其所有左子结点、小于其所有右子结点的值，因此按照中序遍历(左子结点、根、右子结点)，得到的一定是一个有序遍历。
18. 前序遍历序列与中序遍历序列相同的二叉树为()。
    A.根结点无左子树的二叉树
    B.根结点无右子树的二叉树
    C.只有根结点的二叉树或非叶子结点只有左子树的二叉树
    D.只有根结点的二叉树或非叶子结点只有右子树的二叉树
    【答案】D
    【分析】前序遍历的顺序依次为"根结点 - 左子树 - 右子树"，中序遍历的顺序依次为"左子树 - 根结点 - 右子树"。所以当二叉树只有根结点或非叶子结点只有右子树时，前序遍历和中序遍历的顺序都退化成了：根、右子树，故二者得到的序列相同。要使中序遍历序列与前序遍历序列相同，每个非叶子结点都不能有左子树。
19. 【NOIP2015】前序遍历序列与后序遍历序列相同的二叉树为()。
    A.非叶子结点只有左子树的二叉树
    B.只有根结点的二叉树
    C.根结点无右子树的二叉树
    D.非叶子结点只有右子树的二叉树
    【答案】B
    【分析】前序遍历的顺序依次为"根结点 - 左子树 - 右子树"，后序遍历的顺序依次为"左子树 - 右子树 - 根结点"。由于前序遍历序列中的根结点一定在第一个，要使后序遍历序列与之相同，左、右子树必须为空。
20. 【NOIP2011】右图是一棵二叉树，它的先序遍历是()。
    A.ABDEFC
    B.DBEFAC
    C.DFEBCA
    D.ABCDEF
    【答案】A
    【分析】先序遍历的顺序是根左右。
21. 【NOIP2012】如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是()。
    A.ABC
    B.CBA
    C.ACB
    D.BAC
    【答案】C
    【分析】所有的情况如下图所示:

      B
     / \
    A   C

先序遍历:CAB

    C
   / \
  B   A

先序遍历:CBA

  A
 / \
B   C

先序遍历:ABC

  B
 / \
A   C

先序遍历:BCA

  B
 / \
A   C

先序遍历:BAC
22. 【NOIP2009】【NOIP2016】表达式$a *(b + c)-d$的后缀表达式是()。
A.abcd*+
B.abc+d-
C.abc+d-
D.-+*abcd
【答案】B
【分析】后缀表达式的主要特点是左右根，根结点表示符号，左右两边是式子或数字。该树如下:

          -
         / \
        *   d
       / \
      a   +
          / \
         b   c

23. 【NOIP2018】表达式$a * d - b * c$的前缀形式是()。
    A.adbc
    B.-adbc
    C.ad - bc
    D.-**adbc
    【答案】B
    【分析】本题考查前缀表达式的理解。

          -
         / \
        *   *
       / \ / \
      a   d b   c

前缀表达式为 -adbc。
24. 【NOIP2010】前缀表达式+3*2+512的值是()。
A.23
B.25
C.37
D.65
【答案】C
【分析】运算符号只能作为父结点，而数字是叶结点。

          +
         / \
        3   *
            / \
           2   +
               / \
              5   12

中缀表达式是$3+2 *(5 + 12)=37$ 。
25. 【NOIP2008】二叉树T，已知其先根遍历是1243576(数字为结点的编号，以下同)，中根遍历是2415736，则该二叉树的后根遍历是()。
A.4257631
B.4275631
C.7425631
D.4276531
【答案】B
【分析】二叉树的遍历，先构造二叉树，根据先根遍历序列可知根为1，因此在中根遍历序列中1的左边都是左子树，1的右边都是右子树，以此类推。
26.【NOIP2010】-棵二叉树的前序遍历序列是ABCDEFG,后序遍历序列是CBFEG DA,则根结点的左子树的结点个数可能是()。 【答案】A 【分析】根据前序与后序遍历,可知根结点为A;

不定项选择题

1. 【NOIP2008】设T是一棵有n个顶点的树，下列说法正确的是()。 A.T是连通的、无环的 B.T是连通的，有n - 1条边 C.T是无环的，有n - 1条边 D.以上都不对 【答案】ABC 【分析】n个顶点的树有且仅有n - 1条边，而且连通无环，这些都是树的性质。
2. 【NOIP2018】下列说法中，是树的性质的有()。 A.无环 B.任意两个结点之间有且只有一条简单路径 C.有且只有一个简单环 D.边的数目恰是顶点数目减1 【答案】ABD 【分析】树是一个n个结点n - 1条边的连通图，故不可能存在环，其余选项均为树的一些常见基本性质。
3. 【NOIP2015】下列有关树的叙述中，叙述正确的有()。 A.在含有n个结点的树中，边数只能是(n - 1)条 B.在哈夫曼树中，叶结点的个数比非叶结点个数多1 C.完全二叉树一定是满二叉树 D.在二叉树的前序序列中，若结点u在结点v之前，则u一定是v的祖先 【答案】AB 【分析】排除法，C选项，完全二叉树不一定是满二叉树，满二叉树一定是完全二叉树；D选项，在二叉树的前序序列中，若结点u在结点v之前，则u不一定是v的祖先，也有可能u和v分属两棵不同的子树，而v的祖先一定在v之前。
4. 【NOIP2008】二叉树T，已知其先根遍历是1243576(数字为结点的编号，以下同)，后根遍历是4275631，则该二叉树的可能的中根遍历是()。 A.4217536 B.2417536 C.4217563 D.2415736 【答案】ABD 【分析】可以由先根遍历序列和A、B、C、D中的任一中根遍历序列组成一棵确定的树，如果能确定，则写出其后根遍历的序列，和题中叙述的后根序列比对即可。
5. 【NOIP2011】如果根结点的深度记为1，则一棵恰有2011个叶子结点的二叉树的深度可能是()。 A.10 B.11 C.12 D.2011 【答案】CD 【分析】结点数为n的二叉树，最小深度为完全二叉树深度为$|log _{2} n|+1$（下取正整后 +1），最大深度为n，退化为单链长度。所以可能的树深度范围：$|log _{2} n|+1$~$n$，题目中n为2011。高度范围是12~2011。故选择CD。
6. 【NOIP2012】一棵二叉树一共有19个结点，其叶子结点可能有()个。 A.1 B.9 C.10 D.11 【答案】ABC 【分析】一棵任意形态的19个点的二叉树的叶子数范围是$1$~$\left\lfloor\frac{n + 1}{2}\right\rfloor$。1指的是一条链的情况，$\left\lfloor\frac{n + 1}{2}\right\rfloor$指的是完全二叉树的情况。
7. 【NOIP2018】2 - 3树是一种特殊的树，它满足两个条件： (1)每个内部结点有两个或三个子结点； (2)所有的叶结点到根的路径长度相同。 如果一棵2 - 3树有10个叶结点，那么它可能有()个非叶结点。 A.5 B.6 C.7 D.8 【答案】CD 【分析】最底层有10个结点；倒数第二层只有两种可能性：第一种情况，5个结点，每个结点的度都为2。第二种情况，4个结点，两个结点的度为3，两个结点的度为2；根据倒数第二层的结点数，倒数第三层和第四层的结点数是唯一确定的，上往下每层结点分别为(1,2,5,10)和(1,2,4,10)。