资源简介

一．选择题（共30小题）
1．已知二叉树T节点的前序遍历序列为A﹣B﹣D﹣E﹣F﹣G﹣C，中序遍历序列是D﹣B﹣F﹣E﹣G﹣A﹣C，则其后序遍历序列是（　　）
A．F﹣D﹣G﹣E﹣B﹣C﹣A B．D﹣F﹣G﹣E﹣B﹣C﹣A
C．B﹣F﹣D﹣G﹣B﹣C﹣A D．C﹣G﹣F﹣E﹣D﹣B﹣A
2．数学表达式（7﹣5）*（1+2）可用二叉树表示，如图所示。则下列说法错误的是（　　）
A．该二叉树是满二叉树
B．该二叉树的高度为3
C．通过后序遍历可求出该表达式的逆波兰式为7512﹣+*
D．用列表方式存储该二叉树的具体结构为：浙考神墙750[’*’，[’﹣’，[7，None，None]，[5，None，None]]，[’+’，[1，None，None]，[2，None，None]]]
3．有二叉树用数组表示为：[“A”，“B”，“C”，None，“D”，“E”，“F”，None，None，None，“G”]，则下列关于该二叉树的说法 正确的是（　　）
A．该二叉树度为1的节点有2个
B．该二叉树一共有3层
C．该二叉树中的叶子节点有4个
D．该二叉树的中序遍历序列是B﹣G﹣D﹣A﹣E﹣C﹣F
4．用一维数组表示二叉树，如表所示：
0 1 2 3 4 5 6 7 8 9 10
A B C D E F G
下列有关该二叉树的说法正确的是（　　）
A．该树中共有 4 个叶子节点
B．该树是完全二叉树，其深度为4
C．该树的中序遍历为 B﹣F﹣D﹣G﹣A﹣C﹣E
D．该二叉树的结构图为（如图所示）
5．某二叉树前序遍历为ABDCE，后序遍历为DBECA，则该二叉树可能情况有多少种？（　　）
A．1 B．2 C．4 D．6
6．关于二叉树，下列说法正确的是（　　）
A．二叉树的度肯定为2
B．在含有n个节点的二叉树中，边数为n﹣1
C．二叉树的前序遍历序列与中序遍历序列肯定不同
D．在二叉树的前序序列中，若节点u在节点v之前，则u一定是v的祖先
7．有二叉树的前序遍历序列为A﹣B﹣C﹣E﹣F﹣G﹣D，中序遍历序列为A﹣E﹣C﹣F﹣G﹣B﹣D，则关于该二叉树的说法正确的是（　　）
A．该二叉树根节点的度为1
B．该二叉树的高度为4
C．该二叉树中节点G是节点C的左孩子
D．该二叉树中叶子节点的个数为4
8．对于如图所示的一义树，下列说法正确的是（　　）
A．树的高度是4，是一棵完全二叉树
B．度为2的节点数比叶子节点数多1
C．若采用数组存储法，需要6个存储空间
D．该二叉树的后序遍历序列是fdebca
9．下列二叉树中，中序遍历结果为BAEDFC的是（　　）
A． B．
C． D．
10．若一棵二叉树的中序遍历序列为BIGDHAECF，后序遍历序列为IGHDBEFCA，则该二叉树的前序遍历序列为（　　）
A．ABCDEFGHI B．ABDGHICEF C．ABDHGICEF D．ABDG IHCEF
11．现有一颗二叉树的前序遍历为ABCDEF，中序遍历为BCADFE，则该二叉树的后序遍历为（　　）
A．CBFEDA B．BCFEDA C．CBDFEA D．BCEFDA
12．某二叉树的后序遍历序列为F一？—？—C一A一D，中序遍历序列为F一B一D一E一A一C，则其前序遍历序列为（　　）
A．D一B一A一F一E—C B．D一B一F一A一E一C
C．D一E一F一A一B一C D．D一E一A一F一B一C
13．如果将数学表达式中的运算数和运算符视同为二叉树的每个节点，那么我们可以构造出各种表达式二叉树，如图所示的是一棵表达式二叉树。如果对该之叉树进行中序遍历，并加上括号后，就可以得到中缀表达式：（ 9﹣4/2）*5+3。如果对该二叉树实行前序遍历，则可以得到的表达式为（　　）
A．+*﹣9/4253 B．+*﹣/42953 C．942/﹣*53+ D．942/﹣5*3+
14．如图所示，有如下二叉树，关于此二叉树的说法中，描述正确的是（　　）
A．该二叉树的前序遍历为ABDGJCEFHI
B．该树中共有3个叶子节点
C．若有前序遍历和后序遍历可以推导出唯一的二叉树
D．该树的深度为4
15．一棵包含10个节点的完全二叉树，其叶子节点的个数为（　　）
A．3 B．4 C．5 D．6
16．已知二叉树中序遍历序列是BEDAFHCIG，前序遍历序列是ABDECFHGI，它的后序遍历序列是（　　）
A．BDEFHCIGA B．IGHFEDCBA C．EDBFHIGCA D．EDBHFIGCA
17．已知二叉树T2的后序遍历序列为G﹣D﹣H﹣E﹣B﹣I﹣F﹣C﹣A，中序遍历序列是D﹣G﹣B﹣E﹣H﹣A﹣C﹣I﹣F，则二叉树T2的前序遍历序列为（　　）
A．A﹣B﹣D﹣G﹣E﹣H﹣C﹣I﹣F
B．A﹣B﹣D﹣G﹣E﹣H﹣C﹣F﹣I
C．A﹣B﹣D﹣G﹣E﹣H﹣F﹣C﹣I
D．该二叉树形态不唯一，无法确定
18．已知一棵完全二叉树，其第 4 层有 3 个叶子节点，这棵二叉树的节点数量不可能是（　　）
A．25 B．24 C．11 D．10
19．已知一棵二叉树的前序遍历序列为：A﹣B﹣D﹣C﹣E，后序遍历序列为：D﹣B﹣E﹣C﹣A，则该二叉树是否能唯一确定？中序遍历序列是（　　）
A．能唯一确定，中序遍历序列为：B﹣D﹣A﹣E﹣C
B．不能唯一确定，中序遍历序列可能为：B﹣D﹣A﹣E﹣C
C．能唯一确定，中序遍历序列为：D﹣C﹣B﹣A﹣E
D．不能唯一确定，中序遍历序列可能为：D﹣C﹣B﹣A﹣E
20．如图所示的二叉树，其节点的中序遍历的序列为（　　）
A．ABCDEFG B．GDBEACF C．GDEBFCA D．ABDGECF
21．如图a 为一棵二叉树，其数组实现示意图（部分）如图b 所示。
下列说法正确的是（　　）
A．该二叉树的前序遍历为 ABCDEFG
B．该二叉树的高度为 3
C．该二叉树是完全二叉树
D．节点 G 存储在数组下标为 11 的位置
22．有一棵二叉树如图所示，该二叉树的后序遍历结果正确的是（　　）
A．XBCDAYEF B．FEYADCBX C．DBEAFXCY D．DEFABYCX
23．设一棵二叉树的中序遍历序列：becfad，后序遍历序列：efcbda，则二叉树前序遍历序列为（　　）
A．abcdef B．bdaefc C．abcefd D．abcfed
24．一棵具有124个叶子结点的完全二叉树，最多有（　　）个结点。
A．247 B．248 C．249 D．250
25．用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中，若结点R[i]有右孩子，则其右孩子是（　　）
A．R[2i﹣1] B．R[2i+1] C．R[2i] D．R[2/i]
26．设一棵二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树先序遍历序列为（　　）
A．adbce B．decab C．debac D．abcde
27．有一种元素除首元素没有前驱元素、尾元素没有后继元素外，其它元素都只有一个前驱元素和一个后继元素。具有以上特点的数据结构是（　　）
A．树结构 B．选择结构 C．线性结构 D．网状结构
28．在树形结构中，没有的是（　　）？
A．根的父节点 B．父节点 C．根 D．子树
29．VB语言中，下列各种基本数据类型说明符中表示整型数的是（　　）
A．Integer B．Boolean C．Single D．String
30．在VB中，要定义一个存储整型数值的变量，其合适的数据类型是（　　）
A．Boolean B．String C．Date D．Integer
参考答案与试题解析
一．选择题（共30小题）
1．【解答】解：二叉树的先序遍历中第一个为根节点，中序遍历中根节点位置的左右分别为左右子树，根据这个关系，我们可以还原出这个二叉树的结构，然后写出后序遍历为D﹣F﹣G﹣E﹣B﹣C﹣A。
故选：B。
2．【解答】解：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树，所以该二叉树为满二叉树；二叉树的高度是垂直方向上树的长度的量度，所以该二叉树的高度为3；通过后序遍历可求出该表达式的逆波兰式为75﹣12+*；用列表方式存储该二叉树的具体结构为：浙考神墙750[’*’，[’﹣’，[7，None，None]，[5，None，None]]，[’+’，[1，None，None]，[2，None，None]]]，所以选项C说法错误。
故选：C。
3．【解答】解：如果父节点的下标是i那么左子节点的下标i*2+1右子节点的下标的i*2+2，根据此规律可以画出该二叉树，得到该二叉树度为1的节点有2个，该二叉树一共有4层，该二叉树中的叶子节点有3个，该二叉树的中序遍历序列是D﹣B﹣A﹣E﹣G﹣F﹣C，所以选项A符合题意。
故选：A。
4．【解答】解：观察图形可知，中序遍历的规则是：左子树﹣﹣﹣＞根结点﹣﹣﹣＞右子树所以该树的中序遍历为 B﹣F﹣D﹣G﹣A﹣C﹣E，选项C说法正确。
故选：C。
5．【解答】解：根据该二叉树的前序遍历为ABDCE，后序遍历为DBECA，可知根节点为A，画图可得二叉树可能情况有4种。
故选：C。
6．【解答】解：二叉树每个结点最多两个孩子，即结点的度最大为2，但也可能所有结点的度都不为2，如只有1个结点，或单枝树等，所以二叉树的度并不一定是2；在含有n个节点的二叉树中，边数为n﹣1；二叉树的前序遍历序列与中序遍历序列有可能相同。
故选：B。
7．【解答】解：根据前序和中序遍历可知，该二叉树的根节点为A，根节点没有左子树，只有右子树，所以根节点的度为1，所以选项A说法正确。
故选：A。
8．【解答】解：二叉树的高度是二叉树结点层次的最大值，也就是其左右子树的最大高度+1。树的高度是4，是一棵不完全二叉树；后序遍历就是左子树﹣﹣﹣＞右子树﹣﹣﹣＞根结点，所以该二叉树的后序遍历序列是fdebca；所以选项D说法正确。
故选：D。
9．【解答】二叉树的中序遍历顺序为左子树﹣＞根﹣＞右子树，题目中四个二叉树遍历的结果：A：EDFBAC，B：BEDFAC，C：BAEDFC，D：BACEDF。
故选：C。
10．【解答】后序遍历为IGHDBEFCA可以得到根节点为A；中序遍历可知左子树为BIGDH，右子树为ECF，依次类推可以得到该二叉树的前序遍历为ABDG IHCEF。
故选：D。
11．【解答】有先序遍历可得根节点为A，有中序遍历可知左半部分的遍历为BC，结合先序遍历可得后序遍历为CB，在观察左子树中先序和中序得到其后序遍历为EFD，所以该二叉树的后序遍历为CBEFDA。
故选：A。
12．【解答】题干提供了后序遍历可以得到根节点，在通过中序遍历得到FB为左子树，ACE为右子树，结合中序和后序遍历可知，左子树中B为根节点，右子树中，A为根节点，E为左节点由此可以得到前序遍历为D一B一F一A一E一C。
故选：B。
13．【解答】如图所示，前序遍历的顺序为根节点，左节点然后是右节点，所以该二叉树的前序遍历为：+*﹣9/4253。
故选：A。
14．【解答】如图所示该二叉树的前序遍历为ABDGJCEFHI；该树中共有4个叶子节点；给定先序和中序 或者给定 后序加中序 可以唯一确定一颗二叉树二叉树；从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度，所以该二叉树深度为5.
故选：A。
15．【解答】一棵包含10个节点的完全二叉树，其叶子节点的个数为10/2＝5.故选：C。
16．【解答】根据二叉树的前序与中序，可画出二叉树如下图，再写出后序遍历序列是 EDBHFIGCA。
故选：D。
17．【解答】由后序遍历可知根节点为A，由中序遍历可知左子树为D﹣G﹣B﹣E﹣H，右子树为C﹣I﹣F。所以前序遍历为A﹣B﹣D﹣G﹣E﹣H﹣C﹣F﹣I。
故选：B。
18．【解答】完全二叉树除了最后一层，是一棵满二叉树，其节点数为2^k﹣1，k是层数，所以为2^3﹣1＝7，然后加上第四层最少3个叶子为7+3＝10，故最少给10个节点，由于是完成二叉树，每增加一个根节点则下面增加两个子节点，所以不可能是11个节点。
故选：C。
19．【解答】已知一棵二叉树的前序遍历序列为：A﹣B﹣D﹣C﹣E可以确定根节点为A，已知后序遍历序列为：D﹣B﹣E﹣C﹣A可以确定左子树的起点为B，无法确定左子树到哪里结束，同样无法确定右子树的开始节点。所以无法确定唯一性，中序遍历序列可能为：B﹣D﹣A﹣E﹣C故选项B符合题意。
故选：B。
20．【解答】中序遍历（中根）是先遍历左子树，再访问当前节点，最后是右子树。按照这个规则遍历序列是GDBEACF。故选B。
21．【解答】该二叉树的前序遍历为 ABDCEGF；该二叉树的高度为 4；该二叉树是不完全二叉树；节点 G 存储在数组下标为 11 的位置。
故选：D。
22．【解答】根据后序遍历的定义及方法可以该二叉树后序遍历为：DEFABYCX。故选：D。
23．【解答】根据后序可以确定根为a，那么结合中序遍历的顺序becf为左子树，d为右子树。那么可以确定前序遍历顺序根左右为abcefd故选：C。
24．【解答】一颗124个叶子结点的完全二叉树，最多有248个结点。当完全二叉树的最右非终结结点子树个数为一时，非叶节点数目＝叶节点；当完全二叉树的最右非终结结点子树个数为二时，非叶节点数目＝叶节点+1。最右非终结结点子树个数为一时，非叶结点数等于124+124＝248。二叉树结点总数等于124+124＝248＝248。
故选：B。
25．【解答】根据完全二叉树的性质，如果2i+1＞n，则结点i无右孩子，否则其右孩子rchild （i） 是结点2i+1。故选：B。
26．【解答】后序遍历知道a是根结点，中序遍历左根右知道b是左子树。故选：D。
27．【解答】解析：有一种元素除首元素没有前驱元素、尾元素没有后继元素外，其它元素都只有一个前驱元素和一个后继元素。具有以上特点的数据结构是线性结构，故选：C。
28．【解答】解析：在树形结构中，没有的是根的父节点，故选：A。
29．【解答】Integer表示整型数；Boolean是布尔型；Single是单精度的浮点型；string是字符串类型。故选：A。
30．【解答】题干要求定义一个用来存储整型数值的变量，应选择Integer类型。
故选：D

展开更多......

收起↑