三、应用题(本大题共5小题，每小题6分，共30分)
29.将题29图所示的一棵二叉树转换成对应的森林。
题29图
30.给定权值｛3，9，13，5，7｝，构造相应的哈夫曼（Huffman）树，并计算其带权路径长度。
31.写出题31图的邻接矩阵和每个顶点的入度与出度。 
题31图
32. 二叉排序树的各结点的值依次为20~28，请在题32图中标出各结点的值。
题32图
33.用冒泡排序法对数据序列（55，38，65，97，76，138，27，49）进行排序，写出排序过程中的各趟结果。
四、算法设计题(本大题共2小题，每小题7分，共14分)
34.设线性表A =（a1， a2， …,am），B=（b1, b2, …,bn），试写一个按下列规则合并A，B为线性表C的算法，使得
C=（a1, b1, …, am ,bm ,bm+1, …,bn） 当m≤n时；
或者 C=（a1, b1, …, an ,bn ,an+1, …,am） 当m>n时。
线性表A，B和C均以带头结点的单链表作为存储结构，且C表利用A表和B表中的结点空间构成。（注意：单链表的长度值m和n均未显式存储。）
35. 二叉树的二叉链表类型定义如下：
typedef struct btnode {
datatype data;
struct btnode *lchild,*rchild;
} bitreptr;
写出后根遍历根指针为t的二叉树的递归算法( void postorder (bitreptr *t) )。
考试问吧
