7数据结构复习题（二叉树）
一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ）
（√）（1）树结构中每个结点最多只有一个直接前驱。
（ㄨ）（2）完全二叉树一定是满二查树。
（ㄨ）（3）在中序线索二叉树中，右线索若不为空，则一定指向其双亲。
（√）（4）一棵二叉树中序遍历序列的最后一个结点，必定是该二叉树前序遍历的最后一个结点。
（√）（5）二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。
（√）（6）由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。
（√）（7）在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。
（ㄨ）（8）在哈夫曼编码中，当两个字符出现的频率相同，其编码也相同，对于这种情况应
该做特殊处理。
（ㄨ）（9）含多于两棵树的森林转换的二叉树，其根结点一定无右孩子。
（√）（10）具有n个叶子结点的哈夫曼树共有2n-1个结点。
二．填空题
（1）在树中，一个结点所拥有的子树数称为该结点的  度    。
（2）度为零的结点称为    叶（或叶子，或终端）    结点。
（3）树中结点的最大层次称为树的   深度（或高度）  。
（4）对于二叉树来说，第i层上至多有  2i-1  个结点。
（5）深度为h的二叉树至多有 2h-1  个结点。
（6）由一棵二叉树的前序序列和   中序  序列可唯一确定这棵二叉树。
（7）有20个结点的完全二叉树，编号为10的结点的父结点的编号是 5 。
（8）哈夫曼树是带权路径长度    最小 的二叉树。
（9）由二叉树的后序和  中序   遍历序列，可以唯一确定一棵二叉树。
（10）某二叉树的中序遍历序列为: DEBAC，后序遍历序列为：EBCAD。则前序遍历序列为：DABEC 。
（11）设一棵二叉树结点的先序遍历序历为：ABDECFGH，中序遍历序历为：DEBAFCHG，则二叉树中叶结点是：  E、F、H  。
（12）已知完全二叉树的第8层有8个结点，则其叶结点数是  68    。
（13）由树转换成二叉树时，其根结点无  右子树 。
（14）采用二叉链表存储的n个结点的二叉树，一共有  2n  个指针域。
（15）采用二叉链表存储的n个结点的二叉树，共有空指针  n+1  个。
（16）前序为A，B，C且后序为C，B，A的二叉树共有  4  种。
A
C
B
A
B
C
A
B
C
A
C
B
（17）三个结点可以组成  2  种不同形态的树。
（18）将一棵完全二叉树按层次编号，对于任意一个编号为i的结点，其左孩子结点的编号为： 2*i 。
（19）给定如下图所示的二叉树，其前序遍历序列为：  ABEFHCG  。
A
B
F
G
HD
C
E
（20）给定如下图所示的二叉树，其层次遍历序列为：  ABCEFGH  。
A
B
F
G
HD
C
E
三．选择题
（1）树最适合用来表示（  D  ）。
    A．有序数据元素                        B．无序数据元素
    C．元素之间无联系的数据                D．元素之间有分支的层次关系
（2）前序为A，B，C的二叉树共有（  D  ）种。
    A．2                B．3                C．4                D．5
（3）根据二叉树的定义，具有3个结点的二叉树有（  C  ）种树型。
    A．3                B．4                C．5                D．6
（4）在一棵具有五层的满二叉树中，结点的总数为（  B  ）
    A．16              B．31              C．32                D．33
（5）具有64个结点的完全二叉树的深度为（  C  ）
    A．5                B．6                C．7                D．8
（6）任何一棵二叉树的叶结点在前序、中序、后序遍历序列中的相对次序（  A  ）。
    A．不发生改变      B．发生改变        C．不能确定          D．以上都不对
（7）A，B为一棵二叉树上的两个结点，在中序遍历时，A在B前的条件是（  C  ）。
    A．A在B右方      B．A是B祖先      C．A在B左方        D．A是B子孙
（8）下列4棵树中，（  B  ）不是完全二叉树。
    A．                B．                C．                  D．
A
B
E
C
D
A
B
C
D
A
B
E
F
C
D
A
B
E
G
FD
C
D
（9）如右图所示的二叉树，后序遍历的序列是（  D  ）
A
BA
D
E
C
F
G
H
I
    A． A、B、C、D、E、F、G 、H、I
   
B． A、B、D、H、I、E、C、F、G
 
C． H、D、I、B先序中序后序遍历二叉树、E、A、F、C、G
   
D． H、I、D、E、B、F、G、C、A
（10）对于下边的二叉树，其中序序列为  （  A  ）
A．DBEHAFCG      B．DBHEAFCG        C．ABDEHCFG          D．ABCDEFGH
 
（11）某二叉树的后序遍历序列为：DABEC，中序遍历序列为: DEBAC，则前序遍历序列为（  D  ）。
    A． ACBED            B．DECAB            C．DEABC          D．CEDBA
（12）具有n（n>1）个结点的完全二叉树中，结点i（2i>n）的左孩子结点是（  D  ）。
A．2i                B．2i+1                C．2i-1                D．不存在
（若2i<=n，则答案为A）
（13）把一棵树转换为二叉树后，这棵二叉树的形态是（  A  ）。
A．唯一的                              B．有多种
C．有多种，但根结点都没有左孩子        D．有多种，但根结点都没有右孩子

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。