数据结构习题与答案--树和二叉树

一、判断题

( t )01、若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。

( f )02、二叉树中每个结点的两棵子树的高度差等于1。

(t  )03、二叉树中每个结点的两棵子树是有序的。

( f )04、二叉树中每个结点有两棵非空子树或有两棵空子树。

( f )05、二叉树中所有结点个数是2k-1-1，其中k是树的深度。

(f  )06、二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。

( f )07、对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。

(t  )08、用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。

(t)09、具有12个结点的完全二叉树有5个度为2的结点。

( f )10、二叉树中每个结点的关键字值大于其左非空子树(若存在的话)所有结点的关键字值，且小于其右非空子树(若存在的话)所有结点的关键字值。

( f )11、二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索。

( t )12、二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。

二、填空题

01、由3个结点所构成的二叉树有_5_种形态。 

02、一棵深度为6的满二叉树有____个分支结点和____个叶子。

03、一棵具有257个结点的完全二叉树，它的深度为____。

04、设一棵完全二叉树有700个结点，则共有____个叶子结点。

05、设一棵完全二叉树具有1000个结点，则此完全二叉树有____个叶子结点，有____个度为2的结点，有____个结点只有非空左子树，有____个结点只有非空右子树。

06、一棵含有n个结点的k叉树，可能达到的最大深度为____，最小深度为____。

07、二叉树的基本组成部分是：根(N)、左子树(L)和右子树(R)。因而二叉树的遍历次序有六种。最常用的是三种：前序法(即按N L R次序)，后序法(即按LRN次序)和中序法(也称对称序法，即按L N R次序)。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是____。

08、用5个权值{3, 2, 4, 5, 1}构造的哈夫曼(Huffman)树的带权路径长度是____。

三、选择题

(  )01、树最适合用来表示__。

A)有序数据元素

B)无序数据元素

C)元素之间具有分支层次关系的数据

D)元素之间无联系的数据

(  )02、假定在一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为__个。

A)15   B)16   C)17   D)47

(  )03、假定一棵三叉树的结点数为50，则它的最小高度为__。

A)3   B)4   C)5   D)6

(  )04、在一棵二叉树上第5层的结点数最多为__。

A)8   B)16   C)15   D)32

(  )05、用顺序存储方法将完全二叉树中的所有结点逐层存放在数组R[1..n]中，结点R[i]若有子树，则左子树是结点__。

A)R[2i+1]   B)R[2i]   C)R[i/2]   D)R[2i-1]

(  )06、在一棵具有k层的满三叉树中，结点总数为__。

A)(3k-1)/2   B)3k-1   C)(3k-1)/3   D) 3k

(  )07、由带树为9,2,5,7的四个叶子结点树造一棵哈夫曼树，该树的带权路径长度为__。

A)29   B)37   C)46   D)44

(  )08、具有n(n>0)个结点的完全二叉树的深度为  。

A)log2(n)   B)log2(n)   C)log2(n)+1   D)log2(n)+1

(  )09、由n个数据元素构造的哈夫曼树，共有( )个结点。

A)n-1   B)2n-1   C)2n   D)2n+1

(  )10、任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序__。

A)不发生改变   B)发生改变

C)不能确定   D)以上都不对

(  )11、设a,b为一棵二叉树上的两个结点，在中序遍历中，a在b前面的条件是__。

A)a在b的右方   B)a在b的左方

C)a是b的祖先   D)a是b的子孙

(  )12、如图所示，其中__不是完全二叉树。

(  )13、在线索二叉树中，t所指结点没有左子树的充要条件是__。

A)t->lchild==NULL

B)t->ltag==1

C)t->ltag==1 && t->lchild==NULL

D)以上都不对

(  )14、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为__。

A)2h   B)2h-1   C)2h+1   D)h+1

(  )15、以下说法中错误的是__。

A)哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近

B) 若一个二叉树的树叶是某子树中序遍历序列中的第一个结点，则它必是该子树后序遍历序列中的第一个结点

C)已知二叉树的前序遍历和后序遍历并不能惟一地确定这棵树，因为不知道树的根结点是哪一个

D)在前序遍历二叉树的序列中任何结点其子树的结点都是直接跟在该结点之后的

(  )16、二叉树在线索化后，仍不能有效求解的问题是__。

A)先序线索二叉树中求先序后继

B)中序线索二叉树中求中序后继

C)中序线索二叉树中求中序前驱

