深度为k的二叉树中，所含叶子的个数最多为（）。

填空题深度为k的二叉树中，所含叶子的个数最多为（）。

1.填空题设高度为h的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是（），最小值是（）。

2.填空题一棵二叉树的第i（i≥1）层最多有（）个结点；一棵有n（n>0）个结点的满二叉树共有（）个叶子结点和（）个非终端结点。

3.填空题树中某结点的子树的个数称为该结点的（），子树的根结点称为该结点的（），该结点称为其子树根结点的（）。

4.填空题树是n（n≥0）结点的有限集合，在一棵非空树中，有（）个根结点，其余的结点分成m（m＞0）个（）的集合，每个集合都是根结点的子树。

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

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

6.问答题若在矩阵A中存在一个元素ai，j（0≤i≤n-1，0≤j≤m-1），该元素是第i行元素中最小值且又是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。假设以二维数组存储矩阵A，试设计一个求该矩阵所有马鞍点的算法，并分析最坏情况下的时间复杂度。

7.问答题 设某单位职工工资表ST由“工资”、“扣除”和“实发金额”三项组成，其中工资项包括“基本工资”、“津贴”和“奖金”，扣除项包括“水”、“电”和“煤气”。
⑴请用广义表形式表示所描述的工资表ST，并用表头和表尾求表中的“奖金”项；
⑵画出该工资表ST的存储结构。

8.问答题已知A为稀疏矩阵，试从空间和时间角度比较采用二维数组和三元组顺序表两种不同的存储结构完成求运算的优缺点。

9.问答题 一个稀疏矩阵如图4-4所示，写出对应的三元组顺序表和十字链表存储表示。

对应的三元组顺序表如图4-5所示，十字链表如图4-6所示。

10.判断题线性表可以看成是广义表的特例，如果广义表中的每个元素都是单元素，则广义表便成为线性表。