第5章树与二叉树

满分分数:100.0

时间限制:60（分钟）

试题数量:50

截止时间:2023-11-14 21:49

一、单项选择题

1、对于任意一棵高度为5且有10个结点的二叉树，若采用顺序存储结构保存，每个结点占1个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存储单元数量至少是（）。 (2.0分)

A、31

B、16

C、15

D、10

答案:B

解析:--

2、二叉树是非线性数据结构，（）。 (2.0分)

A、它不能用顺序存储结构存储

B、它不能用链式存储结构存储

C、顺序存储结构和链式存储结构都不能使用

D、顺序存储结构和链式存储结构都能存储

答案:D

解析:--

3、若一棵完全二叉树有768个结点，则该二叉树中叶子结点的个数是（）。 (2.0分)

A、257

B、258

C、384

D、385

答案:C

解析:--

4、树的路径长度是从树根到每个结点的路径长度的（）。 (2.0分)

A、总和

B、最小值

C、最大值

D、平均值

答案:A

解析:--

5、下述编码中（）不是前缀编码。 (2.0分)

A、（00，01，10，11）

B、（0，1，00，11）

C、（0，10，110，111）

D、（1，01，000，001）

答案:B

解析:--

6、要使一棵非空二叉树的先序序列与中序序列相同，其所有非叶子结点须满足的条件是（）。 (2.0分)

A、只有左子树

B、只有右子树

C、结点的度均为1

D、结点的度均为2

答案:B

解析:--

7、一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有（）个结点。 (2.0分)

A、h+1

B、2h

C、2h-1

D、2h+1

答案:C

解析:--

8、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。 (2.0分)

A、250

B、254

C、501

D、500

答案:C

解析:--

9、已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（）。 (2.0分)

A、39

B、52

C、111

D、119

答案:C

解析:--

10、已知一棵有2011个结点的树，其叶子结点个数是116，该树对应的二叉树中无右孩子的结点个数是（）。 (2.0分)

A、115

B、116

C、1895

D、1896

答案:D

解析:--

11、在任何一棵二叉树中，若结点a有左孩子b、右孩子c，则在结点的先序序列，中序序列、后序序列中，（）。 (2.0分)

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

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

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

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

答案:C

解析:--

12、在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是（）。 (2.0分)

A、41

B、82

C、113

D、122

答案:B

解析:--

13、3个结点可构成（）个不同形态的二叉树。 (2.0分)

A、2

B、3

C、4

D、5

答案:D

解析:--

14、对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一双亲的左、右孩子中，左孩子的编号小于右孩子的编号，则可采用（）顺序实现编号。 (2.0分)

A、前序遍历

B、中序遍历

C、后序遍历

D、层序遍历

答案:C

解析:--

15、对任何一棵二叉树T，如果其终端结点的个数为n0，度为2的结点个数为n2，则（）。 (2.0分)

A、 n0=n2-1

B、n0=n2

C、n0=n2+1

D、没有规律

答案:C

解析:--

16、对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次为 h，则其左分支下的子孙的最大层次为（）。 (2.0分)

A、h

B、h+1

C、h或h+1

D、任意

答案:C

解析:--

17、二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。 (2.0分)

A、空或只有一个结点

B、高度等于其结点数

C、任一结点无左孩子

D、任一结点无右孩子

答案:B

解析:--

18、二叉树上叶结点数等于（）。 (2.0分)

A、分支结点数加1

B、单分支结点数加1

C、双分支结点数加1

D、双分支结点数减1

答案:C

解析:--

19、假定一棵度为3的树中结点数为50，则其最小高度应为()。 (2.0分)

A、3

B、4

C、5

D、6

答案:C

解析:--

20、具有256个结点的完全二叉树的深度为( )。 (2.0分)

A、6

B、7

C、8

D、9

答案:D

解析:--

21、前序遍历和中序遍历结果相同的二叉树是（）。 (2.0分)

A、根结点无左孩子的二叉树

B、根结点无右孩子的二叉树

C、所有结点只有左子树的二叉树

D、所有结点只有右子树的二叉树

答案:D

解析:--

22、任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（）。 (2.0分)

A、肯定不发生改变

B、肯定发生改变 

C、不能确定

D、有时发生变化

