数据结构习题精编二叉树.docx

数据结构习题精编二叉树.docx

《数据结构习题精编二叉树.docx》由会员分享，可在线阅读，更多相关《数据结构习题精编二叉树.docx（38页珍藏版）》请在冰点文库上搜索。

数据结构习题精编二叉树

数据结构习题精编：

二叉树

一、选择题

1．设树T的度为4，其中度为1、2、3和4的结点个数分别为4、2、1、1，则T中

的结点总数为

A．13B．14C．15D．16

2．在一棵度数为4的树T中，若有20个度为4的结点，10个度为3的结点，1个

度为2的结点，10个度为1的结点，则树T的叶结点个数是

A．41B．82C．113D．122

3．下列关于二叉树的说法中，正确的是

A．二叉树的度为2B．二叉树中至少有一个结点的度为2

C．一棵二叉树的度可以小于2D．二叉树中任何一个结点的度都为2

4．具有4个结点的二叉树可有

A．7种形态B．10种形态C．11种形态D．14种形态

5．已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的

结点个数最多是

A．39B．52C．111D．119

6．二叉树中第5层上的结点个数最多为

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

7．深度为h的完全二叉树中，结点数最多为

A．2h-1B．2h-1C．2hD．2h+1

8．深度为k的二叉树至多有

A．2k-1-1个叶子B．2k-1个叶子C．2k-1个叶子D．2k个叶子

9．已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为

A．7B．8C．9D．10

10．若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数为

A．257B．258C．384D．385

11．具有10个叶结点的二叉树中，度为2的结点的个数为

A．8B．9C．10D．11

12．一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为

A．0B．1C．48D．49

13．一棵二叉树有100个结点，若用二叉链表存储，空指针域有

A．50个B．99个C．100个D．101个

14．二叉树若采用二叉链表结构表示，则对于n个结点的二叉树一定有

A．2n-1个指针域，其中n个指针域为NULL

B．2n-1个指针域，其中n+1个指针域为NULL

C．2n个指针域，其中n个指针域为NULL

D．2n个指针域，其中n+1个指针域为NULL

15．一棵有16结点的完全二叉树，对它按层编号，根结点的编号为1。

对编号为7

的结点X，它的双亲结点及右孩子结点的编号分别为

A．2，14B．2，15C．3，14D．3，15

16．将含有80个结点的完全二叉树从根这一层开始，每层从左到右依次对结点编号，

根结点的编号为1。

下列关于编号为40的结点的左右孩子的说法中，正确的是

A．左孩子不存在，右孩子不存在

B．左孩子不存在，右孩子的编号为80

C．左孩子的编号为79，右孩子的编号为80

D．左孩子的编号为80，右孩子不存在

17．假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存

放在BT[0]。

若BT[i]中的结点有左孩子，则左孩子存放在

A．BT[i/2]B．BT[2*i-1]C．BT[2*i]D．BT[2*i+1]

18．某中缀形式的算术表达式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为

A．-+*ABC/DEB．-+A*BC/DEC．-A+B*CD/ED．-A+B*C/DE

19．若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是

A．树中只有一个根结点B．树中非叶结点均只有左子树

C．树中没有度为2的结点D．树中非叶结点均只有右子树

20．若一棵具有n（n>0）个结点的二叉树的先序序列与后序序列正好相反，则该二叉

树一定是

A．深度为n的二叉树B．存在度为2的结点的二叉树

C．结点均无左孩子的二叉树D．结点均无右孩子的二叉树

21．若一棵具有n（n>0）个结点的二叉树的先序遍历序列与后序遍历序列正好相反，

则该二叉树中叶子结点的个数是

A．1B．n/2-1C．n/2D．无法确定的

22．已知一棵二叉树的先序遍历序列为ABCDEF，中序遍历序列为CBAEDF，则其

后序遍历序列为

A．ABCDEFB．CBEDFAC．CBEFDAD．FEDCBA

23．已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，则它的先序遍历

序列是

A．acbedB．cedbaC．deabcD．decab

24．某二叉树的先序遍历序列为EFHIGJK，中序遍历序列为HFIEJKG，则该二叉树

根的右子树的根是

A．EB．FC．GD．H

25．一棵二叉树的先序遍历序列为ABCDEFG，它的中序遍历序列可能是

A．ABCDEFGB．ADBCFEGC．CABDEFGD．DACEFBG

26．若一棵二叉树的先序遍历序列和后序遍历序列分别为ABCD和DCBA，则该二叉

树的中序遍历序列不会是

A．ABCDB．BCDAC．CBDAD．DCBA

27．某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号（编号从1开

始），且有如下性质：

T中任一结点V，其编号等于左子树上的最小编号减1，而V

的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1。

由此可知，

编号依据的顺序是

