清华大学2005年计算机科学数据结构部分考研试题

清华大学2005年CS试题（回忆版）

数据结构部分：
一，问答
１．什么是线性表 ？
２．线性表分为顺序表和单链表 ，使用时如何选用？
３．已知中序　，前序求后序
４．２０００００００个记录　，磁盘页块数为。。。　，５个存放关键字　，问B树的关键字为多少，　没做出来，　具体细节忘了
５．给了４个散列函数，　问是否可行　，是否好
１）H(key)=key / n
2 ) H(key)=1
3 ) H(key)=(key+random(n)) / n (random(n)产生一个小于n的随机数
４）H(key) =key mod p(n) ,其中p(n)为一个不大于n的最大素数

二．AVL树的插入和删除

三．证明中序　，前序　，后序的叶子节点的相对前后位置都是一样的

四．１．最短路径程序填空
２．最短路径的一个程序应用　，设每个节点的什么什么距，反正就是与其他节点的最短路径的最大值　，　所有节点中的什么什么距的最小值的节点叫做图的中心　。求一个返回图中心的程序　。

其他推荐阅读：