清华大学出版社数据结构(C++版)(第2版)课后习题答案最全整理

少个非零元素，这些非零元素的个数就是k的值。元素aij求所在的行为i，列为j，则在其前面的非零元素的个数是；k=2 + 3(i－1)+( j－i + 1)= 2i+ j。 ⑵ 因为k和i, j之间是一一对应的关系，k+1是当前非零元素的个数，整除即为其所在行号，取余表示当前行中第几个非零元素，加上前面零元素所在列数就是当前列号，即：

7．已知两个n×n的对称矩阵按压缩存储方法存储在已维数组A和B中，编写算法计算对称矩阵的乘积。

【解答】对称矩阵采用压缩存储，乘积矩阵也采用压缩存储。注意矩阵元素的表示方法。

第 5 章 树和二叉树 课后习题讲解

1. 填空题

⑴ 树是n（n≥0）结点的有限集合，在一棵非空树中，有（ ）个根结点，其余的结点分成m（m＞0）个（ ）的集合，每个集合都是根结点的子树。 【解答】有且仅有一个，互不相交

精选

⑵ 树中某结点的子树的个数称为该结点的（ ），子树的根结点称为该结点的（ ），该结点称为其子树根结点的（ ）。 【解答】度，孩子，双亲

⑶ 一棵二叉树的第i（i≥1）层最多有（ ）个结点；一棵有n（n>0）个结点的满二叉树共有（ ）个叶子结点和（ ）个非终端结点。 【解答】2i-1，(n+1)/2，(n-1)/2

【分析】设满二叉树中叶子结点的个数为n0，度为2的结点个数为n2，由于满二叉树中不存在度为1的结点，所以n=n0+n2；由二叉树的性质n0=n2+1，得n0=(n+1)/2，n2=(n-1)/2。

⑷ 设高度为h的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是（ ），最小值是（ ）。 【解答】2h -1，2h-1

【分析】最小结点个数的情况是第1层有1个结点，其他层上都只有2个结点。

⑸ 深度为k的二叉树中，所含叶子的个数最多为（ ）。 【解答】2k-1

【分析】在满二叉树中叶子结点的个数达到最多。

精选

⑹ 具有100个结点的完全二叉树的叶子结点数为（ ）。 【解答】50

【分析】100个结点的完全二叉树中最后一个结点的编号为100，其双亲即最后一个分支结点的编号为50，也就是说，从编号51开始均为叶子。

⑺ 已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。则该树中有（ ）个叶子结点。 【解答】12

【分析】根据二叉树性质3的证明过程，有n0=n2+2n3+1（n0、n2、n3分别为叶子结点、度为2的结点和度为3的结点的个数）。

⑻ 某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是（ ）。 【解答】CDBGFEA

【分析】根据前序遍历序列和后序遍历序列将该二叉树构造出来。

⑼ 在具有n个结点的二叉链表中，共有（ ）个指针域，其中（ ）个指针域用于指向其左右孩子，剩下的（ ）个指针域则是空的。 【解答】2n，n-1，n+1

精选

⑽ 在有n个叶子的哈夫曼树中，叶子结点总数为（ ），分支结点总数为（ ）。 【解答】n，n-1

【分析】n-1个分支结点是经过n-1次合并后得到的。

2. 选择题

⑴ 如果结点A有3个兄弟，B是A的双亲，则结点B的度是（ ）。 A 1 B 2 C 3 D 4 【解答】D

⑵ 设二叉树有n个结点，则其深度为（ ）。 A n-1 B n C 【解答】D

【分析】此题并没有指明是完全二叉树，则其深度最多是n，最少是

⑶ 二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。

A 空或只有一个结点 B 高度等于其结点数

精选

+1 D 不能确定

+1。