1. (简答题)

5.1  定义满二叉树的每一个结点或者是一个分支结点，并恰好有两个非空子结点；或者是叶结点。

证明在有n个分支结点的所有二叉树中，满二叉树的叶结点的数目（或者叶结点与全部结点数的比例）是最高的。

5.6  编写一个递归函数search，传入参数为一棵二叉树（不是二叉检索树）和一个值K，如果值K出现在树中则返回true，否则返回false。

【应用题】5.15 

（a）画出依次插入15、20、25、18、16、5 和 7 之后的BST。

（b）写出上述最终的BST树的前序遍历、中序遍历和后序遍历的结果。

【应用题】5.25

画出对下列存储于数组中的值执行buildHeap后得到的最大堆：

10    5    12    3    2    1    8    7    9    4 

【应用题】5.28

根据下面给定的字母和权重建立Huffman编码树，并给出各个字母的代码。

（A，2）（B，3）（C，5）（D，7）（E，11）（F，13）（G，17）

（H，19）（I，23）（J，31）（K，37）（L，41）

【应用题】6.7

使用加权合并规则与路径压缩，对下列从0 到15 之间的数的等价对进行归并，并给出所得到的树的父指针表示法的数

组表示。在初始情况下，集合中的每个元素分别在独立的等价类中。当两棵待归并的树的规模同样大时，使结点值较大

的根结点作为值较小的根结点的子结点。

（0，2）（1，2）（3，4）（3，1）（3，5）（9，11）（12，14）（3， 9）

（4，14）（6，7）（8，10）（8，7）（7，0）（10，15）（10，13）

6.16 （a） 使用Shaffer编写的教材《数据结构与算法分析》中例6.5的编码方法，写出下图所示树的线性实现。

注意：课后作业必须在作业本上完成，需要有完整的计算过程。在截止时间之前，在系统提交答案照片。

作业本统一交给课代表。

94分答案