2 2 行数：4 列数：4 2 3 -1 5 非零元素个数：4
十字链表：
441001221301022111032222-123530
3. 算法设计
（1）设计上三角矩阵存储类，实现如下接口：
① 对于上三角矩阵A[N][N]，可按行优先压缩存储和按列优先压缩存储。
② 对于给定的一维数组B[M]，可根据行优先压缩存储或列优先压缩存储还原原始的上三角矩阵。
（2）针对24位真彩色BMP图像文件，编写程序实现如下功能： ① 读取24位真彩色BMP图像文件。
② 将原图像转换为24位灰度图像，并进行保存。转按公式如下： Grey=0.3*Red+0.59*Blue+0.11*Green
③ 将24位灰度图像转换为8位灰度图像，并进行保存。
④ 将8位灰度图像分别进行4－邻域和8－邻域平滑，并分别进行保存。
习题5
1. 填空题
（1）已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为（___________）。 答案：129
（2）3个结点可构成（___________）棵不同形态的二叉树。 答案：5 （3） 设树的度为5，其中度为1~5的结点数分别为6、5、4、3、2个，则该树共有（___________）
个叶子。
答案：31
（4）在结点个数为n（n>1）的各棵普通树中，高度最小的树的高度是（___________），它有（___________）个叶子结点，（___________）个分支结点。高度最大的树的高度是（___________），它有（___________）个叶子结点，（___________）个分支结点。 答案：2 n-1 1 n 1 n-1
（5）深度为k的二叉树，至多有（___________）个结点。
答案：2-1 （6）（7）有n个结点并且其高度为n的二叉树的数目是（___________）。 答案：2n-1
（8）设只包含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为（___________），最小结点数为（___________）。
答案：2-1 k+1 （9）将一棵有100个结点的完全二叉树按层编号，则编号为49的结点为X，其双亲PARENT（X）的编号为（）。 答案：24
（10）已知一棵完全二叉树中共有768个结点，则该树中共有（___________）个叶子结点。 答案：384 （11）（12）已知一棵完全二叉树的第8层有8个结点，则其叶子结点数是（___________）。 答案：68
（13）深度为8（根的层次号为1）的满二叉树有（___________）个叶子结点。
答案：128
（14）一棵二叉树的前序遍历是FCABED，中序遍历是ACBFED，则后序遍历是（___________）。 答案：ABCDEF
（15）某二叉树结点的中序遍历序列为ABCDEFG，后序遍历序列为BDCAFGE，则该二叉树结点的前序遍历序列为（___________），该二叉树对应的树林包括（___________）棵树。 答案：EACBDGF 2
2. 选择题
（1）在一棵度为3的树中，度为3的结点的个数为2，度为2的结点个数为1，则度为0的结点个数为（ ）。 A. 4 B. 5 （2）下列陈述中正确的是（ ）。 A. 二叉树是度为2的有序数
B. 二叉树中结点只有一个孩子时无左右之分 C. 二叉树中必有度为2的结点
D. 二叉树中最多只有两棵子树，并且有左右之分 （3）在K叉树中，如果结点M有3个兄弟，而且N是M的双亲，则N的度是（ ） A. 3 B. 4 C. 5 D. 1
（4）设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ ）。 A. 2h B. 2h－1 C. 2h+1 （5）高度为5的完全二叉树至少有（ ）个结点。
D. h+1
C. 6
D. 7
k+1k
A. 16 B. 32 C. 31 D. 5 （6）具有65个结点的完全二叉树的高度为（ ）。（根的层次号为0） A. 8 B. 7 C.6 D. 5 （7）对一个满二叉树，m个树叶，n个结点，深度为h，则（ 无 ）。 A. n=h+m
B. h+m=2n
C. m=h-1 D. n=2h-1
（8）任一棵二叉树，其叶子结点数为n0，度为2的结点数为n2，则存在关系（ ）。 A. n2 +1=n0 B. n0 +1=n2 C. 2n2 +1=n0 D. n2 =2n0 +1
（9）某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（ ）。
A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca （10）设m、n为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是（ ）。 A. n在m右方 B. n是m祖先 C. n在m左方 D.n是m子孙 （11）一棵二叉树的广义表表示为a（b（c，d），e（f（g））），则得到的层序遍历序列为（ ）。
A. abcdefg B. cbdaegf C. cdbgfea D. abecdfg
（12）若二叉树采用二叉链表作为存储结构，要交换其所有分支结点左右子树的位置，利用（ ）遍历方法最合适。 A. 前序 B. 中序
C. 后序
D. 层序
说明：显然，如果按前序或后序遍历，当访问某结点时，交换其左右孩子，则可完成要求。进行层序遍历时，当结点出队时，交换左右孩子，也可以完成题目要求。因此该题有3个答案，谈不上哪个最合适。建议该题目将“最合适”改为“不合适”，这样答案应该是唯一的。 （13）对二叉树进行（ ）遍历，可以得到该二叉树所有结点构成的排序序列。 A. 前序 B. 中序 C. 后序 D. 层序
（14）设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（ ）个。
A. n-1 B. n C. n+1 D. n+2
（15）利用3，6，8，12，5，7这6个值作为叶子结点的权，生成一棵哈夫曼树，该树的深度为（ ）。
A.3 B. 4 C.5 D. 6
（16）若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（ ）。 A. n-1 B. [n/m]-1 C. [(n-1)/(m-1)] D. [n/(m-1)]-1
说明：在这里度为m的哈夫曼树是指仅含有度为0和m的结点的m叉树。因此有： (1) Ｎ＝n+nm
(2) N = 1 + mnm
3. 试分别画出具有3个结点的树和二叉树的所有不同形态。 答案：树：
二叉树：
4． 试找出分别满足下面条件的所有二叉树： （1）前序序列和中序序列相同； 答案: 右斜树
（2）中序序列和后序序列相同； 答案：左斜树
（3）前序序列和后序序列相同。 答案：只有根结点的树
5．一棵高度为h的满k叉树有如下性质：第h层上的结点都是叶结点，其余各层上每个结点都有k棵非空子树，如果按层次自顶向下，同一层自左向右，顺序从0开始对全部结点进行编号，试问：
（1）各层的结点个数是多少？
答案：n层的结点个数为kn-1
（2）编号为i的结点的父结点（若存在）的编号是多少？ 答案：|(i-1)/k| (|·|表示取下整)
（3）编号为i的结点的第m个孩子结点（若存在）的编号是多少？ 答案：k*i+m
（4）编号为i的结点有右兄弟的条件是什么？其右兄弟结点的编号是多少？ 答案：i%k!=0 i+1
（5）叶子结点数n0和非叶子结点数nk之间满足的关系。 答案：nk*(k-1)=n0-1
6．若一棵二叉树的前序序列为abdgcefh，中序序列为dgbaechf，请画出该二叉树，并写出其后序序列。 答案：gdbehfca