数据结构(大作业)

1．把下图中的二叉树转化成森林。

2．给定表（45,36,56,6,,32,8,41），按数据元素在表中的次序构造一棵二叉查找树。

3．写出中缀表达式A-(B+C/D)*E的后缀形式。ABCD/+E*-

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

5. 已知数据序列为12,5,9,20,6,31,24，对该数据序列进行排序，试写出冒泡排序每趟的结果。

二、算法设计题（每小题50分，共25分）

1.判断单链表head(head指向表头)是否是递增的。

2.设一棵二叉树以二叉链表为存储结构，试写一算法求该二叉树上度为2的结点个数。

则返回 递归求左子树度为2节点个数。

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

情况4。

情况2，则返回 递归求右子树度为2节点个数。

情况1：

设根节点为 r，如果 r 既没有左孩子又没有右孩子