第六章：树和二叉树复习题.pdfVIP

第六章：树和二叉树复习题

第六章：树和二叉树复习题

一、选择题

1、有一“遗传”关系，设x是y的父

亲，则x可以把它的属性遗传给y，

表示该遗传关系最适合的数据结构

是（）

A、向量

B、树

C、图

D、二叉树

2、树最适合用来表示（）

A、有序数据元素

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

C、无序数据元素

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

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

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开始连续编号，要求每个结点的编号大于

其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于

其右孩子的编号，则可采用（）次序的遍历实

现二叉树的结点编号。

A、先序

B、中序

C、后序

D、从根开始按层次遍历

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

A、3

B、4

C、5

D、10

6、在一棵有n个结点的二叉树中，若度为2的结点数为n2，度

为1的结点数为n1，度为0的结点数为n0，则数的最大高度为（），

其叶结点数为（）；树的最小高度为（），其叶结点数为（）；若采

用链表存储结构，则有（）个空链域。

A、n/2

B、[log2n]+1

C、log2n

D、n

E、n0+n1+n2

F、n1+n2

G、n2+1H、1I、n+1J、n1K、n2L、n1+1

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

A、n=m+h

B、h+m=2n

C、m=h-1

D、n=2h-1

8、设高度为h的二叉树中只有度为0和度为2的结点，则此类二

叉树中所包含的结点数至少为（），至多为（）。

A、2h

B、2h-1

C、2h-1

D、2h-1

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

数为0）

A、8

B、16

C、15

D、32

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

A、16

B、32

C、31

D、10

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

A、247

B、248

C、249

D、250

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

A、254

B、255

C、256

D、257

13、假定有一棵二叉树，双分支结点数为15，单分支结点数为

30，则叶子结点数为（）个。

A、15

B、16

C、17

D、47

16、用顺序存储的方法将完全二叉树中所有结点逐层存放在数组

R[1…n]中，结点R[i]若有左子树，则左子树是结点（）。

A、R[2i+1]

B、R[2i]

C、R[i/2]

D、R[2i-1]

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

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

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

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

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

18、任何一棵二叉树的叶结点在先序、中序和后序遍历中的相对

次序（）。

A、不发生改变

B、发生改变

C、不能