一、选择题
1、设T是一棵树，T’是对应于x的二叉树，则T的先根次序遍历和T’的（）次序遍历相同。

A、先根
B、中根
C、后根
D、以上都不是
2、
3、若二叉树的后序遍历序列为dabec，中序遍历序列为debac，则前序序列遍历为（）。

A、acbed
B、decab
C、deabc
D、cedba
4、具有35个结点的完全二叉树的深度为（）
A、5
B、6
C、7
D、8
5、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子结点编号为（）
A、98
B、99
C、50
D、48
6、某二叉树的前序和后序序列正好相反，则该二叉树一定是（）的二叉树。

A、空或只有一个结点
B、高度等于其结点数
C、任一结点无左孩子
D、任一结点无左孩子
7、二叉树在线索化后，仍不能有效求解的问题是（）
A、先根线索二叉树中求先根后继
B、中根线索二叉树中求中根后继
C、中根线索二叉树中求中根前驱
D、后根线索二叉树中求后根后继
8、在线索化二叉树中，t所指结点没有左子树的充足条件是（）
A、t-lchild==NULL
B、t->ltag==1
C、t->ltag==1&&t->lchild==NULL
D、以上都不对
9、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）
A、2h
B、2h-1
C、2h+1
D、h+1
10、深度为5的二叉树至多有（）个结点。

A、16
B、32
C、31
D、10
11、在一非空二叉树的中序遍历序列中，根结点的右边（）
A、只有右子树上的所有结点
B、只有右子树上的部分结点
C、只有左子树上的所有结点
D、只有左子树上的部分结点
12、树最适合用来表示（）
A、有序数据元素
B、无序数据元素
C、元素之间具有分支层次关系的数据
D、元素之间无联系的数据
13、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）
A、不发生改变
B、发生改变
C、不能确定
D、以上都不对
14、设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是（）
A、n在m右方
B、n是m祖先
C、n在m左方
D、n是m子孙
15、线索二叉树是一种（）结构
A、逻辑
B、逻辑和存储
C、物理
D、线性
16、森林的后根遍历序列与其对应二叉树的（）遍历序列一致。

A、先根
B、后根
C、中根
D、不可能
二、填空题
1、由一棵二叉树后序序列和（中序）可唯一确定这棵二叉树。

2、含有n个结点的二叉树用二叉链表表示时，有（N+1）个空链域。

3、有m个叶子结点的哈夫曼树有（2*M-1）个结点。

4、前序为a,b,c且后序c,b,a的二叉树共有（4）棵。

5、已知完全二叉树的第4层有6个结点，则其叶子结点数是（7）。

6、已知二叉树有31个叶子结点，且仅有一个孩子的结点数为40，则总结点数为（101）。

7、树和二叉树的两个主要差别是（二叉树是有序树）和（二叉树的度最大为2）。

8、从概念上讲，树与二叉树是两种不同的数据结构，将树转化成二叉树的基本目的是（通过与树对应的二叉树的操作来实现树的操作）。

9、深度为k的完全二叉树至少有（2k-1）个结点，至多有（2k-1）个结点，若按自上而下，从左至右的次序给结点编号从1开始，则编号最小的叶子结点的编号是（2k-1）。

10、结点最少的树为（空树），结点最少的二叉树是（空二叉树）。

12、以数据集（4，5，6，7，10，12，18）为结点权值的Huffman树的带权路径长度为（168）。

（可画出图形）。