A．前序遍历序列B．中序遍历序列C．后序遍历序列D．层次遍历序列

28．n个结点的线索二叉树上含有的线索数为

A．n－lB．nC．n＋lD．2n

29．下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是

A．B．C．D．

30．给定二叉树如图1所示。

设D代表二叉树的根，L代表根结点的左子树，R代

表根结点的右子树。

若遍历后的结点序列为FEADBC，则其遍历方式是

A．DRLB．LRDC．RDLD．RLD

图1二叉树图2一棵树

31．将图2所示的一棵树转换为二叉树，结点D是

A．A的右孩子B．B的右孩子C．C的右孩子D．E的右孩子

32．可以唯一地转化成一棵一般树的二叉树的特点是

A．根结点没有孩子B．根结点无左孩子

C．根结点无右孩子D．根结点有两个孩子

33．将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，

则在原来的森林中，u和v可能具有的关系是：

I．父子关系，II．兄弟关系，III．u

的父结点与v的父结点是兄弟关系

A．只有IIB．I和IIC．I和IIID．I、II和III

34．设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为18、10和24。

与森林F对应的二叉树根结点的右子树上的结点个数是

A．18B．24C．28D．34

35．由m棵结点数为n的树组成的森林，将其转化为一棵二叉树，则该二叉树中根结

点的右子树上具有的结点个数是

A．m*n-1B．m*（n-1）C．n*（m-1）D．m*n

36．已知一棵由2008个结点组成的树，其叶结点个数为115，该树对应的二叉树中

无右孩子的结点个数是

A．114B．115C．1893D．1894

37．对n（n>=2）个权值均不相同的字符构造哈夫曼树，下列关于该树的叙述中，错误

的是

A．该树一定是一棵完全二叉树

B．树中一定没有度为1的结点

C．树中两个权值最小的结点一定是兄弟结点

D．树中任一非叶结点的权值一定不小于下一层任一结点的权值

38．有m个叶子结点的哈夫曼树，其结点总数是

A．2*m-1B．2*mC．2*m+1D．2*（m+1）

39．下列编码中，属于前缀码的是

A．{0,1,00,11}B．{0,10,11,110}C．{1,01,000,001}D．{1,01,011,010}

40．由权值为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为

A．23B．37C．44D．46

二、填空题

1．n（n>1）个结点的各棵树中，其深度最小的那棵树的深度是______，它共有______个叶子结点和________个非叶子结点；深度最大的那棵树的深度是______，它共有______个叶子结点和________个非叶子结点。

2．在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数是________。

3．一棵树T由一个度为1的结点、2个度为2的结点、3个度为3的结点、4个度为4的结点和若干叶子结点组成，则T的叶子结点数为______。

4．有4个结点且深度为4的二叉树的形态共有_______种。

5．设一棵二叉树中度为2的结点数为10，则该树的叶子结点数为_________。

6．已知某二叉树有50个叶子结点，则该二叉树的总结点数至少是______。

7．深度为k的二叉树至多有________个结点，最少有______个结点。

8．任意一棵完全二叉树中，度为1的结点数最多为________。

9．深度为k的完全二叉树至少有________个结点，至多有________个结点。

10．深度为8的完全二叉树至少有______个叶子结点。

深度为k的完全二叉树至少有______个叶子结点。

11．具有256个结点的完全二叉树的深度为______。

12．已知某棵完全二叉树的第5层只有7个结点，则该树共有_______个叶子结点。

13．某完全二叉树有100个结点，其中叶子结点的个数为__________，度为1的结点的个数为__________。

14．一棵满二叉树，若有m个叶子结点，则树中结点总数为____________。

15．一棵有n个结点的满二叉树有_________个度为1的结点、有_________个度为2的结点和_________个叶子，该满二叉树的深度为_________。

16．假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]。

若BT[i]中的存放的结点有左孩子和右孩子，则其左孩子存放在___________，右孩子存放在___________，父结点存放在___________。

17．一个深度为k的，具有最少结点数的完全二叉树按层次（同层次从左到右）用自然数依此对结点编号，则编号最小的叶子的序号是___________；编号是i的结点所在的层次号是___________（根所在的层次号规定为1层）。

18．设某二叉树采用顺序存储结构存储在数组BT[m]中，其中根结点存放在BT[0]。

BT[i]和BT[j]（0<=i，j

19．某二叉树采用二叉链表作为存储结构，在该二叉树中，指针p（p不为空）所指结点为叶子结点的条件是_______________。

20．某二叉树的先序遍历序列为ABDEGCF，中序遍历序列为DBGEACF，则该二叉树中根结点的右孩子是_______，其后序遍历序列为___________________。

21．线索二叉树的左线索指向其_________，右线索指向其_________。

一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为______。

