四、对下图的二叉树完成如下要求： 1．写出该树的深度
2．写出该深度的满二叉数的总结点数 3．写出二叉树的后序遍历的序列 4．将二叉树还原成森林 A B F C G H D I J E 五、假设用于通信的电文仅由8个字母（A—H）组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试用这8个字母进行以下操作： 1．构造一棵赫夫曼树（左结点的权小于右结点的权） 2．求出带权路径的长度
3．设计赫夫曼编码（左分支为“0”，右分支为“1”）
六、任意一棵有N个结点的二叉树，已知它有M个叶子结点。试证明非叶子结点中度数为2的有M-1个，其余的度数为1。
七、简述以下算法的功能（栈和队列的元素类型为int）。 void algo (Queue &Q) {
Stack S; int d; InitStack(S);
While (!QueueEmpty(Q)) {
DeQueue(Q,d); Push (S,d); }
While (!StackEmpty(S)) {
Pop(S,d); EnQueue (Q,d); } }
八、算法题：
1、设计一个算法按层次输出二叉树中的所有结点，要求同一层次的从左向右输出（存储按二叉树表）。
2、已知一单链表，头指针为h，指向表头结点，请写出算法对此单链表就地逆转。（h仍旧为逆转后的单链表的头指针指向表头结点）。 注：逆转为：原单链表的序列为（a1,a2?an），则逆转后为（an,an-1,?a1）
3、写一算法，实现统计带表头的单链表中元素值为奇数的接点个数。
九、已知线性链表如下图，头指针为La，写出语句序列使左图中的指针指向改成右图中的指针指向。
Laa b c a b Lac
十、在一个C语言程序中，有结构类型STUDENT的定义和结构数组allstudents的声明如下： struct STUDENT {
char name[8]; int number; }
STUDENT allstudents[10][50];
allstudents是一个二维数组，它的每个元素都是包含name和number的结构类型。已知在C语言中，二维数组使用以行序为主序的存储结构，char类型占用1字节，int类型占用4字节。
假定allstudents在内存中的起始存储位置是2000，请写出计算allstudents[i][j]的存储位置的算式，并计算allstudents[3][5]的存储位置。
十一、用下标从0到4的一维数组存储一个循环队列，目前其中有两个元素A、B，状态如图(a)。如果此后有17个数据元素C、D、??P、Q、R、S依次进队列，其间又有16个元素先后出队列，请在图(b)中填写队列最后的状态，包括其中的元素和指针的位置。
rear→ (b)
B
front→ A
(a)
十二、附加题：
1、Josephus问题是下面的游戏：N个人从1到N编号，围坐成一个圆圈。从1号开始传递一个热土豆。经过M次传递后拿着热土豆的人被清除离座，围坐的圆圈缩小，由坐在被清除的人后面的人拿土豆继续进行游戏。最后剩下的人取胜。因此，如果M=0和N=5，则依次被清除的人的顺序是2，4，1，5。
a.写一个算法思想解决M和N在一般值下的Josephus问题，应使你的程序尽可能地高效，要确保能够清除单元。（包括采用的数据结构、方法） b.估计你的程序时间复杂度。
2.计算n!的递归函数fac(n)如下，试分析它的时间复杂度。（请写出详细的分析步骤） Int fac(int n) {
If(n<=1) return 1; else return(n*f(n-1)); }
