③任何一棵二叉树中的度肯定等于2 ④任何一棵二叉树中的度可以小于2
12．一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用（ ）遍历方式就可以得到这棵二叉树所有结点的递增序列。 ①先根 ②中根 ③后根 ④层次
13．设森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的右子树上有（ ）个结点。 ①n1-1 ②n1 ③n1+n2+n3 ④n2+n3+n4
14．森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的左孩子上有（ ）个结点。 ①n1-1 ②n1 ③n1+n2+n3 ④n2+n3+n4
15.对含有（ ）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。
①0 ②1 ③2 ④不存在这样的二叉树 16．讨论树、森林和二叉树的关系，目的是为了（ ） ①借助二叉树上的运算方法去实现对树的一些运算 ②将树、森林按二叉树的存储方式进行存储 ③将树、森林转换成二叉树 ④体现一种技巧，没有什么实际意义
26
17．如图选择题17所示二叉树的中序遍历序列是（ ） ①abcdgef ② dfebagc ③dbaefcg ④defbagc
18.已知某二叉树的后续遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是（ ）
①acbed ②deabc ③decab ④cedba
19.如果T2是由有序树T转化而来的二叉树，那么T中结点的前序就是T2中结点的（ ） ①前序 ②中序 ③后序 ④层次序
20．如果T2是由有序树T转化而来的二叉树，那么T中结点的后序就是T2中结点的（ ） ①前序 ②中序 ③后序 ④层次序
21．某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则
其
后
序
遍
历
的
结
点
访
问
顺
序
是
（ ）
①bdgcefha ②gdbecfha ③④ bdgechfa ④ gdbehfca 22.在图选择题22中的二叉树中，（ ）不是完全二叉树。
23、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法 ( )
①正确 ②错误
24、由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法
27
( )
①五确 ②错误
25，二叉树是每个结点的度不超过2的有序树的特殊情况，这种说法 ( ) ①正确 ②错误
26·树最适合用来表示 ( ) ①有序数据元素 ②无序数据元素 ③元素之间具有分支层次关系的数据 ④元素之间无联系的数据 27，深度为5的二叉树至多有( )个结点。 ①16 ②32 ③31 ④10
28、在计算递归函数时，如不使用递归过程，则一般情况下必须借助于（ ）数据结构
①栈 ②树 ③双向队列 ④顺序表
29.堆(Heap)是 ( ) ①完全二叉树 ②线性表 ③满二叉树
30、下列说法中正确的是 ( ) ①二叉树中任何一个结点的度都为2 ②二叉树的度为2
③任何一棵二叉树中至少有一个结点的度为2 ④一棵二叉树的度可以小于2 31、设二叉树根结点的层次为0，一棵高度为h的满二叉树中的结点个数是（ ） ①2h ②2h-1 ③2h-1 ④2h+1-1
32、设二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序( )
①都不相同 ②完全相同 ③先序和中序相同，而与后序不同 ④中序和后序相同，而与先序不同 33·以下说法错误的是 ( ) ①存在这样的二叉树，对它采用任何次序的遍历，其结点访问序列均相同
28
②二叉树是树的特殊情形
③由树转换成二叉树，其根结点的右子树总是空的
④在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树 34、以下说法正确的是 ( ) ①先根遍历树和前序遍历与该树对应的二叉树，其结果不同 ②后根遍历树和前序遍历与该树对应的二叉树，其结果不同 ③前序遍历森林和前序遍历与该森林对应的二叉树，其结果相同 ④后序遍历森林和中序遍历与该森林对应的二叉树，其结果不同
35·以下说法正确的是 ( )
①一般来说，若深度为k的n个结点的二叉树具有最小路径长度，那么从根结点到第k-1层具有最多的结点数为2k-1-1余下的n-2k-1+1个结点在第k层的任一位置上
②若有一个结点是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。
③若一个结点是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的中序遍历序列中的最后一个结点。
④在二叉树中插人结点，该二叉树便不再是二叉树
36、以下说法正确的是 ( ) ①若一个树叶是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。
②若一个树叶是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的中序离历序列中的最后一个结点
③二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点。
④在二叉树中，具有一个子女结点，在中序遍历序列中，它没有后继子女结点。
29
37、以下说法错误的是 ( ) ①哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
②若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。
③已知二叉树的前序遍历和后序遍历序列并不能惟一地确定这棵树，因为不知道树的根结点是哪一个。
④在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点的之后。 四、简答及应用题
1．简述二叉链表的类型定义。 2．简述三叉链表的类型定义。 3．简述孩子链表表示法的类型定义。
4．分别就图简答题4.1中的二叉树和树回答下列问题 (1)哪个是根结点? (2)哪些是叶结点? (3)哪个是G的双亲? (4)哪些是G的祖先? (5)哪些是G的孩子? (6)哪些是E的子孙?
(7)哪些是E的兄弟? 哪些是C的兄弟? (8)结点B和I的层数分别是多少? (9)树的深度是多少?
(10)以结点G为根的子树的深度是多少? (11)树的度数是多少？
30