22．设一棵后序线索树的深度是50，结点x是树中的一个结点，其双亲是结点y，x是y的左孩子，y的右子树的深度是31，则确定x的后继最多需经过______个中间结点（不含后继及x本身）。

23．设F是由T1、T2、T3三棵树组成的森林，与F对应的二叉树为B。

已知T1、T2、T3的结点数分别为n1、n2和n3，则二叉树B的左子树中有______个结点，右子树中有________个结点。

24．一棵树采用孩子兄弟表示法，每个结点有两个指针域，分别指向该结点的第1个孩子结点和下一个兄弟结点。

若指向下一个兄弟结点的指针域有n个为空，则该树有________个非终端结点。

25．有一份电文中共使用6个字符a、b、c、d、e和f，它们的出现频率依次为2、3、4、7、8、9。

为对这六个字符进行编码，构造一棵哈夫曼树，该哈夫曼树的结点个数为_______，带权路径长度WPL为__________，字符“d”的哈夫曼编码的长度为________。

三、解答题

1．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，…，nk个度为k的结点，问该树中有多少个叶子结点？

2．一棵共有n个结点的树，只有度为k的分支结点和度为0的叶子结点，求该树中叶子结点的个数。

3．一棵深度为h的满k叉树有如下性质：

根结点所在层次为1；第h层上的结点都是叶子结点；其余各层上每个结点都有k棵非空子树，如果按层次自顶向下，同一层自左向右，顺序从1开始对全部结点进行编号，试问：

（1）各层的结点个数是多少？

树中总结点数是多少？

（2）编号为i的结点的双亲结点（若存在）的编号是多少？

（3）编号为i的结点的第m个（1<=m<=k）孩子结点（若存在）的编号是多少？

（4）编号为i的结点有右兄弟的条件是什么？

其右兄弟结点的编号是多少？

4．

（1）已知完全二叉树的第7层有8个结点，则其叶子结点数是多少？

（2）已知完全二叉树的第7层有8个叶子结点，则整个二叉树的结点数最多是多少？

5．找出所有满足下列条件的二叉树

（1）它们进行先序遍历和中序遍历时，得到的结点访问序列相同。

（2）它们进行后序遍历和中序遍历时，得到的结点访问序列相同。

（3）它们进行先序遍历和后序遍历时，得到的结点访问序列相同。

（4）它们进行中序遍历和层次遍历时，得到的结点访问序列相同

6．已知某二叉树如图3所示。

（1）试给出其顺序存储结构表示。

（2）画出其二叉链表存储表示。

（3）写出该二叉树的先序遍历序列、中序遍历序列和后序遍历序列。

图3某二叉树

（4）假设二叉树的RDL遍历算法定义如下：

若二叉树非空，则依次执行如下操作：

1）遍历右子树；2）访问根节点；3）遍历左子树。

试写出该二叉树的RDL遍历序列。

7．设二叉树BT的存储结构如下:

1

2

3

4

5

6

7

8

9

10

Lchild

0

0

2

3

7

5

8

0

10

1

Data

J

H

F

D

B

A

C

E

G

I

Rchild

0

0

0

9

4

0

0

0

0

0

其中BT为二叉树根结点的指针，其值为6，Lchild、Rchild分别为结点的左、右孩子指针域，data为结点的数据域。

（l）画出二叉树BT的逻辑结构。

（2）写出按先序、中序、后序遍历该二叉树所得到的结点序列。

8．已知某二叉树的先序遍历序列和中序遍历序列分别为ABCDFGIJEHK和BAFDIGJCHKE。

（1）画出该二叉树；

（2）画出这棵二叉树的后序线索树。

（3）画出与

（1）求得的二叉树对应的森林。

9．已知一棵二叉树的先序遍历序列、中序遍历序列和后序遍历序列如下，其中空缺了部分，试画出该二叉树。

先序：

_BC_EFG_IJK_

中序：

CBED_GAJ_H_L

后序：

_E_FD_J_L_HA

10．已知一棵线索化的二叉排序树如图4所示。

图4线索二叉树

（1）说明该树的线索化是基于何种遍历次序的。

（2）在该树中插入元素值为53的结点并修改相应线索，画出修改之后的树。

11．已知一棵完全二叉树按顺序结构存储在数组A[N]中，其中根结点存储在A[1]中，A[0]中存放二叉树中结点的个数。

如何求出结点A[i]和A[j]的最近的共同祖先？

12．将图5所示的由三棵树组成的森林转化为一棵二叉树。

图5三棵树组成的森林

13．已知一个森林的先序遍历序列和后序遍历序列如下，试构造出该森林。

先序序列：

ABCDEFGHIJKLMNO

后序序列：

CDEBFHIJGAMLONK

14．假设通信电文使用的字符集为{a，b，c，d，e，f，g}，字符的哈夫曼编码依次为0110，10，110，111，00，0111和010。

