数据结构第二单元测验题目的参考答案.pdfVIP

数据结构第二单元测验题目的参考答案

数据结构第二单元测验答案

一、选择题

1.由3个结点可以构造出多少种不同的有向树()

A.2

B.3

C.4

D.5

2.由3个结点可以构造出多少种不同的二叉树(d)

A.2

B.3

C.4

D.5

3.二叉树的第I层上最多含有结点数为(c)

A.2I

B.2I-1-1

C.2I-1

D.2I-1

4.一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉

树最少有(b)结点

A.2h

B.2h-1

C.2h+1

D.h+1

除第一层外,每层最少2个结点

5.一棵树高为K的完全二叉树至少有(c)个结点

A.2k–1

B.2k-1–1

C.2k-1

D.2k

6.深度为6的二叉树最多有(c)个结点

A．64B.63C.32D.31

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

2，1，1则T中的叶子数为()

A.5

B.6

C.7

D.8

8.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则

度为0的结点个数是(c)

A.9

B.11

C.15

D.不确定

9.一棵完全二叉树上有1001个结点，其中叶子结点的个数是(e)

A.250

B.500

C.254

D.505E．以上答案都不对

10.对于有n个结点的二叉树,其高度为(d)

A.nlog2n

B.log2n

C.?log2n?|+1

D.不确定

11.将含有83个结点的完全二叉树从根结点开始编号，根为1号，

按从上到下.从左到右顺序结点编号，那么编号为41的双亲结点编号为

（）

A.42

B.40

C.21

D.20

12.一个二叉树按顺序方式存储在一个维数组中，如图

01234567891011121314

ABCDEFGHIJ

则结点E在二叉树的第（c）层。

A.1

B.2

C.3

D.4

13.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是

（b）的二叉树

A.空或只有一个结点

B.高度等于其结点数

C.任一结点无左孩子

D.任一结点无右孩子

14.任何一棵二叉树的叶结点在其先根.中根.后根遍历序列中的相

对位置(c)

A.肯定发生变化

B.有时发生变化

C.肯定不发生变化

D.无法确定

15.二叉树线索化后，仍不能有效求解的问题是（d）

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

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

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

D.后序线索二叉树中求后续后继

一共有两种情况:一个是先序线索中求先序前驱和后序线索求后序

后继

16.如果T2是由有序树T转化而来的二叉树，那么T中结点的前

序就是T2中结点的(a)

A.前序

B.中序

C.后序

D.层次序

17.设森林T中有4棵树，第一.二.三.四棵树的结点个数分别是

n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的右子树

上有(d)个结点。

A.n1-1

B.n1

C.n1+n2+n3

D.n2+n3+n4

18.设给定权值总数有n个,