数据结构单元7练习.doc

《数据结构单元7练习.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、单元练习7一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）树结构中每个结点最多只有一个直接前驱。（╳）（2）完全二叉树不一定是满二查树。（╳）（3）在中序线索二叉树中，右线索若不为空，则不一定指向其双亲。（√）（4）一棵二叉树中序遍历序列的最后一个结点，必定是该二叉树前序遍历的最后一个结点。（√）（5）二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。（√）（6）由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。（√）（7）在完全二叉树中，若一个结点没有左孩子，则它必然是叶子

2、结点。二．填空题（1）在树中，一个结点所拥有的子树数称为该结点的度。（2）度为零的结点称为叶（或叶子，或终端）结点。（3）树中结点的最大层次称为树的深度（或高度）。（4）对于二叉树来说，第i层上至多有2i-1个结点。（5）深度为h的二叉树至多有2h-1个结点。（6）由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。（7）有20个结点的完全二叉树，编号为10的结点的父结点的编号是5。（8）由二叉树的后序和中序遍历序列，可以唯一确定一棵二叉树。（9）某二叉树的中序遍历序列为:DEBAC，后序遍历序列为：EBCAD。则前序

3、遍历序列为：DABEC。（10）设一棵二叉树结点的先序遍历序历为：ABDECFGH，中序遍历序历为：DEBAFCHG，则二叉树中叶结点是：E、F、H。（11）已知完全二叉树的第8层有8个结点，则其叶结点数是68。（12）采用二叉链表存储的n个结点的二叉树，一共有2n个指针域。（13）采用二叉链表存储的n个结点的二叉树，共有空指针n+1个。（14）前序为A，B，C且后序为C，B，A的二叉树共有4种。ACBABCABCACB（18）将一棵完全二叉树按层次编号，对于任意一个编号为i的结点，其左孩子结点的编号为：2*i。（19）

4、给定如下图所示的二叉树，其前序遍历序列为：ABEFHCG。ABFGHDCE（20）给定如下图所示的二叉树，其层次遍历序列为：ABCEFGH。ABFGHDCE三．选择题（1）树最适合用来表示（D）。A．有序数据元素B．无序数据元素C．元素之间无联系的数据D．元素之间有分支的层次关系（2）前序为A，B，C的二叉树共有（D）种。A．2B．3C．4D．5（3）根据二叉树的定义，具有3个结点的二叉树有（C）种树型。A．3B．4C．5D．6（4）在一棵具有五层的满二叉树中，结点的总数为（B）A．16B．31C．32D．33（5）具有

5、64个结点的完全二叉树的深度为（C）A．5B．6C．7D．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．ABECDABCDABEFCDABEGFDCD（9）如右图所示的二叉树，后序遍历的序列是（D）ABADECFGHIA．A、B、C、D、E、F、G、H、

6、IB．A、B、D、H、I、E、C、F、GC．H、D、I、B、E、A、F、C、GD．H、I、D、E、B、F、G、C、A（10）对于下边的二叉树，其中序序列为（A）A．DBEHAFCGB．DBHEAFCGC．ABDEHCFGD．ABCDEFGH（11）某二叉树的后序遍历序列为：DABEC，中序遍历序列为:DEBAC，则前序遍历序列为（D）。A．ACBEDB．DECABC．DEABCD．CEDBA（12）具有n（n>1）个结点的完全二叉树中，结点i（2i>n）的左孩子结点是（D）。A．2iB．2i+1C．2i-1D．不存在（若

7、2i<=n，则答案为A）（13）把一棵树转换为二叉树后，这棵二叉树的形态是（A）。A．唯一的B．有多种C．有多种，但根结点都没有左孩子D．有多种，但根结点都没有右孩子（14）将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为45的结点的左孩子编号为（C）。A．46B．47C．90D．91（15）将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为49的结点的右孩子编号为（B）。A．98B．99C．50D．100（16）二叉树按某种顺序线索化

8、后，任一结点均有指向其前驱和后继的线索，这种说法（）。A．正确B．错误C．不确定D．都有可能（17）下列陈述正确的是（D）。A．二叉树是度为2的有序树B．二叉树中结点只有一个孩子时无左右之分C．二叉树中必有度为2的结点D．二叉树中最多只有两棵子树，且有左右子树之分（20）二叉树的叶结点个数比度为2的结点的个数（C）。