数据结构、算法与应用(C++语言描述)》习题参考答案doc

再分解的元素），也可以是另一个广义表。

11.一个广义表是(a, (a, b, c), d, e, (m, n),(w, (i, j), x))，请问该广义表的长度、深度分别是多少请画出该广义表的单链表存储结构示意图。

该广义表的深度是3，长度是6。

该广义表的单链表存储结构示意图如下：

head 01a2head01a1d1e2head01m1w2head01i1x21b1n1c1j12．请列举出一些可以归纳成数组、矩阵、字符串和广义表数据结构的实际问题。

线性表的顺序存储、学生编号和姓名的问题、各班级的学生编号和姓名的问题等，都可以归结为数组。

不同物品所需原材料的数量、不同产地原材料的价格、不同类型的住宅需要的物品数量等，不同学生的计算机成绩，不同职工的工资等都可以归结为矩阵。

学生的姓名和学号、学校或各单位的名称、国家名称、一篇文章、一个高级语言源程序等，都可归结为字符串。

应用高斯消元法求解方程组可以归结为广义表。

第5章 树和二叉树

1. 请简述树、二叉树、满二叉树和完全二叉树的结构特性。

树：只有最顶层的结点没有前驱，其余结点都有且只有一个前驱；一个结点可以没有后继，也可以有一个或多个后继。

二叉树：一种特殊形态的树，每个结点至多有两个后继。 满二叉树：一种特殊形态的二叉树，除了最后一层的结点为叶子结点外其它结点都有左、右两棵子树的二叉树。

完全二叉树：一种特殊形态的二叉树，其结点与相同深度的满二叉树中的结点编号完全一致，即对于深度为k的完全二叉树，其前k-1层与深度为k的满二叉树的前k-1层完全一样，只是在第k层上有可能缺少右边若干个结点。

2. 请解释结点的度、树的度、结点的层、树的深度、分支、路径、路径长度、树的路径长度、叶子结点、分支结点、内部结点、孩子、双亲、兄弟、堂兄弟、祖先、子孙、有序树、无序树和森林等基本术语的含义。

结点的度和树的度：一个结点的后继的数目称为该结点的度，树中各结点度的最大值称为树的度。

结点的层和树的深度：树的根结点所在的层为第1层，其余结点的层等于其前驱结点的层加1，树中各结点的层的最大值称为树的深度。

分支、路径、路径长度和树的路径长度：从一个结点到其后继结点之间的连线称为一个分支，从一个结点X到另一个结点Y所经历的所有分支构成结点X到结点Y的路径，一条路径上的分支数目称为路径长度，从树的根结点到其他各个结点的路径长度之和称为树的路径长度。

叶子结点、分支结点和内部结点：树中度为0的结点称为叶子结点（或终端结点），度不为0的结点称为分支结点（或非终端结点），除根结点以外的分支结点也称为内部结点。

孩子和双亲：在树中，一个结点的后继结点称为该结点的孩子，相应地，一个结点的前驱结点称为该结点的双亲，即一个结点是其孩子结点的双亲、其双亲结点的孩子。

兄弟和堂兄弟：同一双亲的孩子结点之间互称为兄弟，不同双亲但在同一层的结点之间互称为堂兄弟。

祖先和子孙：从树的根结点到某一个结点X的路径上经历的所有结点（包括根结点但不包括结点X）称为结点X的祖先，以某一结点X为根的子树上的所有非根结点（即除结点X外）称为结点X的子孙。

有序树和无序树：对于树中的任一结点，如果其各棵子树的相对次序被用来表示数据之间的关系，即交换子树位置会改变树所表示的内容，则称该树为有序树；否则称为无序树。

森林：m（m≥0）棵互不相交的树的集合就构成了森林。 3. 请简述二叉树的五条基本性质。

性质1：在二叉树的第i层上至多有2i-1个结点（i≥1）。 性质2：深度为k的二叉树至多有2k-1个结点。

性质3：在二叉树中，若度为0的结点（即叶子结点）数为n0，度为2的结点数为n2，则n0=n2+1。

性质4：具有n个结点的完全二叉树其深度为log2n+1（其中log2n表示不大于log2n的最大整数）。

性质5：采用顺序编号的完全二叉树具有如下性质：若一个分支结点的编号为i，则其

左子树的根结点（即左孩子结点）编号为2*i，右子树的根结点（即右孩子结点）编号为2*i+1；反之，若一个非根结点的编号为i，则其双亲结点的编号为i/2（其中i/2表示不大于i/2的最大整数）。

4. 请简述二叉树的常用操作及各操作的含义。

创建一棵空二叉树：创建一棵没有任何结点的二叉树。在顺序表示中，根据树的深度为结点分配内存；在二叉链表表示中，将指向根结点的指针赋值为NULL。

删除一棵二叉树：将二叉树各结点所占据的内存释放。

清空二叉树：将二叉树的所有结点删除，使之成为一棵空二叉树。

以指定元素值创建根结点：创建根结点，并以指定值作为根结点的元素值。

将一个结点作为指定结点的左孩子插入：根据指定元素值生成一个新结点，并将其作为指定结点的左孩子。

将一个结点作为指定结点的右孩子插入：根据指定元素值生成一个新结点，并将其作为指定结点的右孩子。

先序遍历二叉树：也称为先根遍历，其访问方式递归定义如下：对于一棵二叉树，先访问其根结点，再访问根结点的左、右子树；对于左、右子树中的结点仍然是按照先序遍历方式访问，即先访问根结点，再访问根结点的左、右子树。

中序遍历二叉树：也称为中根遍历，其访问方式递归定义如下：对于一棵二叉树，先访问根结点左子树，再访问根结点，最后访问右子树；对于左、右子树中的结点仍然是按照中序遍历方式访问。