答案:A

解析:--

23、如果T'是由有序树T转换而来的二叉树，T中结点的后序序列就是 T'中结点的（）序列。 (2.0分)

A、前序

B、中序

C、后序

D、层序

答案:B

解析:--

24、如果结点A有3个兄弟，B是A的双亲，则结点B的度是（）。 (2.0分)

A、1

B、2

C、3

D、4

答案:D

解析:--

25、若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。 (2.0分)

A、前序

B、中序

C、后序

D、按层次

答案:C

解析:--

26、设二叉树有n个结点，则其深度为（）。 (2.0分)

A、n-1

B、n

C、n+1

D、不能确定

答案:D

解析:--

27、设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。 (2.0分)

A、M1

B、M1+M2

C、M3

D、M2+M3

答案:D

解析:--

28、深度为5的二叉树至多有（）个结点。 (2.0分)

A、16

B、32

C、31

D、10

答案:C

解析:--

29、深度为k的完全二叉树至少有（）个结点， (2.0分)

A、2^(k-2)+1

B、2^(k-1)

C、2^k-1

D、2^(k-1)-1

答案:B

解析:--

30、树最适合用来表示（）。 (2.0分)

A、有序数据元素

B、无序数据元素

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

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

答案:C

解析:--

31、讨论树、森林和二叉树的关系，目的是为了（）。 (2.0分)

A、借助二叉树上的运算方法去实现对树的一些运算

B、将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题

C、将树、森林转换成二叉树

D、体现一种技巧，没有什么实际意义

答案:B

解析:--

32、下列陈述中正确的是( )。 (2.0分)

A、二叉树是度为2的有序树

B、二叉树中结点只有一个孩子时无左右之分

C、二叉树中必有度为2的结点

D、二叉树中最多只有两棵子树，并且有左右之分

答案:D

解析:--

33、下面的说法中正确的是（） (1) 任何一棵二叉树的叶结点在三种遍历中的相对次序不变;(2) 按二叉树定义,具有三个结点的二叉树共有6种; (2.0分)

A、(1),(2)

B、(1)

C、(2)

D、(1),(2) 都错

答案:B

解析:--

34、一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有（)成立。 (2.0分)

A、 n=h+m

B、h+m=2n

C、m=h-1

D、n=2m-1

答案:D

解析:--

35、一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有（）个结点。 (2.0分)

A、2h

B、2h-1

C、2h+1

D、h+1

答案:B

解析:--

36、一棵满二叉树中共有n个结点，其中有m个叶子结点，深度为h，则（）。 (2.0分)

A、n=h+m

B、 h+m=2n

C、m=h-1

D、 n=2^h-1

答案:D

解析:--

37、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。 (2.0分)

A、250

B、500

C、254

D、501

答案:D

解析:--

38、已知二叉树的前序序列为ABDCEFG，中序序列为DBCAFEG，则后序序列为 ( )。 (2.0分)

A、DCBAFGE

B、DCBFGEA

C、DCBFEGA

D、DCBGFEA

答案:B

解析:--

39、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（）。 (2.0分)

A、acbed

B、decab

C、deabc

D、cedba

答案:D

解析:--

40、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。则该树中有（）个叶子结点。 (2.0分)

A、12

B、13

C、14

D、15

答案:A

解析:--

41、已知一棵二叉树的先序序列和中序序列相反，则该二叉树一定满足（）。 (2.0分)

A、左子树为空

B、其中任一结点无左孩子

C、右子树为空

D、其中任一结点无右孩子

答案:D

解析:--

42、用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组A[1]~A[n]中，结点A[i]若有左子树，则左子树的根结点是（）。 (2.0分)

A、A[2i-1]

B、 A[2i+1]

C、A[i/2]

D、A[2i]

答案:D

解析:--

43、由权值分别为1，7，6，9，5，3的叶子结点生成一棵哈夫曼树，它的带权路径长度为 (2.0分)

A、42

B、49

C、75

D、56

答案:C

解析:--

44、有n个叶子的哈夫曼树的结点总数为（）。 (2.0分)

A、不确定

B、2n

C、2n+1

D、2n-1

答案:D

解析:--

45、有三个数字1,2,3,将它们构成二叉树，中序遍历序列为1,2,3的不同二叉树有( )种。 (2.0分)

