ds(50分）
一。（15分）
回答下列各题，并简要说明理由，每题3分
1。 什么是线形表？线形表的各元素类型是否必须是同一类型？为什么？
2。线形表有两种不同的继承形式，顺序的和链接的存储结构，
在使用时，如何确定使用哪种存储结构？
3。给出一个二叉树的前序和中序遍历序列，要求写出后序遍历序列。
4。（记不清楚具体数字了，大概的数字把）
一个文件用b+树做索引，给定文件大小2000000 b，每个页块大小为4000 b,
每个指针大小为5 b。每个记录是200 b,其中关键码为5 b.
问：
1）应采用多少阶b+树?
2)该文件索引块数目。
5。下列哪些可以做hash函数？哪些效果不好？哪些效果好？
其中，n为hash表的表长；random(n)可以产生一个0---n=1 的随机数；
p(n)为小于n的最大素数。
1）hash(key) = key/n;
2) hash(key) = 1;
3) hash(key) = (key + random(n)) % n;
4) hash(key) = key % p(n);
二。（5分）
证明：一棵二叉树的前序，中序，后序遍历序列中，叶结点的相对位置是不变的
三。（15分）
1） 给定一组关键码，要求依次插入建立一棵avl树，大约12个关键码左右，
（和03年那个真题只是关键码的不同）
需要旋转的时候，要求标出旋转的类型：左单旋，右单旋，先左后右双旋，先右后
左双旋。
2）在建成的这棵avl树上，依次删除关键码****（四个），要求：
如果需要旋转，那要标出旋转类型；用中序的直接前驱代替关键码
四。（15分）
1）将书上284页的dijkstra算法挖去5个空，让添。（5分）
具体字母有差别，但是确实就是那个算法，我按照书上的来了。
void shortestpath(graph<t> g, int v, int n)
{
for (int i = 0; i < n; i++){ //n为图的顶点数目
dist[i] = edge[v][i];
s[i] = 0;
if (i != v && dist[i] < maxnum)
1空;
else
path[i] = -1;
}
s[v] = 1;
dist[v] = 0;
for (int i = 0; i < n - 1; i++){
float min = maxnum;
