数据结构题目

1、02一 选择题：1、以下说法错误的是 树形结构的特点是一个结点可以有多个直接前趋线性结构中的一个结点至多只有一个直接后继树形结构可以表达(组织)更复杂的数据树(及一切树形结构)是一种"分支层次"结构任何只含一个结点的集合是一棵树2深度为6的二叉树最多有( )个结点 64 63 32 313 下列说法中正确的是 任何一棵二叉树中至少有一个结点的度为2任何一棵二叉树中每个结点的度都为2 二叉树可空任何一棵二叉树中的度肯定等于2 任何一棵二叉树中的度可以小于24 设森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根

2、结点的右子树上有（ ）个结点。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是_ _；若i1,则X的双亲PARENT(X)的编号为_ _。若2i>n，则结点X无_ _且无_ _；否则，X的左孩子LCHILD(X)的编号为_。若2i+1>n，则结点X无_ _；否则，X的右孩子RCHIL

3、D(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 由 _转换成二叉树时，其根结点的右子树总是空的

4、。7 哈夫曼树是带权路径度_ _的树，通常权值较大的结点离根_ _。8 一棵树的形状如图填空题33所示，它的根结点是_，叶子结点是_，结点H的度是_，这棵树的度是_，这棵树的深度是_，结点F的儿子结点是_，结点G的父结点是_。9任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点为_ _个。03一、填空1 由个结点所构成的二叉树有 种形态。 2. 一棵深度为6的满二叉树有 个分支结点和 个叶子。3 一棵具有个结点的完全二叉树，它的深度为 。4. 设一棵完全二叉树具有1000个结点，则此完全二叉树有(100-511)= 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树

5、，有 个结点只有非空右子树。5. 二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即按 次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 。 6. 用5个权值3, 2, 4, 5, 1构造的哈夫曼（Huffman）树的带权路径长度是 。7.一个深度为h的二叉树最多有 结点，最少有 结点。二、选择题1二叉树是非线性数据结构，所以 。（）它不能用顺序存储结构存储; （）它不能用链式存储结

6、构存储; （）顺序存储结构和链式存储结构都能存储; （）顺序存储结构和链式存储结构都不能使用 2. 具有n(n>0)个结点的完全二叉树的深度为 。() élog2(n)ù () ë log2(n)û () ë log2(n) û+1 () élog2(n)+1ù3把一棵树转换为二叉树后，这棵二叉树的形态是 。（）唯一的 （）有2种（）有多种，但根结点都没有左孩子 （）有多种，但根结点都没有右孩子4. 树是结点的有限集合，它 根结点，记为T。其余的结点分成为m（m0）个 的集合T1，T2，Tm，每个集合又都是树

7、，此时结点T称为Ti的父结点，Ti称为T的子结点（1im）。一个结点的子结点个数为该结点的 。供选择的答案A： 有0个或1个 有0个或多个 有且只有1个 有1个或1个以上 B: 互不相交 允许相交 允许叶结点相交 允许树枝结点相交C： 权 度 次数 序答案：A= B= C= 三、简答题1. 给定如图所示二叉树T，请画出与其对应的中序线索二叉树。2825 3340 60 08 54 5504一、选择题1、如图所示的4棵二叉树中，（ ）不是完全二叉树。A、 B、 C、 D、 2、在线索化二叉树中，t所指结点没有左子树的充要条件是（ ）。 A、t->left=NULL B、t->ltag

8、=1 C、t->ltag=1且t->left=NULL D、以上都不对3、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（ ）A、acbed B、decab C、deabc D、cedba 4、如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的（ ）A、前序 B、中序 C、后序 D、层次序5、对一个满二叉树，m个树叶，n个结点，深度为h，则（ ）A、n=h+m B、h+m=2n C、m=h-1 D、n=2（h次方）-16、具有5层结点的二叉平衡树至少有（ ）个结点。A、10 B、12 C、15 D、17 二、填空题1、结点

9、最少的树为_，结点最少的二叉树为_。2、从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是_。三、问答题1、假设二叉树采用顺序存储结构，如图（1）所示1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20eafdgcjhib (1)（1）画出二叉树表示； （2）写出先序遍历，中序遍历和后序遍历的结果；（3）写出结点值c得双亲结点，其左、右孩子；（4）画出把此二叉树还原成森林的图。05选择题 在线索化二叉树中，t所指结点没有左子树的充要条件是_。 A、t->left=NULL B、t->ltag=1 C、t->

10、ltag=1且t->left=NULL D、以上都不对1、 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_。 A.2h B.2h-1 C.2h+1 D.h+12、 如图所示的4棵二叉树，_不是完全二叉树。 3、 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这个数对应的二叉树。结论正确的是_。A、 树的先根遍历序列与其对应的二叉树的先序遍历序列相同B、 树的后根遍历序列与其对应的二叉树的后序遍历序列相同C、 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D、 以

11、上都不对5、 线索二叉树是一种_结构 A、逻辑 B、逻辑与存储 C、物理 D、线性2、 简答题1、 指出树和二叉树的三个主要差别。2、假设二叉树采用顺序存储结构，如图所示。 （1） 画出二叉树表示（2） 写出先序遍历，中序遍历，后序遍历的结果（3） 写出结点值c的双亲结点，其左、右孩子（4） 画出把此二叉树还原成森林的图 06选择题 1.讨论树、森林和二叉树的关系，目的是为了（ ）A借助二叉树上的运算方法去实现对树的一些运算B将树、森林按二叉树的存储方式进行存储C将树、森林转换成二叉树D体现一种技巧，没有什么实际意义2树最适合用来表示 ( )A有序数据元素 B无序数据元素C元素之间具有分支层次

12、关系的数据 D元素之间无联系的数据3若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）A9 B11 C15 D不确定 4设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。AM1 BM1+M2 CM3 DM2+M35.利用二叉链表存储树，则根结点的右指针是（ ）。A指向最左孩子 B指向最右孩子 C空 D非空二填空题1.深度为k的完全二叉树至少有_ _个结点，至多有_ _个结点2.具有n个结点的二叉树中,一共有_个指针域,其中只有_个用来指向结点的左右孩子，其余的_个指针域为NULL。3.

13、树的主要遍历方法有_、_、_等三种。4二叉树的先序序列和中序序列相同的条件是_ _。5一个无序序列可以通过构造一棵_ _树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。判断题1. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。( ) 2.二叉树只能用二叉链表表示。（ ）3.用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（ ）程序填空1.以下程序是二叉链表树中序遍历的非递归算法，请填空使之完善。二叉树链表的结点类型的定义如下： typedef struct node /*C语言/ char data; struct node *lc

14、hild,*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; i

15、f (bt=NULL) return(1)_ _); hl=depth(bt->lchild); hr=depth(bt->rchild); if(2)_ _) (3)_ _； return(hr+1); 07一、选择题1 某二叉树的先序和后序遍历序列正好相反，则该二叉树一定是（）。A ）空或只有一个结点B ）完全二叉树 C ）二叉排序树D ）2 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树，其中结论（）是正确的。 A ）树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B

16、 ）树的后根遍历序列与其对应的二义树的后序遍历序列相同 c ）树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D ）以上都不对 3 按照二叉树的定义，具有3 个结点的二叉树有（）种。 A ) 3B ) 4C ) SD ) 6 4 深度为5 的二叉树至多有（）个结点。 A ) 16B ) 32C ) 3lD ) 10 5. 二叉树前序遍历和中序遍历序列如下： 前序遍历序列：EFHIJK 中序遍历序列：HFIEJK 则该二叉树根结点的右子树的根为：( ）。 A ) E B ) F C ) D ) H 6 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后

17、序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树，其中结论（）是正确的。 A ）树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B ）树的后根遍历序列与其对应的二义树的后序遍历序列相同 c ）树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D ）以上都不对二、填空题1、由10000个结点构成的二叉排序树在等概率查找的假设下查找成功时的平均查找长度的最大值可能达到_。2、深度为k的完全二叉树至少有_个结点至多有_个结点若按自上而下从左到右次序给结点编号(从1开始)三、算法设计题（1） 假设二叉树T采用如下定义的存储结构 typedef struct node DataTyp

18、e data; struct node *lchild,*rchild,*parent; PBinTree;其中结点的lchild域和rchild域已分别填有指向其左右孩子的指针而parent域中的值为空指针拟作为指向双亲结点的指针域。请编写一个递归算法将该存储结构中各结点的parent域的值修改成指向其双亲结点的指针081已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )A-A+B*C/DE B. -A+B*CD/E C-+*ABC/DE D. -+A*BC/DE2. 在下述结论中，正确的是（ ）只有一个结点的二叉树的度为0; 二叉树的度为2；

19、 二叉树的左右子树可任意交换;深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。A B C D6. 设森林F 对应的二叉树为B，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树的结点个数是（ ）Am-n Bm-n-1 Cn+1 D条件不足，无法确定3二叉树的第I 层上最多含有结点数为（ ）A2I B 2I-1-1 C 2I-1 D2I -14一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）ACABDEFG BABCDEFG CDACEFBG DADCFEG5下面的说法中正确的是（ ）.（1）任何一棵二叉树的叶子结点在三种遍历中的相对次

20、序不变；（2）按二叉树定义，具有三个结点的二叉树共有6 种。A(1)(2) B(1) C(2) D(1)、(2)都错6.由3 个结点可以构造出多少种不同的有向树？（ ）A2 B3 C4 D57从下列有关树的叙述中,选出5 条正确的叙述 （ ）A二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。B当K1 时高度为K 的二叉树至多有2k-1 个结点。C用树的前序周游和中序周游可以导出树的后序周游。D线索二叉树的优点是便于在中序下查找前驱结点和后继结点。E将一棵树转换成二叉树后,根结点没有左子树。F一棵含有N 个结点的完全二叉树,它的高度是LOG2N+1。G在二叉树中插入结点,该

21、二叉树便不再是二叉树。H采用二叉树链表作树的存储结构,树的前序周游和其相应的二叉树的前序周游的结果是一样的。I哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。J用一维数组存储二叉树时,总是以前序周游存储结点2.判断题1任何二叉树的后序线索树进行后序遍历时都必须用栈。2由一棵二叉树的前序序列和后序序列可以唯一确定它。3完全二叉树中，若一个结点没有左孩子，则它必是树叶。4. 二叉树只能用二叉链表表示.5. 一棵有n 个结点的二叉树，从上到下，从左到右用自然数依次给予编号，则编号为i 的结点的左儿子的编号为2i(2i< n)，右儿子是2i+1（2i+1<n）三、填空题1二叉树由

22、_(1)_，_(2)_，_(3)_三个基本单元组成。2树在计算机内的表示方式有_(1)_，_(2)_，_(3)_。3在二叉树中，指针p 所指结点为叶子结点的条件是_。4中缀式a+b*3+4*（c-d）对应的前缀式为_(1)_，若a=1，b=2，c=3，d=4，则后缀式db/cc*a-b*+的运算结果为_(2)_。5二叉树中某一结点左子树的深度减去右子树的深度称为该结点的_.6具有256 个结点的完全二叉树的深度为_。7已知一棵度为3 的树有2 个度为1 的结点，3 个度为2 的结点，4 个度为3 的结点，则该树有_个叶子结点。8深度为k 的完全二叉树至少有_(1)_个结点，至多有_(2)_个结

23、点9下面的类PASCAL 语言递归算法的功能是判断一棵二叉树（采用二叉链表存贮结构）是否为完全二叉树。请把空缺的两部分补写完整。（提示：利用完全二叉树结点序号性质）TYPE link=node;node=RECORD key:keytype; l,r:link; END;VAR all:boolean; n:integer; root:link;FUNC num(t:link):integer;BEGIN (1)_END;PROC chk(t:link;mt 所指结点应有序号:integer)BEGIN (2)_END;BEGIN 建二叉树，其根由root 指出 n:=num(root);求结

24、点数 all:=true; chk(root,1);IF all THEN writeln（该树为完全二叉树！）ELSE writeln （该树非完全二叉树！）END； 10将二叉树bt 中每一个结点的左右子树互换的C 语言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分别为进队，出队和判别队列是否为空的函数，请填写算法中得空白处，完成其功能。typedef struct nodeint data ; struct node *lchild, *rchild; btnode;void EXCHANGE(btnode *bt)btnode *p, *q;if (bt)ADD

25、Q(Q,bt);while(!EMPTY(Q)p=DELQ(Q); q=(1)_; p->rchild=(2)_; (3)_=q;if(p->lchild) (4)_; if(p->rchild) (5)_;11下面使用类pascal 语言写的对二叉树进行操作的算法，请仔细阅读TYPE pointer=tnodetp;tnodetp=RECORD data: char; llink,rlink: pointer；END;linkstack=linknodet;linknodet=RECORD data:pointer； next;linkstack；END;PROC unkn

26、own (VAR t:pointer);VAR p,temp：pointer;BEGIN p:=t;IF p<> NIL THENtemp:=p.llink ；p.llink:=p.rlink;；p.rlink:=temp;unknown(p.llink); unknown(p.rlink); END; 指出该算法完成了什么功能 用栈将以上算法改为非递归算法unknown1,其中有若干语句或条件空缺请在空缺处填写上适当的语句或条件PROC inistack(VAR s:linkstack);(1)_; s.next:=NIL;ENDP;FUNC empty (s:linkstack

27、):boolean;IF (2)_THEN empty:=true ELSE empty:=false;ENDF;FUNC gettop(s:linkstack):pointer;gettop:= (3)_;ENDF;FUNC pop(VAR s:linkstack)：pointer;VAR p:linkstack;pop:=s.next.data; p:=s.next; (4)_；(5)_;ENDF;PROC push (VAR s:linkstack;x:pointer);VAR p:linkstack;new(p); p.data:=x; (6)_; s.next:=p;ENDP;PRO

28、C unknown1(VAR t:pointer);VAR p,temp: pointer; finish: boolean;BEGINinistack(s); finish:=false; p:=t;REPEATWHILE p<> NIL DOtemp:=p.llink; p.llink:=p.rlink; p.rlink:=temp;(7)_; p:=p.llink; ;IF (8)_THEN p:=gettop(s);temp;=pop(s); ELSE (9)_UNTIL (10)_ENDP;091.若二叉树的后序遍历序列为dabec，中序遍历序列为debac，则前序序列遍

29、历为（）。 A、acbed B、decab C、deabc D、cedba2. 具有35个结点的完全二叉树的深度为（） A、5 B、6 C、7 D、83. 在线索化二叉树中，t所指结点没有左子树的充足条件是（）A、t-lchild=NULL B、t->ltag=1 C、t->ltag=1&&t->lchild=NULL D、以上都不对4. 设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是（） A、n在m右方 B、n是m祖先 C、n在m左方 D、n是m子孙5. 线索二叉树是一种（）结构 A、逻辑 B、逻辑和存储 C、物理 D、线性 1、由一棵二叉

30、树后序序列和（）可唯一确定这棵二叉树。 2、含有n个结点的二叉树用二叉链表表示时，有（）个空链域。 3、有m个叶子结点的哈夫曼树有（）个结点。 4、前序为a,b,c且后序c,b,a的二叉树共有（）棵。 5、已知完全二叉树的第4层有6个结点，则其叶子结点数是（）。一棵完全二叉树有500个结点，请问该完全二叉树有多少个叶子结点？有多少个度为1的结点？有多少个度为2的结点？如果完全二叉树有501个结点，结果如何？请写出推导过程。 1. 设二叉树中每个结点均用一个字母表示，若一个结点的左子树或右子树为空，用#表示，现前序遍历二叉树，访问的结点序列为ABD#C#E#F#，写出中序和后序遍历二叉树时结点的

31、访问序列。 10一、单项选择题1若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ） A9 B11 C15 D不确定2二叉树的第I层上最多含有结点数为（ ）A2I B 2I-1-1 C 2I-1 D2I -13已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。 ACBEFDA B FEDCBA C CBEDFA D不定4下面几个符号串编码集合中，不是前缀编码的是（ ）。 A0,10,110,1111 B11,10,001,101,0001 C00,010,0110,1000 Db,c,aa,ac,aba,abb,abc

32、5. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论（ ）是正确的。 A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D.以上都不对二、判断1. 二叉树中所有结点如果不存在非空左子树则不存在非空右子树。（ ）2. 用一维数组存储二叉树时，总是以前序遍历顺序存储结点。( )3. 二叉树中序线索化后，不存在空指针域。（ ）三、填空1.深度为k的完全二叉树至少有_个结点，

33、至多有_个结点2. 在二叉树中，指针p所指结点为叶子结点的条件是_3.设一棵完全二叉树有700个结点，则共有_个叶子结点。四、程序1试写出复制一棵二叉树的算法。二叉树采用标准链接结构2.将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果）111. 列出图所示二叉树的叶结点、分支结点和每个结点的层次。 2. 如果一棵树有n1个度为1的结点, 有n2个度为2的结点, , nm个度为m的结点, 试问有多少个度为0的结点? 试推导之。3. 试分别找出满足以下条件的所有二叉树: (1) 二叉树的前序序列与中序序列相同; (2) 二叉树的中序序列与后序序列相同; (3) 二叉树的前序序列与后序序列

34、相同4. 请画出右图所示的树所对应的二叉树。5. 已知一棵二叉树的先序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树。13一、选择题1.由三个结点可以构造出多少种不同的二叉树( ) 。A) 3 B) 4 C) 5 D) 62.在一棵深度为k的完全二叉树中,所含结点个数不小于( )。A）2k B) 2k+1C) 2k-1 D) 2k-13.对于任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=（ ）。A. n2-1 B. n2+1 C. n2 D. n2-24.已知二叉树的后序遍历序列是d a b e c,中序序列是d e b a

35、 c,则它的前序遍历是 ( )。A) c e d b a B) a c b e d C) d e c a b D) d e a b c二、填空题1如果结点A有 3个兄弟，而且B是A的双亲，则B的度是_。2若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是_。三、应用题1要求二叉树按二叉链表形式存储，（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。完全二叉树定义为：深度为K，具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1至N的结点一一对应。此题以此定义为准。2将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果）NPG

36、HJMOLIKEDFBAC 17选择题1.在一棵二叉树上第4层的结点数最多为（）。A. 2B. 4 C. 6D. 82.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R1.n，结点Ri若有左孩子，其左孩子的编号为结点（）。A. R2i+1B. R2iC. Ri/2D. R2i-13.已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为（）。A. 1 B. 2C. 3D. 44.对二叉排序树进行  ( )遍历，可以得到该二叉树所有结点构成的排序序列。   A、前序      

37、;   B、中序       C、后序         D、按层次5.在一棵具有n个结点的二叉树第i层上，最多具有  ( )  个结点。  A、2i           B、2i+1       C、2i-1  

38、0;       D、2n判断题6.完全二叉树的某结点若无左孩子，则它必是叶结点。   （  ）7.存在这样的二叉树，对它采用任何次序的遍历，结果相同。（ ）8.二叉树就是结点度为2的树。（ ）9.二叉树中不存在度大于2的结点，当某个结点只有一棵子树时无所谓左、右子树。（   ）10.已知二叉树的前序遍历序列和后序遍历序列并不能唯一地确定这棵树，因为不知道树的根结点是哪一个。（）11.中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（）12.将一棵树转换成二叉

39、树后，根结点没有左子树。（   ）13.用树的前序遍历和中序遍历可以导出树的后序遍历。（  ）14.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。（ ）15.不使用递归也能实现二叉树前序、中序和后序遍历。（ ）填空题16.一棵具有个结点的完全二叉树，它的深度为 。17.若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 。 18.用5个权值3, 2, 4, 5, 1构造的哈夫曼（Huffman）树的带权路径长度是 。解答题19.已知二叉树的中序遍历序列是DBGEAFHC，后序遍历序列是DGE

40、BHFCA，请构造一棵二叉树,并给出前序遍历序列。18一、单项选择题 以下说法错误的是 ( )A树形结构的特点是一个结点可以有多个直接前趋B线性结构中的一个结点至多只有一个直接后继C树形结构可以表达(组织)更复杂的数据D树(及一切树形结构)是一种"分支层次"结构E任何只含一个结点的集合是一棵树2下列说法中正确的是 ( )A任何一棵二叉树中至少有一个结点的度为2 B任何一棵二叉树中每个结点的度都为2C任何一棵二叉树中的度肯定等于2 D任何一棵二叉树中的度可以小于23讨论树、森林和二叉树的关系，目的是为了（ ）A借助二叉树上的运算方法去实现对树的一些运算B将树、森林按二叉树的存

41、储方式进行存储C将树、森林转换成二叉树D体现一种技巧，没有什么实际意义4树最适合用来表示 ( )A有序数据元素 B无序数据元素C元素之间具有分支层次关系的数据 D元素之间无联系的数据12已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。ACBEFDA B FEDCBA C CBEDFA D不定 13已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ ）。Aacbed Bdecab Cdeabc Dcedba 二、判断题（在各题后填写“”或“×”）1. 完全二叉树一定存在度为1的结点。( )2对于有N

42、个结点的二叉树，其高度为log2n。( )3. 二叉树的遍历只是为了在应用中找到一种线性次序。( )4. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。( )三、填空题1在二叉树中，指针p所指结点为叶子结点的条件是_ _。2深度为k的完全二叉树至少有_个结点，至多有_ _个结点。3高度为8的完全二叉树至少有_个叶子结点。4.具有n个结点的二叉树中,一共有_个指针域,其中只有_个用来指向结点的左右孩子，其余的_个指针域为NULL。5树的主要遍历方法有_、_、_等三种。20一 选择题1.如果T2是由数T转换而来的二叉树，那么对T中结点的后序遍历就是对T2中

43、结点的_遍历。A 先序 B 中序 C 后序 D 层次序2. 设数T的度是4，其中度为1，2，3和4的结点个数分别为4，2，1，1，则T中的叶子数为_ A.5 B.6 C.7 D.83. 由4个结点可以构造出_种不同的二叉树。 A.10 B.12 C.14 D.164. 二叉树在线索后，人不能有效求解的问题是_ A. 在先序线索二叉树中求先序后继 B. 在中序线索二叉树中求中序后继 C. 在中序线索二叉树中求中序前驱 D. 在后序线索二叉树中求后序后继5. 一颗二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是_ A.9 B.11 C.15 D.不确定6.设高度为h的二叉树只有

44、度为0和2的结点，则此类二叉树中所包含的结点数至少为_个 A. 2h B. 2h-1 C.2h+1 D. h+17.设给定权值的叶子总数为n 个，其哈夫曼数的结点总数为_ A. 不确定 B 2n C. 2n+1 D.2n-18. 某二叉树的先序遍历和后序遍历正好相反，则此二叉树一点是_ A. 空或只有一个结点 B. 完全二叉树 C. 单支数 D. 高度等与结点数9. 在二叉树的先序序列，中序遍历和后序遍历中，所有叶子结点的先后顺序_- A 都不相同 B. 完全相同 C. 先序和中序相同，而与后序不同 D. 中序和后序相同，而与先序不同10. 根据使用频率，为五个字符设计的哈夫曼编码不可能是_

45、A.111,110,10,01,00 B. 000,001,010,011,1 C. 100,11,10,1,0 D. 001,000,01,11,10二填空题 1.已知二叉树有50个叶子结点，则二叉树的总结点数至少是_ 2.树在计算机中的存储结构有_._-和_ 3.在一棵二叉树中，度为0的结点个数为N0,度为2的结点个数是N2,则有N0=_ 4.叶子权数（5，6，17，8，19）所构造的哈夫曼数带权路径长度为_ 5.设一棵完全二叉树叶子结点数为k ，最后一层结点数为偶数时，则该二叉树的高度为_,最后一层结点数为奇数时，则该二叉树的高度为_ 6.有_种不同形态的二叉树可以按照中序遍历得到相同的

46、abc序列 7.已知二叉树先序为ABDEGCF，中序为DBGEACF,则后序一定是_ 8.深度为k的完全二叉树至少有_个结点，至多有_个节点 9.具有10个叶子的哈夫曼树，其最大高度为_,最小高度为_ 10.设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端节点，则B中右指针域为空的结点有_个三判断题 1.哈夫曼树的结点个数不可能是偶数 2.二叉树中序线索化后，不存在空指针域 3.二叉树线索化后，任意一个结点均有指向其前驱和后继的线索 4.哈夫曼编码是前缀编码 5.非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子 6.必须把一般数转换成二叉树以后才能进行存储 7.由先

47、序和后序遍历序列不能唯一确定一棵二叉树 8.一棵树中的叶子数一定等于与其对应的二叉树的叶子数 9.一个树的叶子数，在前序遍历和后序遍历下，皆以相同的相对位置出现 10在哈夫曼树中权值相同的叶节点都在同一层上四综合题 1.已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA,写出其先序遍历序列五程序填空 1.一棵以孩子兄弟表示法存储，递归算法计算并返回根为r的数中叶子结点的个数（NULL代表空指针） Typedef struct tnode Struct tnode *firstson, *nextbrother; Tnode; Int numberofleaf(Tnode

48、*r) Int num; If(r=NULL) num=0; Else if(r->firstson=NULL) Num=_+numberrofleaf(r->nextbrother); Else_; Return(num); 2. 假设二叉树t的结点有四个字段，它们分别是：data. Lchild .rchild.parent,，其中data存放结点值，lchild和rchild分别指向左子结点和右子结点，parent指向父结点。在下列程序中，非递归函数mid_order(t)实现了对二叉树t的中序遍历 Type struct node Int data; Struct node *ichild,*rchild; Struct node*parent; Node; Void mid_order(Node *t) Node *p,*q; P=NULL;q=t; Do While(q!=NULL) _(1)_; q=q->lchild; If( (2) ) printf(“%5d,p->data”); _