一、应用题(每小题10分，共50分)
1．把下图中的二叉树转化成森林。

解：1 8
/ \ | \
2 5 6 7
/ \
3 4
2．给定表（45,36,56,6,64,32,8,41），按数据元素在表中的次序构造一棵二叉查找树。

解：45
∕﹨
36 56
∕﹨﹨
6 41 64
﹨
32
∕
8
3．写出中缀表达式A-(B+C/D)*E的后缀形式。

解：
4. 下图是一个地区的交通网络模型，顶点表示城市，边表示城市间的公路，边的权值表示构造公路的费用，请问如何构造出能连通各个城市且造价最低的交通网，并写出其构造过程。

解：由题意知，连通各个城市且造价最低的交通网：1→3→5→2→4，从3分叉、3→0,3→6.连通各个城市且造价最低的交通网总费用为：3+7+2+6+5+15=38
5. 已知数据序列为12,5,9,20,6,31,24，对该数据序列进行排序，试写出冒泡排序每趟的结果。

解：初始键值序列12 5 9 20 6 31 24
第一趟排序 [5 9 12 6 20 24] 31
第二趟排序 [5 9 6 12 20] 24 31
第三趟排序 [5 6 9 12] 20 24 31
第四趟排序 5 6 9 12 20 24 31
二、算法设计题（每小题50分，共25分）
1.判断单链表head(head指向表头)是否是递增的。

解：int GetNumofItemInLnkList(LNode *head)
{
int cnt = 0;
LNode *p = head->next;
while(p)
{ cnt++; p=p->next;}
return cnt;
}
2.设一棵二叉树以二叉链表为存储结构，试写一算法求该二叉树上度为2的结点个数。

答:设根节点为r。

情况1，如果r 既有左孩子又有右孩子，则返回1 +递归求左子树度为2节点个数+ 递归求右子树度为2节点个数。

情况2，如果r 只有左孩子，则返回递归求左子树度为2节点个数。

情况3，如果r 只有右孩子，则返回递归求右子树度为2节点个数。

情况4，如果r 既没有左孩子又没有右孩子，则返回0。