A、5

B、6

C、7

D、8

答案:A

解析:--

46、在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（）。 (2.0分)

A、线性表

B、栈

C、队列

D、有序表

答案:C

解析:--

47、在具有n个结点的二叉链表中，（）个指针域则是空的。 (2.0分)

A、n-1

B、n+1

C、n

D、n+2

答案:B

解析:--

48、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为 ( )。 (2.0分)

A、4

B、5

C、6

D、7

答案:C

解析:--

49、在一棵二叉树中，第4层上的结点数最多为（）。 (2.0分)

A、31

B、8

C、15

D、16

答案:B

解析:--

50、在一棵完全二叉树中，假定树根结点的编号为1，若编号为i的结点存在左孩子，则左孩子结点的编号为 (2.0分)

A、2i

B、2i -1

C、2i +1

D、2i +2

答案:A

解析:--

一、单项选择题

1、对于任意一棵高度为5且有10个结点的二叉树，若采用顺序存储结构保存，每个结点占1个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存储单元数量至少是（ ）。 (2.0分)

2、二叉树是非线性数据结构， （ ）。 (2.0分)

3、若一棵完全二叉树有768个结点，则该二叉树中叶子结点的个数是（ ）。 (2.0分)

4、树的路径长度是从树根到每个结点的路径长度的（ ）。 (2.0分)

5、下述编码中（ ）不是前缀编码。 (2.0分)

6、要使一棵非空二叉树的先序序列与中序序列相同，其所有非叶子结点须满足的条件是（ ）。 (2.0分)

7、一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有（ ）个结点。 (2.0分)

8、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。 (2.0分)

9、已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（ ）。 (2.0分)

10、已知一棵有2011个结点的树，其叶子结点个数是116，该树对应的二叉树中无右孩子的结点个数是（ ）。 (2.0分)

11、在任何一棵二叉树中，若结点a有左孩子b、右孩子c，则在结点的先序序列，中序序列、后序序列中，（ ）。 (2.0分)

12、在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是（ ）。 (2.0分)

13、3个结点可构成（）个不同形态的二叉树。 (2.0分)

14、对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一双亲的左、右孩子中，左孩子的编号小于右孩子的编号，则可采用（ ） 顺序实现编号。 (2.0分)

15、对任何一棵二叉树T，如果其终端结点的个数为n0，度为2的结点个数为n2，则（ ）。 (2.0分)

16、对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次为 h，则其左分支下的子孙的最大层次为（ ）。 (2.0分)

17、二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。 (2.0分)

18、二叉树上叶结点数等于（ ）。 (2.0分)

19、假定一棵度为3的树中结点数为50，则其最小高度应为()。 (2.0分)

20、具有256个结点的完全二叉树的深度为( )。 (2.0分)

21、前序遍历和中序遍历结果相同的二叉树是（ ）。 (2.0分)

22、任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（ ）。 (2.0分)

23、如果T'是由有序树T转换而来的二叉树，T中结点的后序序列就是 T'中结点的（ ）序列。 (2.0分)

24、如果结点A有3个兄弟，B是A的双亲，则结点B的度是（）。 (2.0分)

25、若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。 (2.0分)

26、设二叉树有n个结点，则其深度为（ ）。 (2.0分)

27、设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。 (2.0分)

28、深度为5的二叉树至多有（ ）个结点。 (2.0分)

29、深度为k的完全二叉树至少有（ ）个结点， (2.0分)

30、树最适合用来表示（ ）。 (2.0分)

31、讨论树、森林和二叉树的关系，目的是为了（ ）。 (2.0分)

32、下列陈述中正确的是( )。 (2.0分)

33、下面的说法中正确的是（ ） (1) 任何一棵二叉树的叶结点在三种遍历中的相对次序不变;(2) 按二叉树定义,具有三个结点的二叉树共有6种; (2.0分)

34、一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有（)成立。 (2.0分)

35、一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有（ ）个结点。 (2.0分)

36、一棵满二叉树中共有n个结点，其中有m个叶子结点，深度为h，则（ ）。 (2.0分)

37、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。 (2.0分)

38、已知二叉树的前序序列为ABDCEFG，中序序列为DBCAFEG，则后序序列为 ( )。 (2.0分)