D)后序线索二叉树中求后序后继

(  )17、棵有124个叶结点的完全二叉树，最多有__个结点。

A)247   B)248   C)249   D)250

(  )18、在N个结点的线索二叉树中，线索的数目为__。

A)N-1   B)N   C) N+1   D)2N

(  )19、设树T的高度为4，其中度为1、2、3和4的结点个数分别为4、2、1、1，则T中的叶子数为__。

A)5   B)6   C)7   D)8

(  )20、下列有关二叉树的说法正确的是__。

A)二叉树的度为2

B)一棵二叉树可以小于2

C)二叉树中至少有一个结点的度为2

D)二叉树中任一个结点的度都为2

(  )21、某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则前序序列是__。

A)EGFACDB    B)EACBDGF

C)EAGCFBD    D)上面都不对

(  )22、设森林F对应的二叉树为B，它有m个结点，B的根为P，P的右子树结点个数为n，森林F中的第一棵树的结点个数是__。

A)m-n   B)m-n-1   C)n+1   D)条件不充分，无法确定

(  )23、对二叉排序树进行__遍历，可以得到该二叉树所有结点构成的排序序列。

A)先序   B)中序   C)后序   D)按层次

(  )24、对于一棵具有n个结点、度为4的树来说，__。

A)树的高度至多是n-3

B)树的高度至多是n-4

C)第i层上至多有4*(i-1)个结点

D)至少在某一层上正好有4个结点

(  )25、度为4、高度为h的树，__。

A)至少有h+3个结点    B)至多有4h-1个结点

C)至多有4h个结点     D)至少有h+4个结点

(  )26、用双亲数组法表示树，其优点之一是__比较方便。

A)找指定结点的双亲   B)找指定结点的孩子

C)找指定结点的兄弟   D)判断某结点是不是树叶

(  )27、用孩子链表法表示树，其优点之一是__比较方便。

A)判断两个指定结点是不是兄弟

B)找指定结点的双亲

C)判断指定结点在第几层

D)计算指定结点的度数

(  )28、如果用孩子链表法来表示树，则__。

A)树的高度等于各链表长度的最大值

B)树叶的数目和链表的数目成反比

C)树的度数等于各链表长度的最大值

D)结点的数目等于各链表长度之和

(  )29、如果在表示树的二叉链表中有6个空的左指针域，7个空的右指针域，5个结点左、右指针域都为空，则该树中叶子结点的个数是__。

A)7   B)6   C)5   D)不能确定

(  )30、如果用二叉链表法来表示一棵具有n (n>1)个结点的树，则在二叉链表中__。

A)至多有n-1个非空的右指针域

B)至少有2个空的右指针域

C)至少有2个非空的左指针域

D)至多有n-1个空的右指针域

(  )31、二叉树和度为2的树的相同之处包括__。

A)每个结点都有一个或两个孩子结点

B)至少有一个根结点

C)至少有一个度为2的结点

D)每个结点至多只有一个双亲结点

(  )32、“二叉树为空”意味着二叉树__。

A)由一些没有赋值的空结点构成

B)根结点没有子树

C)不存在

D)没有结点

(  )33、在高度为h的完全二叉树中，__。

A)度为0的结点都在第h层上

B)第i(1≤iC)第i(1≤iD)不存在度为1的结点

(  )34、若树中结点的前序序列是abcdef，后序序列是bdecfa，则__。

A)结点c有两个孩子

B)树有两个度为0的结点

C)树的高度为5

D)不能唯一确定该树的结构

(  )35、若树中结点的前序序列是abcdefg，后序序列前面3个结点是bde，则后序序列的后面4个结点有可能是__。

A)gcfa   B)gacf   C)afgc   D)cfga

(  )36、若某棵二叉树结点的前序序列和中序序列相同，则该二叉树__。

A)只有一个结点          B)每个结点都没有左孩子

C)每个结点都没有右孩子  D)不存在

(  )37、若某棵二叉树结点的后序序列和层次序列正好相反，则该二叉树__。

A)每个结点都没有右孩子   B)不存在度为2的结点

C)每个结点都没有左孩子   D)不存在

(  )38、若某棵二叉树结点的前序序列和后序序列相同，则该二叉树__。

A)度为1

B)只有一个结点

C)每个结点都没有左孩子

D)每个结点都没有右孩子

(  )39、在一棵高度小于4的二叉树中，若结点的前序序列是abcdef，则结点的中序序列有可能是__。

