D．pre（x）>pre（y）且post（x）>post（y）
16．每棵树都能惟一地转换成对应的二叉树，由树转换的二叉树中，一个结点N的左孩子是它在原树对应结点的（23），而结点N的右孩子是它在原树里对应结点的（24）。
（23）—（24）：
A．最左孩子B．最右孩子C．右邻兄弟D．左邻兄弟
17．二叉树在线索化后，仍不能有效求解的问题是（25）。
（25）：
A．前序线索树中求前序直接后继结点
B．中序线索树中求中序直接前驱结点
C．中序线索树中求中序直接后继结点
D．后序线索树中求后序直接后继结点
18．一棵具有124个叶子结点的完全二叉树，最多有（26）个结点。
（26）：
A．247B．248C．249D．250。
19．实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最有效的存储结构是采用（27）。
（27）：
A.二叉链表B．孩子链表C．三叉链表D．顺序表
3．二叉树后序遍历的次序是什么？
（）
A根、左子树、右子树B左子树、根、右子树
C左子树、右子树、根D根、右子树、左子树
4．已给如图二叉树，它的中序遍历是哪一项？
（）
A．ABECDFB．ABCDEFC．CBDAEFD．CDBFEA
6．已知完全二叉树有26个结点，则整棵二叉树有多少个度为1的结点？
（）
A．1B．0C．2D．不确定
1．以下说法错误的是（）
A.树形结构的特点是一个结点可以有多个直接前趋
B.线性结构中的一个结点至多只有一个直接后继
C.树形结构可以表达（组织）更复杂的数据
D.树（及一切树形结构）是一种"分支层次"结构
⑤任何只含一个结点的集合是一棵树
2，以下说法错误的是（）
A.二叉树可以是空集
B.二叉树的任一结点都有两棵子树
C.二叉树与树具有相同的树形结构
D.二叉树中任一结点的两棵子树有次序之分
3、以下说法错误的是（）
A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达
B.在三叉链表上，二叉树的求双亲运算很容易实现
C.在二叉链表上，求根，求左、右孩子等很容易实现
D.在二叉链表上，求双亲运算的时间性能很好
4、以下说法错误的是（）
A.一般在哈夫曼树中，权值越大的叶子离根结点越近
B.哈夫曼树中没有度数为1的分支结点
C.若初始森林中共有n裸二叉树，最终求得的哈夫曼树共有2n-1个结点
D.若初始森林中共有n裸二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树
5．深度为6的二叉树最多有（）个结点（）
A.64B.63C.32D.31
6．将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双结点编号为（）
A.42B.40C.21D.20
7．任何一棵二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置（）
A.肯定发生变化B.有时发生变化
C.肯定不发生变化D.无法确定
8．设二叉树有n个结点，则其深度为（）
A.n-1B.nC.5floor（log2n）D.无法确定
9．设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数最少（）个
A.k+1B.2kC.2k-1D.2k+1
10.下列说法正确的是（）
A.树的先根遍历序列与其对应的二叉树的先根遍历序列相同
B.树的先根遍历序列与其对应的二叉树的后根遍历序列相同
C.树的后根遍历序列与其对应的二叉树的先根遍历序列相同
D.树的后根遍历序列与其对应的二叉树的后根遍历序列相同
11．下列说法中正确的是（）
A.任何一棵二叉树中至少有一个结点的度为2
B.任何一棵二叉树中每个结点的度都为2
C.任何一棵二叉树中的度肯定等于2
D.任何一棵二叉树中的度可以小于2
12．一棵二叉树满足下列条件：
对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。
现采用（）遍历方式就可以得到这棵二叉树所有结点的递增序列。
A.先根B.中根C.后根D.层次
13．设森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的右子树上有（）个结点。
A.n1-1B.n1C.n1+n2+n3D.n2+n3+n4
14．森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的左孩子上有（）个结点。
A.n1-1B.n1C.n1+n2+n3D.n2+n3+n4
15.对含有（）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。
A.0B.1C.2D.不存在这样的二叉树
16．讨论树、森林和二叉树的关系，目的是为了（）
A.借助二叉树上的运算方法去实现对树的一些运算
B.将树、森林按二叉树的存储方式进行存储
C.将树、森林转换成二叉树
D.体现一种技巧，没有什么实际意义
17．如图选择题17所示二叉树的中序遍历序列是（）
A.abcdgefB.dfebagcC.dbaefcgD.defbagc
18.已知某二叉树的后续遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是（）
A.acbedB.deabcC.decabD.cedba
19.如果T2是由有序树T转化而来的二叉树，那么T中结点的前序就是T2中结点的（）
A.前序B.中序C.后序D.层次序
20．如果T2是由有序树T转化而来的二叉树，那么T中结点的后序就是T2中结点的（）
A.前序B.中序C.后序D.层次序
21．某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是（）
A.bdgcefhaB.gdbecfhaC.D.bdgechfaD.gdbehfca
22.在图选择题22中的二叉树中，（）不是完全二叉树。
23、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法（）
A.正确B.错误
24、由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法（）
A.五确B.错误
25，二叉树是每个结点的度不超过2的有序树的特殊情况，这种说法（）
A.正确B.错误
26·树最适合用来表示（）
A.有序数据元素B.无序数据元素
C.元素之间具有分支层次关系的数据D.元素之间无联系的数据
27，深度为5的二叉树至多有（）个结点。
A.16B.32C.31D.10
28、在计算递归函数时，如不使用递归过程，则一般情况下必须借助于（）数据结构
A.栈B.树C.双向队列D.顺序表
29.堆（Heap）是（）
A.完全二叉树B.线性表C.满二叉树
30、下列说法中正确的是（）
A.二叉树中任何一个结点的度都为2B.二叉树的度为2
C.任何一棵二叉树中至少有一个结点的度为2D.一棵二叉树的度可以小于2
31、设二叉树根结点的层次为0，一棵高度为h的满二叉树中的结点个数是（）
A.2hB.2h-1C.2h-1D.2h+1-1
32、设二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序（）
A.都不相同B.完全相同
C.先序和中序相同，而与后序不同D.中序和后序相同，而与先序不同
33·以下说法错误的是（）
A.存在这样的二叉树，对它采用任何次序的遍历，其结点访问序列均相同
B.二叉树是树的特殊情形
C.由树转换成二叉树，其根结点的右子树总是空的
D.在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树
34、以下说法正确的是（）
A.先根遍历树和前序遍历与该树对应的二叉树，其结果不同
B.后根遍历树和前序遍历与该树对应的二叉树，其结果不同
C.前序遍历森林和前序遍历与该森林对应的二叉树，其结果相同
D.后序遍历森林和中序遍历与该森林对应的二叉树，其结果不同
35·以下说法正确的是（）
A.一般来说，若深度为k的n个结点的二叉树具有最小路径长度，那么从根结点到第k-1层具有最多的结点数为2k-1-1余下的n-2k-1+1个结点在第k层的任一位置上
B.若有一个结点是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。
C.若一个结点是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的中序遍历序列中的最后一个结点。
D.在二叉树中插人结点，该二叉树便不再是二叉树
36、以下说法正确的是（）
A.若一个树叶是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。
B.若一个树叶是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的中序离历序列中的最后一个结点
C.二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点。
D.在二叉树中，具有一个子女结点，在中序遍历序列中，它没有后继子女结点。
37、以下说法错误的是（）
A.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
B.若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。
C.已知二叉树的前序遍历和后序遍历序列并不能惟一地确定这棵树，因为不知道树的根结点是哪一个。
D.在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点的之后。
6.深度为6（根的层次为1）的二叉树至多有（D）结点。
A）64 B）32 C）31 D）63
7.将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次堆结点编号，根结点的编号为1。
编号为49的结点X的双亲的编号为（ A）。
A）24 B）25 C）23 D）无法确定
15.设深度为k的二叉树上只有度为0和2的结点，则此类二叉树中所含的结点数至少为（C ）。
A）k+1 B）2k C）2k-1 D）2k+1
5. 树最适合用来表示（C）。
A.有序数据元素B.无序数据元素
C.元素之间具有分支层次关系的数据D.元素之间无联系的数据
6. 二叉树的第k层的结点数最多为（D）.
A．2k-1B.2K+1C.2K-1 D.2k-1
4、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（B）
A24B71C48D53
10．在一棵度为3的树中,度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为（C）
A．4B．5C．6D．7
4．二叉树中第i（i≥1）层上的结点数最多有（C）个。
（A）2i（B）2i（C）2i-1（D）2i-1
9．根据二叉树的定义可知二叉树共有（B）种不同的形态。
（A）4（B）5（C）6（D）7
2．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（B）个空指针域。
（A）2m-1（B）2m（C）2m+1（D）4m
4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A）。
（A）BADC（B）BCDA（C）CDAB（D）CBDA
6．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（C）。
（A）9（B）10（C）11（D）12
6．设二叉排序树中有n个结点，则在二叉排序树的平均查找长度为（B）。
（A）O
（1）（B）O（log2n）（C）（D）O（n2）
2．设一棵二叉树的深度为k，则该二叉树中最多有（D）个结点。
（A）2k-1（B）2k（C）2k-1（D）2k-1
9．设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（C）。
（A）N0=N1+1（B）N0=Nl+N2（C）N0=N2+1（D）N0=2N1+l
6．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0=（B）。
（A）Nl+N2+……+Nm（B）l+N2+2N3+3N4+……+（m-1）Nm
（C）N2+2N3+3N4+……+（m-1）Nm（D）2Nl+3N2+……+（m+1）Nm
5．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（D）。
（A）空或只有一个结点（B）高度等于其结点数
（C）任一结点无左孩子（D）任一结点无右孩子
7．设某棵三叉树中有40个结点，则该三叉树的最小高度为（B）。
（A）3（B）4（C）5（D）6
10.深度为k的完全二叉树中最少有（B）个结点。
（A）2k-1-1（B）2k-1（C）2k-1+1（D）2k-1
14.设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（D）。
（A）O（n）（B）O（n2）（C）O（nlog2n）（D）O（1og2n）
5．设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（B）。
（A）2i+1（B）2i（C）i/2（D）2i-1
8．设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（C）。
（A）20（B）256（C）512（D）1024
5. 在二叉排序树中插入一个关键字值的平均时间复杂度为（B）。
（A）O（n）（B）O（1og2n）（C）O（nlog2n）（D）O（n2）
7. 设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（B）。
（A）8（B）7（C）6（D）5
8. 设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉链权中有（C）个度数为0的结点。
（A）5（B）6（C）7（D）8
3．设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（A）。
（A）N1-1（B）N2-1（C）N2+N3（D）N1+N3
9．设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（C）个。
（A）4（B）5（C）6（D）7
6．设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，……，Nm个度数为m的结点，则该树中共有（D）个叶子结点。
（A）
（B）
（C）
（D）
7.二叉排序树中左子树上所有结点的值均（A）根结点的值。
（A）<（B）>（C）=（D）!
=
8.设一组权值集合W=（15，3，14，2，6，9，16，17），要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（D）。
（A）129（B）219（C）189（D）229
10.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（C）个结点。
（A）2n（B）n+l（C）2n-1（D）2n+l
1．假定在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶子结点数为_____。
A．15B．16C．17D．47答案：
B
2．假定一棵二叉树的结点数为18个，则它的最小高度_____。
A．4B．5C．6D．18答案：
B
3．在一棵二叉树中第五层上的结点数最多为_____。
A．8B．15C．16D．32答案：
C
4．在一棵具有五层的满二叉树中，结点总数为_____。
A．31B．32C．33D．16答案：
A
5．已知8个数据元素为（34、76、45、18、26、54、92、65），按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为_____。
A．1B．2C．3D．4答案：
B
6．由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为_____。
A．23B．37C．44D．46答案：
C
7、在树中除根结点外，其余结点分成m（m≥0）个_____的集合T1,T2,T3...Tm
升级会员 