题1

1、设高度为h的二叉树上只有度为0和度为2的结点，则该二叉树中所包含的结点数至少为（），最多为（）。
A、h ；2^h-1
B、2h-1 ； 2^h-1
C、2h+1； 2^h-1-1
D、h+1；2^h-1

解析：（B）
最少的情况下，除了根结点该层为1个结点以外，其余h-1层都有2个结点，得2(h-1)，即2(h-1)+1=2h-1。
最多的情况下，除了最后一层度为0，其余结点都是度为2的结点，即 2^h-1个。

题2

2、一棵有124个叶结点的完全二叉树，最多有（ ）个结点。
A、247
B、248
C、249
D、250

解析：（B）
由于n₀=n₂+1，且N=n₀+n₁+n₂，度为0和度为1的结点相差为1，所以完全二叉树中度为1的结点n₁只可能是0或1，即当总结点数为偶数时n₁=1，为奇数时n₀=0。
本题中，n₀=124，可得n₂=123，由于是考虑最多结点数，即n₁=1，所以N=124+123+1=248。

题3

3、若一棵二叉树有126个结点，在第7层（根结点在第1层）至多有（）个结点。
A、32
B、64
C、63
D、不存在第7层

解析：（C）
考虑第1层到第6层结点都是满的情况，即第1层到第6层结点的结点数量为1+2+4+8+16+32=63个。第7层最多可有64个结点，由于二叉树有126个结点，即第7层还有126-63=63个结点。

题4

4 、一棵有n个结点的二叉树采用二次链表存储结点，其中非空指针数为（），空指针数为（）。
A、n+1；n-1
B、n；n-1
C、n-1；n+1
D、2n；2n-1

解析：（A）
n个结点的数有n-1条分支，每个分支对应一个指针，所以非空指针数为n-1；另外，由于每个结点中包含2个指针域（左指针域lchild、右指针域rchild），总指针域数量减去非空指针数即为空指针数，2n-(n-1)=n+1。

题5

5、在二叉树的前序序列、中序序列和后序序列中，所有叶子结点的先后顺序是（）。
A、都不相同
B、完全相同
C、前序序列和中序序列相同，与后序序列不同
D、中序序列和后序序列相同，与前序序列不同

解析：（B）
三种遍历方式中，访问左右子树的顺序是相同的，只是访问根结点的先后顺序不同，故所有叶子结点的先后顺序是相同的。

题6

6、线索二叉树是一种（）结构。
A、逻辑
B、逻辑和存储
C、物理
D、线性

解析：（C）
二叉树是一种逻辑结构，而线索二叉树是加上线索的链表结构，是一种物理结构。

题7

7、在有n个叶子结点的哈夫曼树中，非叶子结点的总数是（）；若该哈夫曼树有215个结点，对其进行哈夫曼编码，可以得到（）个不同的码字。
A、n-1；108
B、n；107
C、2n-1；214
D、2n；215

解析：（A）
哈夫曼树中只有度为0和2的结点，由n₀=n₂+1，可得：非叶子结点的总数为n-1。
结点总数N=n₀+n₂，且n₀=n₂+1，N=215代入可得，n₀=108。

题8

8、（判断）哈夫曼编码树中，两个频率相同的字符具有相同的哈夫曼编码。

解析：（×）
不会有相同的哈夫曼编码，除非它们的字符相同，从而得到的哈夫曼编码也相同。

题9

9、找出下列条件的二叉树：
A、先序遍历序列与后序遍历序列相同，为（）
B、中序遍历序列与后序遍历序列相同，为（）
C、先序遍历序列与中序遍历序列相同，为（）
D、中序遍历序列与层次遍历序列相同，为（）

解析：
A、空树或只有根结点的二叉树；
B、空树或任一结点至多只有左子树；
C、空树或任一结点至多只有右子树；
D、空树或任一结点至多只有右子树。