一．名词解释（25分，1个5分）

1.1堆分配存储表示

1.2完全图

1.3树的结点层次

1.4拓扑排序

1.5时间复杂度

二．选择题（25分，1个5分）

2.1 折半查找的平均时间复杂度是（B）

A. 1

B.logn

C. n

D. n

2.2

int frog｛

if(n==0)

return 1;

else

return （n+frog（n-1）/2）;

｝

上述算法时间复杂度是多少（B）

A.logn

B.n

C. nlogn

D. (n)`2

2.3一个算法的时间复杂度与什么有关（D）

A. 存储器的大小

B. 编程语言

C. 计算机的主频

D. 循环执行的次数

2.4具有20个树叶的二叉树中只有1个孩子的结点个数是11，则这个二叉树总的结点个数是多少（A）

A. 50

B.49

C. 51

D.52

2.5下列关于队列说话不正确的是（B）

A. 先进先出

B.后进先出

C. 插入删除只能在端点

D. 插入删除在不同点进行

三．简答题（60分）

3.1｛1，2，3，4，5，6，7，8｝利用数组建成一个最大堆并使用堆排序将其排序唯一个升序数组。要求画出所有中间过程。

3.2 先序为ABDFGHCE 中序BFDHGACE 画出该树

3.3给出一个邻接矩阵画出克鲁斯卡尔算法具体过程

00 4 4 2 1

4 00 1 00 2

4 1 00

5 3

2 00 5 00 4

1 2 3 4 00

3.4 13个权值为5，18，12，13，4，6，7，9，28，16，20，30，2

给出哈夫曼树并设计编码

3.5给出输出结果并说明函数功能。

void Print(int w)

{

int i;

if (w!=0)

{

Print(w-1);

for(i=1:i<=w;i++)

printf(“%d, ”,w);

printf(“/n”);

}

}

四．算法设计（40分）（编码困难可以写伪代码，会适当扣分）

4.1求二叉树所有具有两个子女的结点个数，如果根节点为空，则返回0。

typedef struct Bintreenode{

int data；

struct Bintreenode *right；

struct Bintreenode *left；

} *Bintreenode；

4.2 一个长度为n数组由负数0 正数组成，编写函数，将其重新排序为前面都是负数，中间都是0 .后面都是正数的结构。要求时间复杂度为n。