广州大学松田学院7数据结构复习题-树-参考答案.pdfVIP

广州大学松田学院7数据结构复习题-树-参考答案--第1页

7数据结构复习题（二叉树）

一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）

（√）（1）树结构中每个结点最多只有一个直接前驱。

（ㄨ）（2）完全二叉树一定是满二查树。

（ㄨ）（3）在中序线索二叉树中，右线索若不为空，则一定指向其双亲。

（√）（4）一棵二叉树中序遍历序列的最后一个结点，必定是该二叉树前序遍历的最后一个结点。

（√）（5）二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。

（√）（6）由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。

（√）（7）在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。

（ㄨ）（8）在哈夫曼编码中，当两个字符出现的频率相同，其编码也相同，对于这种情况应该做特

殊处理。

（ㄨ）（9）含多于两棵树的森林转换的二叉树，其根结点一定无右孩子。

（√）（10）具有n个叶子结点的哈夫曼树共有2n-1个结点。

二．填空题

（1）在树中，一个结点所拥有的子树数称为该结点的度。

（2）度为零的结点称为叶（或叶子，或终端）结点。

（3）树中结点的最大层次称为树的深度（或高度）。

（4）对于二叉树来说，第i层上至多有2i-1个结点。

h

（5）深度为h的二叉树至多有2-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种。

AAAA

BBBB

CCC1C

广州大学松田学院7数据结构复习题-树-参考答案--第1页

广州大学松田学院7数据结构复习题-树-参考答案--第2页

（17）三个结点可以组成2种不同形态的树。

（18）将一棵完全二叉树按层次编号，对于任意一个编号为i的结点，其左孩子结点的编号为：2*i。

（19）给定如下图所示的二叉树，其前序遍历序列为：ABEFHCG。

A