数据结构单元练习7.docx

本文格式为Word版，下载可任意编辑数据结构单元练习7 单元练习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 A A A B B B B C C C （17）三个结点可以组成 2 种不同形态的树 C （18）将一棵完全二叉树按层次编号，对于任意一个编号为i的结点，其左孩子结点的编号为： 2*i （19）给定如下图所示的二叉树，其前序遍历序列为： ABEFHCG A C B E F G H （20）给定如下图所示的二叉树，其层次遍历序列为： ABCEFGH A C B E F G H 三．选择题 （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 A A A C C C C B B B B D E F D D E D E FG （9）如右图所示的二叉树，后序遍历的序列是（ D ） A． A、B、C、D、E、F、G 、H、I A C BB． A、B、D、H、I、E、C、F、G F G D E C． H、D、I、B、E、A、F、C、G H I D． H、I、D、E、B、F、G、C、A （10）对于下边的二叉树，其中序序列为 （ A ） A．DBEHAFCG B．DBHEAFCG C．ABDEHCFG D．ABCDEFGH A B C D E F G H （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．有多种，但根结点都没有右孩子 （14）将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，那么编号为45的结点的左孩子编号为（ B ） A．46 B．47 C．90 D．91 （15）将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，那么编号为49的结点的右孩子编号为（ B ） A．98 B．99 C．50 D．100 （16）二叉树按某种依次线索化后，任一结点均有指向其前驱和后继的线索，这种说法（ B ）。

A．正确 B．错误 C．不确定 D．都有可能 （17）以下陈述正确的是（ D ） A．二叉树是度为2的有序树 B．二叉树中结点只有一个孩子时无左右之分 C．二叉树中必有度为2的结点 D．二叉树中最多只有两棵子树，且有左右子树之分 （18）用5个权值{3, 2, 4, 5, 1}构造的哈夫曼树的带权路径长度是（ B ） Ａ．32 Ｂ．33 Ｃ．34 Ｄ．15 （ 先构造哈夫曼树，WPL=（1+2）*3+（3+4+5）*2=33 ） （19）在树布局中，若结点B有4个兄弟，A是B的父亲结点，那么A的度为为（ C ） A．3 B．4 C．5 D．6 （20）二叉树的叶结点个数比度为2的结点的个数（ C ） A．无关 B．相等 C．多一个 D．少一个 四. 简答题 1． 已知一棵树边的集合如下，请画出此树，并回复问题。

{(L,M),(L,N),(E,L),(B,E),(B,D),(A,B),(G,J),(G,K),(C,G),(C,F),(H,I),(C,H),(A,C)} （1）哪个是根结点？ （2）哪些是叶结点？ （3）哪个是G的双亲？ （4）哪些是G的祖先？ （5）哪些是G的孩子？ （6）哪些是E的子孙？ （7）哪些是E的兄弟？哪些是F的兄弟？ （8）结点B和N的层次各是多少？ — 8 —。