208 树

【NOIP2013】已知一棵二叉树有 10 个节点，则其中至多有（）个节点有 2 个子节点。

A.4

B.5

C.6

D.7

【NOIP2013】已知一棵二叉树有 2013 个节点，则其中至多有（）个节点有 2 个子节点。

A.1006

B.1007

C.1023

D.1024

【NOIP2011】如果根结点的深度记为 1，则一棵恰有 2011 个叶结点的二叉树的深度最少是（）。

A.10

B.11

C.12

D.13

【NOIP2010】如果树根算是第一层，那么一颗 n 层的二叉树最多有（）个结点。

A.2^n-1

B.2^n

C.2^n+1

D.2^(n+1)

【NOIP2009】一个包含 n 个分支结点（非叶结点）的非空二叉树，它的叶结点数目最多为（）。

A.2n + 1

B.2n-1

C.n-1

D. n+1

【NOIP2009】最优前缀编码，也称 Huffman编码。这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码，以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码（）。

A.（00，01， 10， 11）

B.（0， 1，00， 11）

C.（0， 10， 110， 111）

D.（1，01，000，001）

【NOIP2011】现有一段文言文，要通过二进制哈夫曼编码进行压缩。简单起见，假设这段文言文只由 4 个汉字 “之 ”、“乎 ”、“者 ”、“也 ”组成，它们出现的次数分别为 700、 600、 300、 200。那么，“也 ”字的编码长度是（）。

A.1

B.2

C.3

D.4

【NOIP2016】一棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为 1，若某结点的下标为 i ，则其左孩子位于下标 2i 处、右孩子位于下标 (2i+1)处），则图中所有结点的最大下标为（）。

A. 6

B. 10

C. 12

D. 15

【NOIP2016】一棵二叉树如右图所示，若采用二叉树链表存储该二叉树（各个结点包括结点的数据、左孩子指针、右孩子指针）。如果没有左孩子或者右孩子，则对应的为空指针。那么该链表中空指针的数目为（）。

A. 6

B. 7

C. 12

D. 14

10.

【NOIP2010】完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。假定根结点存放在数组的 1 号位置上，则第 k 号结点的父结点如果存在的话，应当存放在数组中的（）号位置。

A.2k

B. 2k+1

C. k/2 下取整

D. (k+1)/2

11.

【NOIP2008】完全二叉树共有 2*N-1 个结点，则它的叶节点数是（）。

A. N-1

B. N

C. 2*N

D. 2^N-1

12.

【NOIP2009】一个包含 n 个分支结点（非叶结点）的非空满 k 叉树，k>=1，它的叶结点数目为（）。

A.nk + 1

B.nk-1

C.(k+1)n-1

D.(k-1)n+1

13.

【NOIP2015】如果根的高度为 1，具有 61 个结点的完全二叉树的高度为（）。

A.5

B.6

C.7

D.8

14.

【NOIP2014】一棵具有 5 层的满二叉树中结点数为（）。

A.31

B.32

C.33

D.16

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)

16.

【NOIP2013】二叉树的（）第一个访问的节点是根节点。

A.先序遍历

B.中序遍历

C.后序遍历

D.以上都是

17.

【NOIP2013】二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。那么，二叉查找树的（）是一个有序序列。

A.先序遍历

B.中序遍历

C.后序遍历

D.宽度优先遍历

18.

前序遍历序列与中序遍历序列相同的二叉树为（）。

A.根结点无左子树的二叉树

B.根结点无右子树的二叉树

C.只有根结点的二叉树或非叶子结点只有左子树的二叉树

D.只有根结点的二叉树或非叶子结点只有右子树的二叉树

19.

【NOIP2015】前序遍历序列与后序遍历序列相同的二叉树为（）。

A.非叶子结点只有左子树的二叉树

B.只有根结点的二叉树

C.根结点无右子树的二叉树

D.非叶子结点只有右子树的二叉树

20.

【NOIP2011】下图是一棵二叉树，它的先序遍历是（）。

A. ABDEFC

B. DBEFAC

C. DFEBCA

D. ABCDEF

21.

【NOIP2012】如果一棵二叉树的中序遍历是 BAC，那么它的先序遍历不可能是（）。

A.ABC

B.CBA

C. ACB

D.BAC

22.

【NOIP2009】【NOIP2016】表达式 a*(b+c)-d 的后缀表达式是（）。

A.abcd*+-

B.abc+*d-

C.abc*+d-

D.-+*abcd

23.

【NOIP2018】表达式 a * d - b * c 的前缀形式是（）。

A.a d * b c * -

B.- * a d * b c

C.a * d - b * c

D.- * * a d b c

24.

【NOIP2010】前缀表达式“+ 3 * 2 + 5 12”的值是（）。

A.23

B.25

C.37

D.65

25.

【NOIP2008】二叉树 T，已知其先根遍历是 1 2 4 3 5 7 6（数字为结点的编号，以下同），中根遍历是 2 4 1 5 7 3 6，则该二叉树的后根遍历是（）。

A. 4 2 5 7 6 3 1

B. 4 2 7 5 6 3 1

C. 7 4 2 5 6 3 1

D. 4 2 7 6 5 3 1

26.

【NOIP2010】一棵二叉树的前序遍历序列是 ABCDEFG,后序遍历序列是 CBFEGDA,则根结点的左子树的结点个数可能是（）。

A.2

B.3

C.4

D.5

27.

【NOIP2008】设 T 是一棵有 n 个顶点的树，下列说法正确的是（）。【多选题】

A. T 是连通的、无环的

B. T 是连通的，有 n-1 条边

C. T 是无环的，有 n-1条边

D. 以上都不对

28.

【NOIP2018】下列说法中，是树的性质的有（）。【多选题】

A. 无环

B. 任意两个结点之间有且只有一条简单路径

C. 有且只有一个简单环

D. 边的数目恰是顶点数目减 1

29.

【NOIP2015】下列有关树的叙述中，叙述正确的有（）。【多选题】

A.在含有 n 个结点的树中，边数只能是(n-1)条

B.在哈夫曼树中，叶结点的个数比非叶结点个数多 1

C.完全二叉树一定是满二叉树

D.在二叉树的前序序列中，若结点 u 在结点 v 之前，则 u 一定是 v 的祖先

30.

【NOIP2008】二叉树 T，已知其先根遍历是 1 2 4 3 5 7 6（数字为结点的编号，以下同），后根遍历是 4 2 7 5 6 3 1，则该二叉树的可能的中根遍历是（）。【多选题】

A. 4 2 1 7 5 3 6

B. 2 4 1 7 5 3 6

C. 4 2 1 7 5 6 3

D. 2 4 1 5 7 3 6

31.

【NOIP2011】如果根结点的深度记为 1，则一棵恰有 2011 个叶子结点的二叉树的深度可能是（）。【多选题】

A. 10

B. 11

C. 12

D. 2011

32.

【NOIP2012】一棵二叉树一共有 19 个节点，其叶子节点可能有（）个。【多选题】

A.1

B.9

C.10

D.11

33.

【NOIP2018】 2-3 树是一种特殊的树，它满足两个条件：(1)每个内部结点有两个或三个子结点；(2)所有的叶结点到根的路径长度相同。如果一棵 2-3 树有 10 个叶结点，那么它可能有（）个非叶结点。【多选题】

A. 5

B. 6

C. 7

D. 8