1、对以下算法功能最准确的描述是（）。

A.判断二叉树根结点值是否为e

B.判断二叉树是否存在值为e结点

C.求二叉树中值为e结点的层次

D.求二叉树值为e的结点的个数

C

2、二叉树的形态

由 3 个结点可以构造出 ▁▁▁▁▁ 种不同形态的二叉树。

A.2

B.3

C.4

D.5

D

由n个结点可以构造出C(2n, n) / (n + 1)种不同形态的二叉树。

卡特兰数的通项为C(2n, n) / (n + 1)。

3、完全二叉树的叶子结点数

一棵有 1001 个结点的完全二叉树，其叶子结点数为 ▁▁▁▁▁ 。

A.250

B.254

C.500

D.501

D

完全二叉树有如下性质：n=n0+n1+n2，n0=n2+1（叶子结点数等于度为2的结点数加1）

n:结点总数

n0:度为0的结点个数，也就是叶子结点

n1:度为1的结点个数，在完全二叉树中值有0和1这两种情况（n1=0或1）

n2:度为2的结点个数

度为1的结点数为：

n为偶数：1

n为奇数：0

1001=n0+0+n0-1

n0=501

4、二叉树的高度

若根节点为高度1，一棵具有 1025 个结点的二叉树的高度为 ▁▁▁▁▁ 。

A.10

B.11

C.11～1025 之间

D.10～1024 之间

C、

若二叉树每层只有一个结点（单链表），则高度为1025

若二叉树为完全二叉树（高度为n，最多有2ⁿ-1个结点（n≥1），第i层，最多有2ⁿ-1个结点）

2ⁿ-1=1025 ( 2^10 - 1 < 1025 < 2^11 - 1 )，n=11

则该二叉树的高度为11~1025之间。

5、已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ ）。

A.acbed

B.decab

C.deabc

D.cedba

D

前序遍历：根左右

中序遍历：左根右debac

后序遍历：左右根dabec

①根据后序序列确定二叉树的根结点

②根据根结点在中序序列中划分出二叉树的左、右子树包含哪些结点。

然后根据左右子树结点在后序序列中的次序确定子树的根结点，即回到步骤①

③如此重复上述步骤，直到每棵子树仅有一个结点为止

第一层：根结点为c，左子树包含deba，没有右结点。

第二层：根结点为e，左结点为d，右子树包含ba

第三层：根结点为b，没有左结点，右结点为a

1 c

2 e

3 d b

4 a

6、对于任意一棵高度为 5 且有 10 个结点的二叉树，若采用顺序存储结构保存，每个结点占 1 个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存储单元的数量至少是：

A.31

B.16

C.15

D.10

A

2^5 - 1 = 31

7、已知森林 F 及与之对应的二叉树 T，若 F 的先根遍历序列是 a, b, c, d, e, f，后根遍历序列是 b, a, d, f, e, c，则 T 的后序遍历序列是：

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

C

前序遍历：根左右 a, b c, d, e, f

中序遍历：左根右

后序遍历：左右根 b, a d, f, e, c

易知F中存在两棵二叉树，分别包括ab结点和cdef结点

F

1 a c

2 b d e

3 f

T

1 a

2 b c

3 d

4 e

5 f

8、一棵二叉树中有7个度为2的结点和5个度为1的结点，其总共有（ ）个结点。

A.16

B.18

C.20

D.30

C

n=n0+n1+n2

n0=n2+1

n=8+5+7=20

9、用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为( )

A.n-1

B.n

C.n+l

D.2n

C

n个结点的二叉链表中，有2n个链域，每一条非空链域对应一条树枝，而树枝的个数为n-1，

因此，空节点个数为2n-(n-1)=n+1。

10、某森林 F 对应的二叉树为 T，若 T 的先序遍历序列是 a, b, d, c, e, g, f，中序遍历序列是 b, d, a, e, g, c, f，则 F 中的树的棵树是：

A.1

B.2

C.3

D.4

C

前序遍历：根左右 a, b, d, c, e, g, f

中序遍历：左根右 b, d, a, e, g, c, f

后序遍历：左右根

第一层：根结点为a，左子树包含bd结点，右子树包含egcf结点

第二层：a的左子树的根结点为b，无左结点，右结点为d

a的右子树的根结点为c，左子树包含eg结点，右结点为f

第三层：根结点为e，无左结点，右结点为g

T

1 a

2 b c

3 d e f

4 g

F

1 a c f

2 b e

3 d g

转换为森林，包含3棵树，根结点分别为a，c，f。

11、若某二叉树有 5 个叶结点，其权值分别为 10、12、16、21、30，则其最小的带权路径长度（WPL）是：

A.89

B.200

C.208

D.289

B

合并最小的两个叶结点10、12→22：{ 16、21、22、30 }

合并最小的两个叶结点16、21→37：{ 22、30、37 }

合并最小的两个叶结点22、30→52：{ 37、52 }

合并最小的两个叶结点37、52→89：{ 89 }

1 89

2 37 52

3 16 21 22 30

4 10 12

16×2+21×2+10×3+12×3+30×2=200

32+42+30+36+60=200

12、给二叉树的结点编号

对一棵二叉树的结点从 1 开始顺序编号。要求每个结点的编号小于其左、右孩子的编号，且左孩子的编号小于右孩子的编号。可采用 ▁▁▁▁▁ 实现编号。

A.先序遍历

B.后序遍历

C.中序遍历

D.层次遍历

A

根