爱迪国际C++章节测试-树

*
1.单选题
如果树根算第1层,那么一棵n层的二叉树最多有( )个结点。
A. 2n −1
B. 2n
C. 2n +1
D. 2n+1
*
2.单选题
一棵二叉树的前序遍历序列是ABCDEFG,后序遍历序列是CBFEGDA,则根结点的左子树的结点个数可能是( )。
A. 2
B. 3
C. 4
D. 5
*
3.单选题
完全二叉树的顺序存储方案,是指将完全二叉树的结点从上至下、从左至右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置,则第
k号结点的父结点如果存在的话,应当存放在数组的( )号位置。
A 2k
B 2k+1
C k/2下取整
D (k+1)/2下取整
*
4.单选题
如果根结点的深度记为1,则一棵恰有2011个叶结点的二叉树的深度最少是( )。
A 10
B 11
C 12
D 13
*
5.单选题
如果一棵二叉树的中序遍历是 BAC,那么它的先序遍历不可能是( )。
A. ABC
B. CBA
C. ACB
D. BAC
*
6.单选题
已知一棵二叉树有10 个节点,则其中至多有( )个节点有 2 个子节点。
A. 4
B. 5
C. 6
D. 7
*
7.单选题
二叉树的( )第一个访问的节点是根节点。
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 以上都是
8.填空题
完善程序:*
(二叉查找树) 二叉查找树具有如下性质: 每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。试判断一棵树是否为二叉查找树。
输入的第一行包含一个整数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);
}
问题1:问题2:问题3:问题4:问题5:
*
9.单选题
前序遍历序列与中序遍历序列相同的二叉树为( )。
A. 根结点无左子树
B. 根结点无右子树
C. 只有根结点的二叉树或非叶子结点只有左子树的二叉树
D. 只有根结点的二叉树或非叶子结点只有右子树的二叉树
*
10.单选题
如果根的高度为 1,具有 61 个结点的完全二叉树的高度为( )。
A.5
B.6
C.7
D.8
*
11.填空题

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

*
12.单选题
一棵二叉树如右图所示,若采用顺序存储结构,即用一 维数组元素存储该二叉树中的结点(根结点的下标为 1, 若某结点的下标为i,则其左孩子位于下标 2i处、 右孩子位于下标(2i+1)处) ,则图中所有结点的最大下标为( ) 。
A.6
B.10
C.12
D.15
13.填空题
约定二叉树的根节点高度为 1。一棵结点数为 2016 的二叉树最少有()个叶子结点;一棵结点数为 2016 的二叉树最小的高度值是( )。
*
问题1:问题2:
*
14.单选题
根节点深度为 0,一棵深度为 h 的满 k(k>1)叉树,即除最后一层无任何子节点外,每一层上的所有结点都有
kk 个子结点的树,共有( )个结点。
A. (k ^h+1 −1)/(k−1)
B. k^ h−1
C. k ^h
D. k ^h−1 /(k−1)
*
15.单选题
假设一棵二叉树的后序遍历序列为DGJHEBIFCA,中序遍历序列为DBGEHJACIF,则其前序遍历序列为()。
A. ABCDEFGHIJ
B. ABDEGHJCFI
C. ABDEGJHCFI
D. ABDEGHJFIC
*
16.单选题
独根树的高度为 1,具有 61 个结点的完全二叉树的高度为( )。
A. 5
B. 6
C. 7
D. 8
*
17.单选题
如果一棵二叉树只有根结点,那么这棵二叉树高度为1。请问高度为5的完全二叉树有( )种不同形态?
A.16
B.15
C.17
D.32
*
18.单选题
一棵有 n 个结点的完全二叉树用数组进行存储与表示,已知根结点存储在数组的第 1 个位置。若存储在数组第 9 个位置的结点存在兄弟结点和两个子结点,则它的兄弟结点和右子结点的位置分别是( )。
A 8 、18
B 10、 18
C 8、 19
D 10、19
*
19.单选题
根节点的高度为1,一 棵拥有2023个节点的三叉树高度至少为()。
A 6
B 7
C 8
D 9
*
20.选题
假设有一组字符 {a,b,c,d,e,f}, 对应的频率分别为5%、9%、12%、13%、16%、45%。请问以下哪个选项是字符 a,b,c,d,e,f 分别对应的一组哈夫曼编码 ?
A 1111,1110,101,100,110,0
B 1010,1001,1000,011,010,00
C 000,001,010,011,10,11
D 1010,1011,110,111,00,01
*
21.单选题
给定一棵二叉树,其前序遍历结果为:ABDECFG, 中序遍历结果为:DEBACFG。请问这棵树的正确后序遍历结果是什么 ?
A EDBGFCA
B EDGBFCA
C DEBGFCA
D DBEGFCA
*
22.单选题
一棵具有5层的满二叉树中结点数为( )。
A. 31
B. 32
C. 33
D. 16
问卷星提供技术支持
举报