清华大学 - 话题

数据结构:
第一题:15分
1。线性表的定义，表中元素是否必须是同一个类型，为什么？

2。线性表有两种存储形式，定义如下，然后给了一个线性链表类的空架字，一个
静态数组实现类，一个单链表实现类，后两个继承于第一个。问使用时如何选用哪
种类型的实现。

3。二叉树给你前序和中序排列，求后序
所给序列已经记不清了，可能是前序ABDEFCFHIJ，中序DBCEAFCHIJ。

4。B树相关计算
一个磁盘块大小4，000（实际为4096，但是为计算方便，按4000算），一个地址指
针需要5个字节。有一个有20，000，000条记录的文件。一个关键字占5个字节，求
B树的最大阶数，当记录不是按顺序排列时，求索引需要占用的磁盘块数。

5。散列有n个位置，0~n-1。判断散列函数是否正确，插入和查找是否能正确执行
，如正确，判断好坏，不正确说明原因。random(n)函数能随机产生0~n-1之间的数
。
1) H(Key)=Key/n；
2) H(Key)=1;
3) H(Key+random(n))%n;
4) H(Key)%p(n)，其中p(n)是比n小的素数


第2题:5分
证明:在前序序列、中序序列和后序序列中叶节点相对(前后)的排列位置不变

第3题:15分
AVL树的插入和删除
1) 从空树开始插入数值,(数值序列也记不清楚了,只能写个大概,大家参考20,12,
9,27,22,17,16,15,18,10),画出插入后的状态,如需旋转,标明旋转的种类(有单右
旋转,单左旋转,先左后右旋转,先右后左旋转).
2) 从刚才生成的AVL树中删除22,...,9和10,画出删除后的状态和旋转的类型.删除
的非叶子结点用中序前趋结点代替.

第4题:
图类
template class Graph{
int numberOfVectise(Graph G){}//返回图中顶点数
.
.
.
}
1) 在图中用dijsktla算法求从u点出发到各个点的最短路径算.5分
template void shortestdist(Graph G,int v, float
*dist,int *path){
//在图G中求由点c出发到各点的最点路径,路径长度放在数组dist中,路径放在数组
path里,maxWeight是float型所能表示的最大值
int n=numberOfVectise(G);
int *S=new int[n];
for(int i=0;i {
......
if(value(u,i) else path=-1;
....

后面有两个空是if（）中&&之前的第一个判断条件

}
}
整个函数太长,我记不得了，书上应该是有的.

2) 在一个图中,从u点出发,到图中各个点的最短路径中距离最长的叫做点u在这个
图中的偏心距.图中偏心距最小的点叫做中心.设计算法求一个图的中心.函数头为
template int centre(Graph G, float &mindist);
函数返回值是中心点编号,mindist返回的是最小偏心距.10分
这个题我记得练习册上有原题,只是换了一种表述,实质是一样的.

北京是中国的首都吗？

考研论坛提示：
1、请勿发布个人联系方式或询问他人联系方式，包括QQ和手机等。
2、未经允许不得发布任何资料出售、招生中介等广告信息。
3、如果发布了涉及以上内容的话题或跟帖，您在考研网的注册账户可能被禁用。