试卷答案

一、判断题

1~5: √  √  √  ×  ×

二、选择题

1~5:B  D  D  C  C

三、填空题

1.    0  1  0  1;

2.    cedba;

3.    ;

4.    任意多个;

5.    n-i+1;

6.   (rear-front+m+1)%m;

7.     push;

8.    d=2*e;

9.    升序序列;

10.   2n-1;

四、简答题

1.    数据结构的逻辑结构是指数据之间的逻辑关系,如顺序关系,隶属关系等。而存储结构则是数据在内存中位置的关系,包括顺序存储、链式存储、索引存储、散列存储

数据的逻辑结构决定着算法的设计,而算法的实现则与数据的存储结构相关。一个好的数据存储结构能够极大的优化算法。

2.   采用堆排序最合适.依题意可知,只需取得第k个最小元素之前的排序序列,堆排序的时间复杂度为O(n+k×log2n),若k≤n/log2n,则时间复杂度为O(n)。

五、应用题

1.    因为对于任意的一个节点,它最多有两个子节点,所以对于任意的一层n个节点,它的下一层最多有2n个节点。故第i层上最多有(1+2+4+…+2n)=2i-1个节点。

2.    

树的前序遍历相当于二叉树的前序遍历,树的后序遍历相当于二叉树的中序遍历。故,树的前序遍历为:ABCDEFGHIJKLMN。树的后序遍历为:CEDBAGHIFKJMNL。

3.

a) 采用堆排序方法进行排序,每一趟的排序结果。

初始堆:88,85,83,72,73,42,57,6,48,60

第一趟:85,73,83,72,60,42,57,6,48,[88]

第二趟:83,73,57,72,60,42,48,6,[85,88]

第三趟:73,72,57,6,60,42,48,[83,85,88]

b)        采用shell 排序进行排序,增量序列分别为4,2,1,每一趟的结果。

第一趟:48,6,57,72,60,42,83,88,73,85

第二趟:48,6,57,42,60,72,73,85,83,88

第三趟:6,42,48,57,60,72,73,83,85,88

六、算法设计题

1.

int TreeHeight(Node * root)

{

     if(root==NULL) return 0;

     return Max(1+TreeHeight(root->left),1+TreeHeight(root->right));

}

2. 

本题的算法思想是:由于向量中的元素按元素值非递减有序排列,值相同的元素必为相邻的元素,因此依次比较相邻两个元素,若值相等,则删除其中一个,否则继续向后查找。实现本题功能的函数如下:

Void del(vector A,int n)    

{

 int i= i,j;

while (i< = n - l )

if (A[i]! =A[i-l]) i++; 

else

for (j= (i+2);j<=n;j++ ) A[j-1]=A[ i ]; 

n - -;

}

}