02一选择题：1、以下说法错误的是①树形结构的特点是一个结点可以有多个直接前趋②线性结构中的一个结点至多只有一个直接后继③树形结构可以表达(组织)更复杂的数据④树(及一切树形结构)是一种"分支层次"结构⑤任何只含一个结点的集合是一棵树2．深度为6的二叉树最多有( )个结点①64 ②63 ③32 ④313 下列说法中正确的是①任何一棵二叉树中至少有一个结点的度为2②任何一棵二叉树中每个结点的度都为2 二叉树可空③任何一棵二叉树中的度肯定等于2 ④任何一棵二叉树中的度可以小于24 设森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的右子树上有（）个结点。
①n1-1 ②n1③n1+n2+n3④n2+n3+n4二．名词解释：1 结点的度 3。
叶子 4。
分支点 5。
树的度三填空题二叉树第i(i>=1)层上至多有_____个结点。
1、深度为k(k>=1)的二叉树至多有_____个结点。
2、如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1<=i<=n)的结点X有：若i=1,则结点X是_ ____；若i〉1,则X的双亲PARENT(X)的编号为__ ____。
若2i>n，则结点X无_ _____且无_ _____；否则，X的左孩子LCHILD(X)的编号为____。
若2i+1>n，则结点X无__ ____；否则，X的右孩子RCHILD(X)的编号为_____。
4．以下程序段采用先根遍历方法求二叉树的叶子数，请在横线处填充适当的语句。
Void countleaf(bitreptr t,int *count)/*根指针为t，假定叶子数count的初值为0*/ {if(t!=NULL){if((t->lchild==NULL)&&(t->rchild==NULL))__ __;countleaf(t->lchild,&count);countleaf(t->rchild,&count);}}5 先根遍历树和先根遍历与该树对应的二叉树，其结果_____。
6 由____转换成二叉树时，其根结点的右子树总是空的。
7 哈夫曼树是带权路径度___ _____的树，通常权值较大的结点离根__ ______。
8一棵树的形状如图填空题33所示，它的根结点是_____，叶子结点是______，结点H的度是_____，这棵树的度是_____，这棵树的深度是________，结点F的儿子结点是______，结点G的父结点是_____。
9任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点为_____ ___个。
1．由３个结点所构成的二叉树有种形态。
2. 一棵深度为6的满二叉树有个分支结点和个叶子。
3．一棵具有２５７个结点的完全二叉树，它的深度为。
4. 设一棵完全二叉树具有1000个结点，则此完全二叉树有(100-511)= 个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。
5. 二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。
因而二叉树的遍历次序有六种。
最常用的是三种：前序法（即按N L R次序），后序法（即按次序）和中序法（也称对称序法，即按L N R次序）。
这三种方法相互之间有关联。
若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是。
6. 用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是。
7.一个深度为h的二叉树最多有结点，最少有结点。
二、选择题1．二叉树是非线性数据结构，所以。
（Ａ）它不能用顺序存储结构存储; （Ｂ）它不能用链式存储结构存储; （Ｃ）顺序存储结构和链式存储结构都能存储; （Ｄ）顺序存储结构和链式存储结构都不能使用2. 具有n(n>0)个结点的完全二叉树的深度为。
(Ａ) ⎡log2(n)⎤ (Ｂ) ⎣ log2(n)⎦ (Ｃ) ⎣ log2(n) ⎦+1 (Ｄ) ⎡log2(n)+1⎤3．把一棵树转换为二叉树后，这棵二叉树的形态是。
（Ａ）唯一的（Ｂ）有2种（Ｃ）有多种，但根结点都没有左孩子（Ｄ）有多种，但根结点都没有右孩子4. 树是结点的有限集合，它根结点，记为T。
其余的结点分成为m（m≥0）个的集合T1，T2，…，Tm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。
一个结点的子结点个数为该结点的。
供选择的答案A：①有0个或1个②有0个或多个③有且只有1个④有1个或1个以上B: ①互不相交②允许相交③允许叶结点相交④允许树枝结点相交C：①权②度③次数④序答案：A= B= C=三、简答题1. 给定如图所示二叉树T，请画出与其对应的中序线索二叉树。
1、如图所示的4棵二叉树中，（）不是完全二叉树。
2、在线索化二叉树中，t所指结点没有左子树的充要条件是（）。
A、t->left==NULLB、t->ltag==1C、t->ltag==1且t->left==NULLD、以上都不对3、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（）A、acbedB、decabC、deabcD、cedba4、如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的（）A、前序B、中序C、后序D、层次序5、对一个满二叉树，m个树叶，n个结点，深度为h，则（）A、n=h+mB、h+m=2nC、m=h-1D、n=2（h次方）-16、具有5层结点的二叉平衡树至少有（）个结点。
A、10 B、12 C、15 D、17二、填空题1、结点最少的树为____，结点最少的二叉树为_____。
2、从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是_____。
三、问答题1、假设二叉树采用顺序存储结构，如图（1）所示e af dg c jhi b(1)（1）画出二叉树表示；（2）写出先序遍历，中序遍历和后序遍历的结果；（3）写出结点值c得双亲结点，其左、右孩子；（4）画出把此二叉树还原成森林的图。
05选择题在线索化二叉树中，t所指结点没有左子树的充要条件是______。
A、t->left==NULLB、t->ltag==1C、t->ltag==1且t->left==NULLD、以上都不对1、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为______。
A.2h B.2h-1 C.2h+1 D.h+12、如图所示的4棵二叉树，____不是完全二叉树。
3、树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。
这里，我们把由树转化得到的二叉树叫做这个数对应的二叉树。
结论正确的是_____。
A、树的先根遍历序列与其对应的二叉树的先序遍历序列相同B、树的后根遍历序列与其对应的二叉树的后序遍历序列相同C、树的先根遍历序列与其对应的二叉树的中序遍历序列相同D、以上都不对5、线索二叉树是一种______结构A、逻辑B、逻辑与存储C、物理D、线性二、简答题1、指出树和二叉树的三个主要差别。
2、假设二叉树采用顺序存储结构，如图所示。
（1）画出二叉树表示（2）写出先序遍历，中序遍历，后序遍历的结果（3）写出结点值c的双亲结点，其左、右孩子（4）画出把此二叉树还原成森林的图1.讨论树、森林和二叉树的关系，目的是为了（）A．借助二叉树上的运算方法去实现对树的一些运算B．将树、森林按二叉树的存储方式进行存储C．将树、森林转换成二叉树D．体现一种技巧，没有什么实际意义2．树最适合用来表示 ( )A．有序数据元素 B．无序数据元素C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据3．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B．11 C．15 D．不确定4．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。
与森林F 对应的二叉树根结点的右子树上的结点个数是（）。
A．M1 B．M1+M2 C．M3 D．M2+M35.利用二叉链表存储树，则根结点的右指针是（）。
A．指向最左孩子 B．指向最右孩子 C．空 D．非空二填空题1.深度为k的完全二叉树至少有___ ____个结点，至多有___ ____个结点2.具有n个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点的左右孩子，其余的________个指针域为NULL。
3.树的主要遍历方法有________、________、________等三种。
4．二叉树的先序序列和中序序列相同的条件是___ ___。
5．一个无序序列可以通过构造一棵___ ___树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。
判断题 1. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。
( ) 2.二叉树只能用二叉链表表示。
（）3.用一维数组存储二叉树时，总是以前序遍历顺序存储结点。
（）程序填空 1.以下程序是二叉链表树中序遍历的非递归算法，请填空使之完善。
二叉树链表的结点类型的定义如下：typedef struct node /*C语言/{char data; struct node *lchild,*rchild;}*bitree;void vst(bitree bt) /*bt为根结点的指针*/{ bitree p; p=bt; initstack(s); /*初始化栈s为空栈*/while(p || !empty(s)) /*栈s不为空*/if(p) { push (s,p); (1)___ ; } /*P入栈*/else { p=pop(s); printf(“%c”,p->data);(2)__ __; }/*栈顶元素出栈*/ }2.二叉树存储结构同上题，以下程序为求二叉树深度的递归算法，请填空完善之。
int depth(bitree bt) /*bt为根结点的指针*/{int hl,hr;if (bt==NULL) return((1)_ __);hl=depth(bt->lchild); hr=depth(bt->rchild);if((2)_ __) (3)_ ____；return(hr+1);}07一、选择题1 ．某二叉树的先序和后序遍历序列正好相反，则该二叉树一定是（）。