《数据结构》习题集：第6章_树和二叉树

选择题

1.有一“遗传”关系，设x是y的父亲，则x可以把它的属性遗传给y，表示该遗传关系最适合的数据结构是（ B   ）

A、向量            B、树              C、图                D、二叉树

2.树最适合用来表示（ B   ）

A、有序数据元素 

B、元素之间具有分支层次关系的数据 

C、无序数据元素 

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

3.树B 的层号表示为1a,2b,3d,3e,2c，对应于下面选择的（ C   ）

A、1a(2b(3d,3e),2c)  B、a(b(D,e),c)        C、a(b(d,e),c)         D、a(b,d(e),c)

4.对二叉树的结点从1 开始连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（ C   ）次序的遍历实现二叉树的结点编号。

A、先序           B、中序             C、后序              D、从根开始按层次遍历

5.按照二叉树的定义，具有3 个结点的二叉树有（C ）种。

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

6.在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为1的结点数为n1，度为0的结点数为n0，则树的最大高度为（ E   ），其叶结点数为（  H  ）；树的最小高度为（  B  ），其叶结点数为（  G ）；若采用链表存储结构，则有（  I  ）个空链域。

A、n/2             B、+1       C、log2n             D、n 

E、n0+n1+n2             F、n1+n2                     G、n2+1              H、1 

I、n+1             J、n1                         K、n2                        L、n1+1

7.对一棵满二叉树，m 个树叶，n 个结点，深度为h，则（ D   ）

A、n=m+h          B、h+m=2n          C、m=h-1            D、n=2h-1

8.设高度为h 的二叉树中只有度为0 和度为2 的结点，则此类二叉树中所包含的结点数至少为（ B   ），至多为（D    ）。

A、2h              B、2h-1             C、2h-1                      D、2h-1

9.在一棵二叉树上第5 层的结点数最多为（B）（假设根结点的层数为1）

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

10.深度为5 的二叉树至多有（ C   ）个结点。

A、16              B、32               C、31               D、10

11.一棵有124 个叶结点的完全二叉树，最多有（B ）个结点

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

12.含有129 个叶子结点的完全二叉树，最少有（  D  ）个结点

A、254             B、255              C、256              D、257

13.假定有一棵二叉树，双分支结点数为15，单分支结点数为30，则叶子结点数为（ B   ）个。

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

14.用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[1…n]中，结点R[i]若有左子树，则左子树是结点（ B ）。

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

15.在一棵非空二叉树的中序遍历序列中，根结点的右边（ A ）。

A、只有右子树上的所有结点              B、只有右子树上的部分结点 

C、只有左子树上的所有结点              D、只有左子树上的部分结点

16.任何一棵二叉树的叶结点在先序、中序和后序遍历中的相对次序（ A   ）。

A、不发生改变       B、发生改变        C、不能确定         D、以上都不对

17.设n、m为一棵树上的两个结点，在中序遍历时，n在m 前的条件是（  C  ）。

A、n在m右方        B、n是m祖先        C、n在m左方        D、n是m子孙

18.一棵完全二叉树按层次遍历的序列为ABCDEFGHI，则在先序遍历中结点E的直接前驱为（ D   ），后序遍历中结点B的直接后继是（ E   ）。

A、B               B、D               C、A                D、I 

E、F                  F、C

19.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（D    ）。

A、acbed            B、decab           C、deabc                D、cedba

20.若二叉树采用二叉链表作存储结构，要交换其所有分支结点左右子树的位置，利用（ C  ）遍历方法最合适。

A、前序            B、中序            C、后序              D、层次

21.线索二叉树是一种（  C  ）结构。

A、逻辑            B、逻辑和存储      C、物理              D、线性

22.如果T2 是由有序树T 转换而来的二叉树，那么T 中结点的前序就是T2 中结点的（  A  ）。

A、前序            B、中序            C、后序              D、层次序

23.设T是哈夫曼树，具有5个叶结点，树T 的高度最高可以是（ E   ）。

