二叉树的历年真题

1、完全二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置，则第k号结点的父结点如果存在的话，应当存放在数组的（ ）号位置。

A. 2k

B. 2k+1

C. k/2下取整

D. (k+1)/2下取整

2、如果根的高度为 1,具有 61 个结点的完全二叉树的高度为( )。

A.5

B.6

C.7

D.8

3、如果树根算第1层，那么一棵n层的二叉树最多有（ ）个结点。

A. 2^n−1

B. 2^n

C. 2^n+1

D. 2^(n+1)

4、一棵结点数为 2015 的二叉树最多有___个叶子结点。

5、一棵二叉树如右图所示，若采用顺序存储结构，即用一 维数组元素存储该二叉树中的结点（根结点的下标为 1， 若某结点的下标为 i，则其左孩子位于下标 2i2i处、 右孩子位于下标**(2i**+1)处） ，则图中所有结点的最大下标为( ) 。

A.6

B.10

C.12

D.15

6、一棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为1,若某结点的下标为i ,则其左孩子位于下标2i处、右孩子位于下标22i**+**1处），则该数组的最大下标至少为( )。 A. 6

B. 10

C. 15

D. 12

7、已知一棵二叉树有10 个节点，则其中至多有（ ）个节点有 2 个子节点。

A. 4

B. 5

C. 6

D. 7

8、一棵具有5层的满二叉树中结点数为( )。

A. 31

B. 32

C. 33

D. 16

9、如果根结点的深度记为1，则一棵恰有2011个叶结点的二叉树的深度最少是（ ）。

A. 10

B. 11

C. 12

D. 13

10、约定二叉树的根节点高度为 1。一棵结点数为 2016 的二叉树最少有（）个叶子结点；一棵结点数为 2016 的二叉树最小的高度值是（ ）。(答案以空格分隔)

11、独根树的高度为 1,具有 61 个结点的完全二叉树的高度为( )。

A. 5

B. 6

C. 7

D. 8

12、如果一棵二叉树只有根结点，那么这棵二叉树高度为1。请问高度为5的完全二叉树有（ ）种不同形态?

A.16

B.15

C.17

D.32

13、如果一棵二叉树的中序遍历是 BAC，那么它的先序遍历不可能是( )。

A. ABC

B. CBA

C. ACB

D. BAC

14、一棵二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数可能是（ ）。

A. 2

B. 3

C. 4

D. 5

15、二叉树的（ ）第一个访问的节点是根节点。

A. 先序遍历

B. 中序遍历

C. 后序遍历

D. 以上都是

16、前序遍历序列与中序遍历序列相同的二叉树为( )。

A. 根结点无左子树

B. 根结点无右子树

C. 只有根结点的二叉树或非叶子结点只有左子树的二叉树

D. 只有根结点的二叉树或非叶子结点只有右子树的二叉树

17、假设一棵二叉树的后序遍历序列为DGJHEBIFCA,中序遍历序列为DBGEHJACIF,则其前序遍历序列为（）。

A. ABCDEFGHIJ

B. ABDEGHJCFI

C. ABDEGJHCFI

D. ABDEGHJFIC

18、完善程序： （二叉查找树） 二叉查找树具有如下性质： 每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。试判断一棵树是否为二叉查找树。 输入的第一行包含一个整数n，表示这棵树有n 个顶点， 编号分别为 1, 2, ⋯ ,n，其中编号为 1 的为根结点。之后的第 i 行有三个数value, left‾child, right‾child，分别表示该节点关键字的值、左子节点的编号、右子节点的编号；如果不存在左子节点或右子节点，则用 0 代替。输出 1 表示这棵树是二叉查找树，输出0 则表示不是。

#include <iostream> 
using namespace std; 
const int SIZE = 100;
const int INFINITE = 1000000;
struct node
{
	int left_child, right_child, value;
}; node a[SIZE];
int is_bst( int root, int lower_bound, int upper_bound )
{
	int cur;
	if ( root == 0 )
		return(1);
	cur = a[root].value;
	if ( (cur > lower_bound) && ( ① ) && (is_bst( a[root].left_child, lower_bound, cur ) == 1) && (is_bst( ②, ③, ④ ) == 1) )
		return(1);
	return(0);
}


int main()
{
	int i, n; cin >> n;
	for ( i = 1; i <= n; i++ )
		cin >> a[i].value >> a[i].left_child >> a[i].right_child;
	cout << is_bst( ⑤, -INFINITE, INFINITE ) << endl;
	return(0);
}

第一空：________ 第二空：________ 第三空：________ 第四空：________ 第五空：________

19、根节点的高度为1，一 棵拥有2023个节点的三叉树高度至少为（）。

• A 6
• B 7
• C 8
• D 9

20、给定一棵二叉树，其前序遍历结果为：ABDECFG, 中序遍历结果为：DEBACFG。请问这棵树的正确后序遍历结果是什么 ?

• A EDBGFCA
• B EDGBFCA
• C DEBGFCA
• D DBEGFCA