设树T的度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1。则T中有多少个叶子结点？
A.4
B.6
C.8
D.10

一棵含有n个结点的树，有n-1个分支，即 n = 14 + 22 + 31 + 41 + 1 = 16;
又由于 n = n0 + n1 + n2 + n3 + n4 = n0 + 8;
n0 + 8 = 16，所有叶子结点个数为8

规律1： （节点个数）m=（边数）n+1
规律2： 度为节点的子女个数，可以看作几个出边就是几个度，叶子节点没有度

三叉树中，度为1的结点有5个，度为2的结点3个，度为3的结点2个，问该树含有几个叶结点？
A. 8
B. 10
C. 12
D. 13

总结点数：1 * 5 + 2 * 3 + 3 * 2 + X * 0 + 1 = 18
叶子结点数：X = 18 - 5 - 3 - 2 = 8

设每个d叉树的结点有d个指针指向子树，有n个结点的d叉树有多少空链域？
A.nd
B.n(d−1)
C.n(d−1)+1
D.以上都不是

每个d叉树的结点有d个链域（就是d条边，每个结点不满d条边的，少几条边就几个空链域）
应该具有边的条数：nd
现有边的条数：n-1
空链域个数：nd-（n-1）= n(d−1)+1

有一个四叉树，度2的结点数为2，度3的结点数为3，度4的结点数为4。问该树的叶结点个数是多少？
A. 10
B. 12
C. 20
D. 21

总结点数=10+22+33+44+0*x+1=30
叶结点数=30-2-3-4=21

以二叉链表作为二叉树的存储结构，在具有 n 个结点的二叉链表中（n>0），空链域的个数为 __
A.n+1
B.n
C.n−1
D.无法确定

n个结点的二叉树
每个结点有两个指针域，所以总共有2n个指针
除了根节点没有被指针指向，其他结点的有一个有效的指针指向
所以有n-1个有效指针
则空链域=2n-(n-1)=n+1

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

二叉树是一种特殊的树 F

二叉树不是一种特殊的树，二叉树可以为空，树不能为空
树与二叉树的两个主要区别：
1.树中结点的最大度数没有限制，二叉树结点的最大度数为2
2.树的结点无左右之分，二叉树的结点有左右之分

若A和B都是一棵二叉树的叶子结点，则存在这样的二叉树，其前序遍历序列为…A…B…，而中序遍历序列为…B…A…。F

先序中序后序是对根结点而言，叶子结点的顺序保持不变

将一棵完全二叉树存于数组中（根结点的下标为1）。则下标为23和24的两个结点是兄弟。F

根结点为n的左孩子为2n，右孩子为2n+1.
故23和24不可能是兄弟。

一棵有9层结点的完全二叉树（层次从1开始计数），至少有255个结点。F

9层全部满的情况下共有2^8-1=256-1=255个结点。此时是一棵9层的满二叉树，而题目中说的是完全二叉树，所以应该为至多255个结点。

对两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序却是一致的。T

二叉排序树/二叉搜索树：
1.非空左子树的所有键值小于其根结点的键值
2.非空右子树的所有键值大于其根结点的键值
3.左、右子树都是二叉搜索树
4.没有键值相等的结点

中序遍历它以后，也就是排成从小到大的顺序，所以得到的序列的顺序是一致的

二叉搜索树中，新结点总是作为树叶来插入的

二叉搜索树的查找效率和二叉排序树的高度有关

满二叉树：每层都是满的；
完全二叉树：除最后一层外，每层都是满的，并且或者最后一层是满的，或者是在右边缺少连续若干结点;

深度为6的二叉树最多有( )个结点。
64
63
32
31

2^6-1=63

一个具有1025个结点的二叉树的高h为（ ）个。
11
10
11至1025之间
10至1024之间

若将一棵树 T 转化为对应的二叉树 BT，则下列对 BT 的遍历中，其遍历序列与 T 的后根遍历序列相同的是：
先序遍历
中序遍历
后序遍历
按层遍历

一棵树的后根遍历与这棵树所对应的二叉树的中序遍历相同。因为树转化为二叉树后是没有右子树的，所以最后访问的是树的根结点。

二叉树的顺序存储结构：

• 这种结构是用一组连续的存储单元（比如数组）存储二叉树结点的数据，结点的父子关系是通过他们的相对位置来反映的，而不需要任何附加的存储单元来存放指针
• 通常情况下，顺序存储用于完全二叉树的存储
• 具体实现是从树的根结点开始，从上到下，从左到右，依次给结点编号并将数据存放到一个数组的对应单元中

在N个结点的完全二叉树中，对于下标为i的结点：

• 当i/2>=1时，i/2单元时其父节点；当i/2=0时，表明该结点是树的根节点，无父节点
• 当2i<=N时，2i单元是其左孩子；否则无左孩子
• 当2i+1<=N时，2i+1单元是其右孩子，否则无右孩子

二叉树的链表存储：
每个结点由数据和左右指针三个数据成员组成：

typedef struct TNode *Position;
typedef Position BinTree;//二叉树类型BT
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

二叉树的遍历：先序遍历，中序遍历，后序遍历，层序遍历

利用二叉链表存储树，则根结点的右指针是（ ）。
指向最左孩子
指向最右孩子
空
非空

二叉链表根节点的左指针指向树的根节点，右指针指向树的根节点的兄弟
树的根节点没有兄弟，因此为空

树的三种常用存储结构：

• 双亲表示法
• 孩子表示法
• 孩子兄弟表示法

在下列存储形式中，（ ）不是树的存储形式。
双亲表示法
孩子链表表示法
孩子兄弟表示法
顺序存储表示法

对于一个有N个结点、K条边的森林，共有几棵树？
A.N−K
B.N−K+1
C.N−K−1
D.不能确定

由一颗树的性质：结点=边+1【n= k+ 1】
等价于 n - k =1
故共有 n - k 棵树

设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M1，M​2和M​3​​ 。则与森林F对应的二叉树根结点的右子树上的结点个数是：
A.M1
​​B.M​1​​ +M​2
​​C.M​2​​ +M​3
​​D.M3
​​