A、1               B、2               C、3                 D、4 

E、5               F、6

24.由带权为8，2，5，7 的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（   D ）。

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

25.树的后根遍历序列等同于该树对应的二叉树的（   B  ）。

A、先序遍历        B、中序遍历        C、后序遍历          D、层次遍历

26.以下说法错误的是（  A  ）。

A、树形结构的特点是一个结点可以有多个直接前趋

B、线性结构中的一个结点至多只有一个直接后继

C、二叉树与树是两种不同的数据结构

D、树(及一切树形结构)是一种“分支层次”结构

27.以下说法错误的是（ C  ）。

A、二叉树可以是空集                    B、二叉树的任一结点都有两棵子树

C、二叉树与树具有相同的树形结构        D、二叉树中任一结点的两棵子树有次序之分

28.以下说法错误的是（  D  ）。

A、完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达

B、在三叉链表上，二叉树的求双亲运算很容易实现

C、在二叉链表上，求根，求左、右孩子等很容易实现

D、在二叉链表上，求双亲运算的时间性能很好

29.以下说法错误的是（D  ）。

A、一般在哈夫曼树中，权值越大的叶子离根结点越近

B、哈夫曼树中没有度数为1 的分支结点

C、若初始森林有n 棵二叉树，最终求得的哈夫曼树共有2n-1 个结点

D、若初始森林有n 棵二叉树，进行2n-1 次合并后才能剩下一棵最终的哈夫曼树

30.将含有41个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为21 的双亲结点编号为（ A   ）。

A 、10             B、 11              C、 41              D、 20

31.任何一棵二叉树的叶结点在其先根、中根、后根遍历序列中的相对位置（ C   ）。

A、肯定发生变化    B、有时发生变化     C、肯定不发生变化   D、无法确定

32.下列说法正确的是（ A  ）。

A、树的先根遍历序列与其对应的二叉树的前序遍历序列相同

B、树的先根遍历序列与其对应的二叉树的后序遍历序列相同

C、树的后根遍历序列与其对应的二叉树的前序遍历序列相同

D、树的后根遍历序列与其对应的二叉树的后序遍历序列相同

33.下列说法中正确的是（ D ）。

A、任何一棵二叉树中至少有一个结点的度为2

B、任何一棵二叉树中每个结点的度都为2

C、任何一棵二叉树中的每个结点的度肯定等于2

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

34.一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用（B ）遍历方式就可以得到这棵二叉树所有结点的递减序列。

A、前序            B、中序             C、后序             D、层次

35.对含有（  B  ）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。

A 、0              B、 1               C 、2               D、不存在这样的二叉树

36.在图6.2 中的二叉树中，（ C ）不是完全二叉树。

37.哈夫曼树的带权路径长度是（ B   ）。

A、所有结点权值之和                    B、所有叶结点带权路径长度之和

C、带权结点的值                        D、除根以外所有结点权值之和

38.在线索二叉树上，线索是（ B  ）。

A、两个标志域                          B、指向结点前驱和后继的指针

C、数据域                              D、指向左、右子树的指针

39.已给出如图6.3 所示哈夫曼树，那么电文CDAA 的编码是(  B )。

A、110100          B、11011100         C、010110111        D、11111100

40.已给出的图6.3 所示二叉树，A,B,C,D 分别带权值为7，5，2，4 则该树的带权路径长度为（ C ）。

A、46              B、36               C、35               D、都不是

41.在线索化二叉树中，t 所指结点没有左子树的充要条件是（ B ）。

A、t->lchild==NULL B、t->ltag==1

C、t->ltag==1&&t->lchild==NULL D、以上都不对

42.下列叙述中正确的是（ D   ）。

A、二叉树是度为2 的有序树               B、二叉树中结点只有一个孩子时无左右之分

C、二叉树中必有度为2 的结点             D、二叉树中结点最多有两棵子树，并且有左右之分

43.下图6.4 所示的几种结构中属于树型结构的是（  B  ）。

、

判断题

