二、读程序题
阅读下列程序，并写出其运行结果。
1．Void P(int w)
{
If(w>0)
{ p(w-1);
Cout<<w;
}
}
调用p(4)=
2．Void P(int w)
{
If(w>)
{Cout<<w;
p(w-1);
}
}
调用p(4)=
3．Void P(int w)
{
If(w>0)
{Cout<<w;
4．在编号的完全二叉树中，判断编号为i和j的两个结点在同一层的条件是什么？
for (j=i;j<n;j++) x++;
时间复杂度为：
（2）i=n;
while (i>1) i=i/2;
时间复杂度为：
（3）for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
for (k=1;k<=n;k++)
x++;
时间复杂度为：
（4）for (i=1;i<n;i++)
for (j=1;j<n;j++) x++;
2．以数据集合{4,6,8,10,12,15,18,20,22}中的元素为叶子结点的权值构造一棵哈夫曼树，并计算其带权路径长度。
3．分别用Prim算法和Kruskal算法求解出下图的最小生成树，在空内填写每一步所加入的边的两个顶点，如Prim算法第一步加入的边的两个顶点为①⑥
（1）Prim算法：
，，，，，
for (k=1;k<n;k++) x++;
时间复杂度为：
2．假设栈S的一个输入序列为1,2,3,4,5，判断序列1,3,4,5,2是否是合法的输出序列，请解释理由（进出栈顺序）。
3．已知一棵树的度为4，其中度为4的结点数目为3，度为3的结点数目为4，度为2的结点数目为5，度为1的结点数目为2，请求出该树中的叶子结点的数目。
（5030 120 25 85 40 100 12 90 15 60 35 105 78 10 28）
9．将下面的数据分别调整为大根堆和小根堆。
（5030 120 25 85 40 100 12 90 15 60 35 105 78 10 28）
四、简答题
1．计算整个程序段的时间复杂度。
（1）for (i=0;i<n;i++)
p(w-1);
Cout<<w;
}
}
调用p(4)=
4．Void P(int w)
{
If(w>0)
{ p(w-1);
p(w-1);
Cout<<w;
}
}
调用p(4)=
三、操作题
1．分别由下面的两个序列构造出相应的二叉树
（1）先序：ABCDEFGHI中序：ADECFBGIH
（2）后序：DCFEBIHGA中序：DCBFEAGHI
（2）Kruskal算法：
，，，，，
4．对有序数据表（5,7,9,12,15,18,20,22,25,30,100）构造二分查找判定树。
5．设散列函数为H(k)=k%7，采用拉链法处理冲突，将关键字10,26,38,43,55,69,72,88,100,92依次存储到散列表中，并求出等概率情况下的平均查找长度。
6．对下面数据表，写出采用希尔排序算法排序的每趟的结果。
（78100 120 25 85 40 90 15 60 35 105 50 30 10 28 12）
7．对下面数据表，写出采用冒泡排序算法排序的每趟的结果。
（10550 30 25 85 40 100 12 10 28）
8．对下面数据表，写出采用快速排序算法排序的第一趟的结果。