（1）请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符。

（2）若这些字符在电文中出现的频度分别为3、35、13、15、20、5和9，求该哈夫曼树的带权路径长度。

15．设用于通讯的电文仅由A~H这8个字母组成，它们在电文中出现的频率分别为0.07、0.19、0.02、0.06、0.32、0.03、0.21和0.10，试设计哈夫曼树及其编码。

使用0~7的二进制表示形式是另一种编码方案。

给出两种编码的对照表、带权路径长度WPL值并比较两种方案的优缺点。

四、分析题

1．阅读下列程序，并回答问题。

#include

usingnamespacestd;

voidfun541（chara[],inti,intn）

{

if（i

='0'）

{

fun541（a,2*i+1,n）;//

（1）

cout<

（2）

fun541（a,2*i+2,n）;//（3）

}

}

intmain（）

{

charstr[64]="ABCDEFGH00I0JKL";

fun541（str,0,strlen（str））;

cout<

return0;

}

（1）程序执行后，输出结果是什么？

（2）若将函数fun541（）中的语句“cout<

（3）若将函数fun541（）中的语句“cout<

2．阅读下列程序，并回答问题。

#include

usingnamespacestd;

voidfun542（charBT[],intn）

{

inttop=0,s[50],i;//top是栈s的栈顶指针，栈容量足够大

i=0;

while（i0）

{

while（i

='#'）

{

cout<

if（2*i+2

s[++top]=2*i+2;

i=2*i+1;

}

if（top>0）i=s[top--];

}

}

intmain（）

{

charstr[64]="ABCD#EF#G##HI";

fun542（str,strlen（str））;

cout<

return0;

}

（1）程序执行后，输出结果是什么？

（2）简述函数voidfun542（charBT[],intn）的功能。

3．阅读下列程序，并回答问题。

BiTreefun543（BiTreebt1）

{

BiTreebt2;

if（bt1==NULL）

bt2=NULL;

else

{

bt2=newBiTNode（）;

bt2->data=bt1->data;

bt2->rchild=fun543（bt1->lchild）;

bt2->lchild=fun543（bt1->rchild）;

}

returnbt2;

}

（1）对于如图6所示的二叉树bt1，画出执行函数bt2=fun543（bt1）;后二叉树bt2的示意图。

图6某二叉树

（2）简述函数BiTreefun543（BiTreebt1）的功能。

4．阅读下列程序，并回答问题。

voidfun544（BiTreebt）

{

if（bt!

=NULL）

{

cout<data;

if（bt->lchild||bt->rchild）

{

cout<<"（";

fun544（bt->lchild）;

if（bt->rchild）cout<<"，";

fun544（bt->rchild）;

cout<<"）";

}

}

}

（1）对于如图6所示的二叉树bt，执行函数fun544（bt）;后的输出是什么？

（2）简述函数voidfun544（BiTreebt）的功能。

5．阅读下列程序，并回答问题。

voidfun545（BiTreebt）

{

BiTrees[100];//设栈s容量足够大

inttop=0;

BiTreep=bt;

if（p）

{

s[++top]=NULL;

while（p）

{

cout<data;

if（p->rchild）s[++top]=p->rchild;

if（p->lchild）

p=p->lchild;

else

p=s[top--];

}

}

}

（1）已知如图7所示的二叉树以二叉链表作存储结构，rt为指向根结点的指针。

写出执行函数调用fun545（rt）的输出结果。

图7一棵二叉树

（2）对图7所示的二叉树bt调用下面的函数fun545Ex（rt）后，输出结果为dbgeafhc。

请在划线处填上适当的内容，将函数fun545Ex补充完整。

voidfun545Ex（BiTreebt）

{

BiTrees[100],p;

inttop=0;

p=bt;

while（p!

=NULL||__________）//①

{

if（p!

=NULL）

{

s[__________]=p;//②

p=__________;//③

}

else

{

p=s[__________];//④

cout<data;

p=__________;//⑤

}

}

cout<

}

6．下面的两个函数分别采用栈和队列非递归地实现将二叉树bt中每一个结点的左右子树互换。

请在划线处填上适当的内容，将程序补充完整。

voidBinTreeRevolute_1（BiTree&bt）//采用栈非递归实现二叉树的镜像

{

BiTreer,p,stack[500];

inttop=0;

stack[top]=bt;

while（____________）//

（1）

{

p=stack[____________];//

（2）

if（p）

{

r=p->lchild;p->lchild=p->rchild;p->rchild=r;

stack[____________]=p->lchild;//（3）

stack[____________]=p->rchild;//（4）

}

}

}

voidBinTreeRevolute_2（BiTree&bt）//采用队列非递归实现二叉树的镜像

{

BiTreep,q,queue[1000];//设队列queue的容量足够大

in