数据结构——树习题.pdfVIP

数据结构——树习题--第1页

数据结构——树练习

注：“[]”为向上取整，“{}”为向下取整。

一、填空题

1、二叉树第i(i=1)层上至多有__2^(i-1)___个结点。

2、深度为k(k=1)的二叉树至多有___2^k-1__个结点。

3、具有n个结点的完全二叉树的深度为__log(n+1)____。

2

4、具有n个结点的二叉树中,一共有____2n___个指针域,其中只有

____n-1___个用来指向结点的左右孩子，其余的___n+1_____个指针

域为NULL。

5、若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，

则它必是该子树的后根遍历序列中的___第一个_____个结点。

6、在____先序____遍历二叉树的序列中，任何结点的子树上的所有

结点，都是直接跟在该结点之后。

7、具有n个结点的完全二叉树，若按层次从上到下、从左到右对其

编，号（根结点为1号），则编号最大的分支结点序号是____n/2____，

编号最小的分支结点序号是___1____，编号最大的叶子结点序号是

_____n__，编号最小的叶子结点序号是__n/2+1_____。

8、先根遍历树和先根遍历与该树对应的二叉树，其结果___相同____

（填“相同”或“不同”）。

9、由____一颗树___转换成二叉树时，其根结点的右子树总是空的。

10、若一棵二叉树的叶子数为n，则该二叉树中，左、右子树皆非空

的结点个数为___n-1____。

数据结构——树习题--第1页

数据结构——树习题--第2页

11、任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉

树上度数为1的结点为___n-2m+1___个。

12、现有按中序遍历二叉树的结果为ABC，问有____5__种不同形态

的二叉树可以得到这一遍历结果

13、已知一棵度为3的树有2个度为1的结点，3个度过为2的结点，

4个度为3的结点，则该树中有____12___个叶子结点。

二、单选题

1、1．以下说法错误的是

(1.)

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

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

③树形结构可以表达(组织)更复杂的数据

④树(及一切树形结构)是一种分支层次结构

⑤任何只含一个结点的集合是一棵树

2.以下说法错误的是

(4)

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

达

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

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

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

数据结构——树习题--第2页

数据结构——树习题--第3页

3、深度为6的二叉树最多有(2)个结点

()

①64②63③32④31

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

面按从上