后序遍历二叉树：也称为后根遍历，其访问方式递归定义如下：对于一棵二叉树，先访问根结点的左子树，后访问右子树，最后访问根结点；对于左、右子树中的结点仍然是按照后序遍历方式访问。

逐层遍历二叉树：从第1层开始依次对每层中的结点按照从左至右的顺序进行访问。 获取指定结点的双亲结点：根据指定结点获取其双亲结点。在顺序表示中，可以直接根据指定结点的位置计算双亲结点的位置；在二叉链表表示中，则需要从根结点开始遍历二叉树直至找到指定结点的双亲结点。

删除以指定结点为根的子树：将以指定结点为根结点的子树上的所有结点（包括指定结点）删除。

按关键字查找结点：按照某种规则（先序、中序、后序或逐层）依次访问二叉树中的每一结点，直至找到与关键字匹配的结点。

判断二叉树是否为空：判断一棵二叉树是否为空二叉树。 修改指定结点的元素值：将指定结点的元素值修改为指定值。

计算二叉树的深度：按照某种规则依次访问二叉树中的每一结点，计算各结点所在层的最大值。

计算二叉树的叶子结点数：按照某种规则依次访问二叉树中的每一结点，计算度为0的结点数。

5. 请简述顺序表示的二叉树中各结点的编号规则。

顺序表示的二叉树中各结点的编号与相同深度的完全二叉树中对应结点的编号相同。 6. 请简述二叉链表表示和三叉链表表示的二叉树中结点的结构。

在二叉链表表示中，双亲结点有指向其孩子结点的指针，而孩子结点不包含指向其双亲结点的指针；在三叉链表表示中，双亲结点有指向其孩子结点的指针，而孩子结点也包含指向其双亲结点的指针。

7. 请简述二叉树的四种遍历方式及每一种遍历方式中结点的访问顺序。

先序遍历二叉树：也称为先根遍历，其访问方式递归定义如下：对于一棵二叉树，先

访问其根结点，再访问根结点的左、右子树；对于左、右子树中的结点仍然是按照先序遍历方式访问，即先访问根结点，再访问根结点的左、右子树。

中序遍历二叉树：也称为中根遍历，其访问方式递归定义如下：对于一棵二叉树，先访问根结点左子树，再访问根结点，最后访问右子树；对于左、右子树中的结点仍然是按照中序遍历方式访问。

后序遍历二叉树：也称为后根遍历，其访问方式递归定义如下：对于一棵二叉树，先访问根结点的左子树，后访问右子树，最后访问根结点；对于左、右子树中的结点仍然是按照后序遍历方式访问。

逐层遍历二叉树：从第1层开始依次对每层中的结点按照从左至右的顺序进行访问。 8. 已知一棵二叉树的先序遍历结果为A、B、D、G、C、E、F、H、I，中序遍历结果为D、G、B、A、E、C、H、F、I，请给出该二叉树的后序遍历结果。

G、D、B、E、H、I、F、C、A

9. 已知一棵二叉树的中序遍历结果为D、G、B、A、E、C、H、F、I，后序遍历结果为G、D、B、E、H、I、F、C、A，请给出该二叉树的先序遍历结果。

A、B、D、G、C、E、F、H、I

10. 已知一棵二叉树的先序遍历结果为A、B、D、G、C、E、F、H、I，后序遍历结果为G、D、B、E、H、I、F、C、A，请给出该二叉树的中序遍历结果。

D、G、B、A、E、C、H、F、I 11. 请简述哈夫曼树的结构特性。

哈夫曼树，又称最优二叉树，是指在由n个叶子结点构成的一类二叉树中具有最短带权路径长度的二叉树。

12. 请简述结点的权、结点的带权路径长度、树的带权路径长度等基本术语的含义。

结点的权和结点的带权路径长度：在实际应用中，往往给树中的结点赋予一个具有某种意义的实数，该实数就称为是结点的权。结点的带权路径长度是指从树根到该结点的路径长度与结点的权的乘积。

树的带权路径长度：是指树中所有叶子结点的带权路径长度之和，记为WPL??WiLii?1（其中，n为叶子结点的数目，Wi为第i个叶子结点的权，Li为根结点到第i个叶子结点的路径长度，可知WiLi为第i个叶子结点的带权路径长度）。 13. 请简述哈夫曼树的构造方法。

哈夫曼树的构造方法如下：

（a）已知n个权值为Wi（i=1, 2, …, n）的结点，将每个结点作为根结点生成n棵只有根结点的二叉树Ti，形成森林F={T1, T2, …, Tn}。

（b）从森林F中选出根结点权值最小的两棵二叉树Tp和Tq，并通过添加新的根结点将它们合并为一棵新二叉树，新二叉树中Tp和Tq分别作为根结点的左子树和右子树，且根结点的权值等于Tp和Tq两棵二叉树的根结点权值之和。以合并后生成的新二叉树替代森林F中的原有二叉树Tp和Tq。重复该步骤直至森林F中只存在一棵二叉树。 14. 请简述哈夫曼码的作用及其编码方法。

哈夫曼编码是指将用其他编码法表示的字符序列转成用哈夫曼码表示以减少存储空间，其具体方法为：

（a）以要编码的字符集C={c1, c2, …, cn}作为叶子结点、字符出现的频度或次数W={w1, w2, …, wn}作为结点的权，构造哈夫曼树。

（b）规定哈夫曼树中，从根结点开始，双亲结点到左孩子结点的分支标为0，双亲结点到右孩子结点的分支标为1。从根结点到某一叶子结点经过的分支形成的编码即是该叶子

n