1.二叉树是树的特殊形式。X

2.树和二叉树之间最主要的差别是：二叉树的结点的子树要区分为左右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。 V

3.一棵有n 个结点的d 度树，若用多重链表表示，树中每个结点都是有d 个链域，则在树的n*d 个链域中，有n*(d-1)+1 个是空链域，只有n-1 个是非空的。V

4.前序遍历树和前序遍历与该树对应的二叉树，其结果相同。V

5.后序遍历树和中序遍历与该树对应的二叉树，其结果不同。X

6.前序遍历森林和前序遍历与该森林对应的二叉树，其结果相同。X

7.中序遍历森林和中序遍历与该森林对应的二叉树，其结果不同。V

8.若有一个结点是某二叉树子树的中序遍历序列中最后一个结点，则它必须是该子树的前序遍历序列中的最后一个结点。X

9.二叉树具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女。V

10.在二叉树中，具有一个子女的父结点，在中序遍历中，它没有后继的子女结点。X

11.中序线索二叉树的优点之一是便于在中序下查找前驱结点和后继结点。V

12.在二叉树中插入结点，该二叉树便不在是二叉树。X

13.用一维数组存储二叉树时，总是以前序遍历存储结点。X

14.已知二叉树的前序遍历和后序遍历序列不能唯一地确定这棵树。V

15.不使用递归，也可以实现二叉树的前序，中序，后序遍历。V

16.在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点之后。V

17.在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应做特殊处理。X

填空题

1.在树型结构中，树根结点没有（ 双亲     ）结点，其余每个结点有且只有（ 1     ）个前驱结点；叶子结点没有（ 子     ）结点，其余每个结点的后继结点可以（  是结点或叶子     ）。

2.假定一棵树的广义表表示为A（B（E），C（F（H，I，J），G），D），则该树的度为（  3    ），树的深度为（ 4     ），终端结点的个数为（   6 ），单分支结点的个数为（  1  ），双分支结点的个数为（   1  ），三分支结点的个数为（  2  ），C的双亲结点为（  A  ），其孩子结点为（  F,G    ）。

3.设树T 中除叶结点外，任意结点的度数都是3，则T的第I层结点的个数为（  3^i-1    ）。

4.在具有n(n>=1)个结点的k叉树中，有（  (n-1)*k+1   ）个空指针。

5.一棵含有n个结点的k叉树，可能达到的最大深度为（   n  ），最小深度为（   2   ）。

6.一棵深度为k的满二叉树的结点总数为（ 2^k -1），一棵深度为k的完全二叉树的结点总数的最小值为（ 2^k-1），从左到右次序给结点编号（从1开始）则编号最小的叶子结点的编号是（      ），最大值为（      ）。

7.设根结点的层次数为0，定义树的高度为树中层次最大的结点的层次加1，则高度为k的二叉树具有的结点数目，最少为（   2^k-1   ），最多为（  2^k -1    ）。

8.n个结点的完全二叉树，若按从上到下、从左到右给结点顺序编号，则编号最大的非叶结点编号为（  n/2    ），编号最小的叶结点编号为（  n/2 +1    ）。

9.在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则n0=（ n2+1     ）。

10.一棵二叉树的第I层最多有（2i-1 ）个结点，一棵有n个结点的满二叉树共有（ (n+1)/2 ）个叶子结点和（  (n+1)/2-1    ）个非终端结点。

11.一棵完全二叉树的第5层有5个结点，则共有（ 20     ）个结点，其中度为1的结点有（ 1 ）个，度为0的结点有（ 10  ）个。

12.具有n 个结点的完全二叉树，其叶子结点的个数为（ (n+1)/2     ）。

13.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为（  2n    ）个，其中（ n-1    ）个用于链接孩子结点，（ n+1     ）个空闲。

14.对于一棵具有n 个结点的二叉树，当它为一棵（ 完全 ）二叉树时具有最小高度，高度为（  log2(n+1)    ），当它为一棵单支树时具有（最大 ）高度，高度为（  n    ）。