A)dcebaf   B)bcdafe   C)cbdafe   D)fcadbe

(  )40、若二叉树中结点的中序序列是abcdef，则结点的前序序列不可能是__。

A)dbacef   B)acbedf   C)efbacd   D)bafdce

(  )41、在一棵高度小于5的二叉树中，若结点的中序序列是abcdef，则结点的后序序列有可能是__。

A)bdfeca   B)befdca   C)bdefca   D)fedcba

(  )42、在任何一棵二叉树中，如果结点a有左孩子b、右孩子c，则在结点的前序序列、中序序列、后序序列中，__。

A)结点b一定在结点a的前面

B)结点a一定在结点c的前面

C)结点b一定在结点c的前面

D)结点a一定在结点b的前面

(  )43、若二叉树结点的前序序列是abcd，后序序列是dcba，则该二叉树__。

A)每个分支结点都没有左孩子

B)每个分支结点都只有一个孩子

C)每个分支结点都没有右孩子

D)高度可能为3

(  )44、如果二叉树中结点的前序序列是...a...b...，中序序列是...b...a...，则__。

A)结点a和结点b分别在某结点的左子树和右子树中

B)结点b在结点a的右子树中

C)结点b在结点a的左子树中

D)结点a和结点b分别在某结点的两棵非空子树中

(  )45、如果二叉树结点的前序序列和中序序列分别是abcdefgh和bcafegdh，则该二叉树的后序序列是__。

A)一定是cbfgehda   B)可能是cbgefhda

C)不存在           D)有多种可能

(  )46、如果完全二叉树结点的后序序列是abcdefgh，则结点的前序序列__。

A)不能唯一确定   B)是hgfedcba

C)是abdchegf    D)是hdbacgef

(  )47、二叉树若用顺序方法存储，则下列四种运算中的__最容易实现。

A)前序遍历二叉树

B)判断两个指定结点是不是在同一层上

C)层次遍历二叉树

D)根据结点的值查找其存储位置

(  )48、根据使用频率为五个字符设计的哈夫曼编码不可能是__。

A)111，110，10，01，00

B)000，001，010，011，1

C)100，11，10，1，0

D)001，000，01，11，10

(  )49、用整数1,2,3,4,5作为五个树叶的权值，可构造一棵带树路径长度值为__的哈夫曼树。

A)33   B)15   C)34   D)54

(  )50、树的后根遍历序列等同于该树对应的二叉树的__。

A)先序遍历   B)中序遍历

C)后序遍历   D)层次遍历

(  )51、在下列存储形式中，__不是树的存储结构。

A)双亲表示法       B)孩子链表表示法

C)孩子兄弟表示法   D)顺序存储表示法

(  )52、利用二叉链表存储树，则根结点的右指针是__。

A)指向最左孩子   B)指向最右孩子

C)空             D)非空

(  )53、由树为8,2,5,7的数据元素构造一棵哈夫曼树，该树的带权路径径长度为__。

A)23   B)37   C)46   D)43

(  )54、设T是哈夫曼树，具有5个叶子结点，树T的高度最高可以是__。

A)3   B)4   C)5   D)6

(  )55、把一棵树转换为二叉树后，这棵二叉树的形态是  。

A)唯一的

B)有多种

C)有多种，但根结点都没有左孩子

D)有多种，但根结点都没有右孩子

(  )56、如果T2是由有序树T1转换而来的二叉树，那么T1中结点的先序就是T2中结点的__。

A)先序   B)中序   C)后序   D)层次序

(  )57、如果T2是由有序树T1转换而来的二叉树，那么T1中结点的后序就是T2中结点的__。

A)先序   B)中序   C)后序   D)层次序

(  )58、某二叉树的先序遍历和后序遍历序列正好相反，则该二叉树一定是__。

A)空或只有一个结点   B)完全二叉树

C)二叉排序树         D)高度等于其结点的树

(  )59、如图所示的T2是由森林T1转换而来的二叉树，那么森林T1有__个叶子结点。

A)4   B)5   C)6   D)7

(  )60、设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是__。

A)n在m右方   B)n是m祖先

C)n在m左方   D)n是m子孙

四、简答题

01、给定二叉树的两种遍历序列，前序遍历序列：DACEBHFGI；中序遍历序列：DCBEHAGIF。试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。

02、若根据右面图中所示的二叉树建立线索二叉树，请在图中画出其中表示前驱的线索，并写出求结点后继的规律。