39、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（）。 (2.0分)

40、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。则该树中有（ ）个叶子结点。 (2.0分)

41、已知一棵二叉树的先序序列和中序序列相反，则该二叉树一定满足（）。 (2.0分)

42、用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组A[1]~A[n]中，结点A[i]若有左子树，则左子树的根结点是（ ）。 (2.0分)

43、由权值分别为1，7，6，9，5，3的叶子结点生成一棵哈夫曼树，它的带权路径长度为 (2.0分)

44、有n个叶子的哈夫曼树的结点总数为（ ）。 (2.0分)

45、有三个数字1,2,3,将它们构成二叉树，中序遍历序列为1,2,3的不同二叉树有( )种。 (2.0分)

46、在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（）。 (2.0分)

47、在具有n个结点的二叉链表中，（ ）个指针域则是空的。 (2.0分)

48、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为 ( )。 (2.0分)

49、在一棵二叉树中，第4层上的结点数最多为（ ）。 (2.0分)

50、在一棵完全二叉树中，假定树根结点的编号为1，若编号为i的结点存在左孩子，则左孩子结点的编号为 (2.0分)

1、对于任意一棵高度为5且有10个结点的二叉树，若采用顺序存储结构保存，每个结点占1个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存储单元数量至少是（）。 (2.0分)

2、二叉树是非线性数据结构，（）。 (2.0分)

3、若一棵完全二叉树有768个结点，则该二叉树中叶子结点的个数是（）。 (2.0分)

4、树的路径长度是从树根到每个结点的路径长度的（）。 (2.0分)

5、下述编码中（）不是前缀编码。 (2.0分)

6、要使一棵非空二叉树的先序序列与中序序列相同，其所有非叶子结点须满足的条件是（）。 (2.0分)

7、一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有（）个结点。 (2.0分)

8、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。 (2.0分)

9、已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（）。 (2.0分)

10、已知一棵有2011个结点的树，其叶子结点个数是116，该树对应的二叉树中无右孩子的结点个数是（）。 (2.0分)

11、在任何一棵二叉树中，若结点a有左孩子b、右孩子c，则在结点的先序序列，中序序列、后序序列中，（）。 (2.0分)

12、在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是（）。 (2.0分)

14、对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一双亲的左、右孩子中，左孩子的编号小于右孩子的编号，则可采用（）顺序实现编号。 (2.0分)

15、对任何一棵二叉树T，如果其终端结点的个数为n0，度为2的结点个数为n2，则（）。 (2.0分)

16、对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次为 h，则其左分支下的子孙的最大层次为（）。 (2.0分)

17、二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。 (2.0分)

18、二叉树上叶结点数等于（）。 (2.0分)

21、前序遍历和中序遍历结果相同的二叉树是（）。 (2.0分)

22、任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（）。 (2.0分)

23、如果T'是由有序树T转换而来的二叉树，T中结点的后序序列就是 T'中结点的（）序列。 (2.0分)

26、设二叉树有n个结点，则其深度为（）。 (2.0分)

27、设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。 (2.0分)

28、深度为5的二叉树至多有（）个结点。 (2.0分)

29、深度为k的完全二叉树至少有（）个结点， (2.0分)

30、树最适合用来表示（）。 (2.0分)

31、讨论树、森林和二叉树的关系，目的是为了（）。 (2.0分)

33、下面的说法中正确的是（） (1) 任何一棵二叉树的叶结点在三种遍历中的相对次序不变;(2) 按二叉树定义,具有三个结点的二叉树共有6种; (2.0分)

35、一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有（）个结点。 (2.0分)

36、一棵满二叉树中共有n个结点，其中有m个叶子结点，深度为h，则（）。 (2.0分)

37、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。 (2.0分)

40、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。则该树中有（）个叶子结点。 (2.0分)

42、用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组A[1]~A[n]中，结点A[i]若有左子树，则左子树的根结点是（）。 (2.0分)

44、有n个叶子的哈夫曼树的结点总数为（）。 (2.0分)

47、在具有n个结点的二叉链表中，（）个指针域则是空的。 (2.0分)

49、在一棵二叉树中，第4层上的结点数最多为（）。 (2.0分)