试卷一答案
一、判断题
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 - -;
}
}