3． 给定一棵以二叉链表形式存储的二叉树，root指向其根。请编写算法求二叉树的高度。
4． 给定一棵以二叉链表形式存储的二叉树，root指向其根。请编写算法求出二叉树中值为x的结点的数目。
5． 已知下图所示的二叉树是由某森林转换而来的。请给出原森林。
6． 假定有八个字符，它们出现的概率分别为：0.07、0.09、0.14、0.19、0.23、0.44、0.58和0.77。
（1）请给出这8个字符的哈夫曼树和哈夫曼编码；
（2）编码树的WPL的实际意义是什么？
第六章
1． 对于如下图所示的有向图，请给出
(1) 各顶点的入度和出度
(2) 强连通分量和弱连通分量
(3) 邻接矩阵
(4) 邻接表和逆邻接表
2． 假设有向图存储为邻接矩阵，请编写一个算法，求出指定顶点的入度和出度。
3． 对于如下图所示的无向图，分别画出其深度优先搜索和广度优先搜索生成的树。
4． 对下面的无向带权图应用求最短路经的Floyd算法，求出每对顶点之间的最短路径，并写出在算法的执行过程中所求得的各个矩阵。
5． 对如下图所示的无向带权图，按照Kruskal算法求出最小生成树，并画出每一步所得到的中间结果。
第七章
1． 试比较顺序查找算法和二分查找算法的特点、优缺点。
2． 请编写一个递归的二分查找算法。
3． 从一棵空的查找树开始，依次插入键值71，32，103，66，135，82，57，91，画出每次插入后所得到的查找树，再依次删除57、82、71，画出每次删除后所得到的查找树，并对最终得到的查找树求出等概率情况下的平均成功查找长度。
4． 请编写一个判断二叉树T是否为查找树的算法，假定二叉树T是以标准形式存贮的。
5． 从一个空的散列表开始，依次为插入关键字Jan、Feb、Mar、Apr、May、Jun、Jul、Aug、Sep、Oct、Nov、Dec，散列函数为 为关键字key第一个字母的序号，如 散列表长度为17。分别使用
（1） 线性探测法
（2） 链地址法
建立散列表。请分别画出散列表，并求出等概率情况下的平均成功查找长度。
第八章
1． 分别用下列排序算法对关键字序列（49，7，50，5，94，16，90，29，71）进行排序，写出每一趟排序所得到的中间结果。
（1） 直接插入排序
（2） 希尔排序
（3） 改进的冒泡排序
（4） 快速排序
（5） 直接选择排序
（6） 堆排序
（7） 合并排序
2． 一种冒泡排序算法是所谓“上浮式的”，即每趟排序都把较小的关键字“浮”到上面（数组下标较小的那一边）去。请编写一个改进的“下沉式的”冒泡排序算法。
3． 举例说明直接选择排序算法、快速排序算法和堆排序算法不是稳定的。