交换a[j]、a[j+1]；
分析该算法的时间复杂性。
答：排序算法的基本运算步为元素比较，冒泡排序算法的时间复杂性就是求比较次数与n 的关系。
（1）设比较一次花时间1；
（2）内循环次数为：n-i 次,（i=1,…n ），花时间为：
∑-=-=i
n j i n 1)(1 （3）外循环次数为：n-1，花时间为：
2.设计一个分治算法计算一棵二叉树的高度。
答：算法思想：对于二叉树T ，若为空树，则其高度为0；否则，分别求其左子树和右子树的高度，最
大者加1 即为树T 的高度。其描述如下：
)1(2)()(1
-=-=∑=n n i n n T n i
int BTLength(BT T)
//为了便于描述，假定二叉树类型为BT。T 的左子树为T.lchild，右子树为T.rchild。
{
if(T= =NULL) return 0; //T为空树
return max(BTLength(T.lchild),BTLength(T.rchild)) +1
}
3.设计一个分治算法来判定给定的两棵二叉树T1 和T2 是否相同。
答：算法思想：对于两棵二叉树T1 和T2，若其根结点值相同，且其左右子树分别对应相同，则T1＝T2；否则T1≠T2。其描述如下：
boolean BTEQUAL(BT T1，BT T2)
//为了便于描述，假定二叉树类型为BT。二叉树T的左子树为T.lchild，右子树为T.rchild。
二叉树T的根结点值T.data。
{
if(T1= =NULL&& T2= =NULL) return True; //均为空树
if(T1&&T2&&T1.data==T2.data&&BTEQUAL(T1.lchild,T2.lchild)&&BTEQUAL (T1.rchild, T2.rchild))
return True;
return False;
}
4.给出一个分治算法来找出n 个元素的序列中的第2大元素，并分析算法的时间复杂度。
答：算法思想：当序列A[1..n]中元素的个数n=2 时，通过直接比较即可找出序列的第2 大元素。当n>2 时，先求出序列A[1..n-1]中的第1 大元素x1 和第2 大元素x2；然后，通过2次比较即可在三个元素x1x2 和A[n]中找出第2 大元素，该元素即为A[1..n]中的第2 大元素。
算法描述如下：
SecondElement(A[low..high],max1,max2)
{//假设主程序中调用该过程条件为high-low>=2
if(hight-low= =2)
{
if(A[low]else {max2= A[high];max1=A[low];}
}
else
{
SecondElement(A[low..high],x1,x2);
if(x1<=A[n]) { max2=max1; max1=A[n];}
else if(x2>=A[n]) { max2=x2; max1=x1; }
else { max2=A[n]; max1=x1; }
}
}
该算法的时间复杂度满足如下递归方程：T(n)=T(n-1)+2；T(2)=1。解得T(n)=2n-3。