15.树所对应的二叉树其根结点的（  右  ）子树一定为空。

16.从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是（ 方便编程中的调用 ）。

17.一棵完全二叉树按层次遍历的序列为ABCDEFGHI，则在先序遍历中结点E的直接前驱为（  I  ），后序遍历中结点B的直接后继为（  F  ）。

18.某二叉树的中序遍历序列为ABCDEFG，后序序列为BDCAFGE，则该二叉树结点的前序序列为（  EACBDGF  ），该二叉树对应的森林包括（   2 ）棵树。

19.在一棵二叉排序树上按（ 中序 ）遍历得到的结点序列为有序序列。

20.由n个权值构成的哈夫曼树共有（ 2n-1     ）个结点。

21.由带权为3，9，6，2，5 的5 个叶子结点构成一棵哈夫曼树，则带权路径长度为（  55 ）。

22.设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有（n+1  ）个。

附加判断题

1.树中任意结点的子树不必是有序的。（  X  ）

2.树可以看成特殊的的无向图。（  X  ）

3.可以使用双链表表示树形结构。（  V  ）

4.顺序存储方式只能用于存储线性结构。（ X ）

5.完全二叉树的某结点若无左孩子，则必为叶结点。（ V   ）

6.如果一个二叉树的结点，或者没有子树，或者恰有两棵非空子树，则此二叉树称为完全二叉树。（  X  ）

7.包含两个结点的所有二叉树都是相同的。（  X  ）

8.二叉树的前序遍历序列中，任意一个结点均处在其子树结点的前面。（  V  ）

9.二叉树的前序和后序遍历能唯一确定一棵二叉树。（ X）

10.二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索。（ X   ）

11.中序线索二叉树中，右线索若不为空，则一定指向其父结点。（ X ）

简答题

1.分别画出含3个结点的树与二叉树的所有不同形态。

    三结点:

  A          A

 / \\       |    

B   C      B

           |

           C

二叉树:

  A         A       A       A        A

 / \\       /       /         \\        \

B   C     B       B           B        B

         /         \\         /          \

        C           C       C            C

2.

3.设在树中，结点x是结点y的双亲时，用(x,y) 来表示边。已知一棵树边的集合为：{(i,j),(i,k),(b,e),(e,i),(b,d),(a,b),(c,g),(c,f),(c,h),(a,c)}，用树形表示法画出此树，并回答下列问题：

1)哪个是根结点？

a

2)哪些是叶子结点？

k,j,d,g,f,h

3)哪个是g的双亲？

c

4)哪些是g的祖先？

c,a

5)哪些是e的子孙？

i,k,j

6)哪些是f的兄弟？

g,h

7)结点b和j的层次各是多少？

2,5

8)树的深度是多少？

5

9)树的度数是多少？

3

4.任意一个有n(n>0)个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点有m-1个度为2，其余度为1。

5.分别画出图6.6 所示二叉树的二叉链表、三叉链表和顺序存储结构。

6.分别写出图6.7 所示二叉树的前序、中序和后序序列

前序:

ABCDEF

中序:

CBEFDA

后续:

CFEDBA

7.试分别画出图6.8所示树的孩子链表、孩子兄弟链表和静态双亲链表。

8.将图6.9所示的森林转换成二叉树。

9.分别画出图6.10所示各二叉树对应的森林。并写出森林的前序和中序遍历序列。

10.设某密码电文由8个字母组成，每个字母在电文中的出现频率分别是7，19，2，6，32，3，21，10，试为这8个字母设计相应的哈夫曼编码。

    7:1110;

    19:00;

    2:11010;

    6:1100;

    32:10;

    3:11011;

    21:01;

    10:1111

11.将代数式：y=3*(x+a)-a/x2 描述成表达式树，并写出前缀式和后缀式来。

12.下述编码{00，01，10，11}，{0，1，00，11，}，{0，10，110，111}哪一组不是前缀码？

{0，1，00，11，} 不是前缀码