2017年淮北师范大学数据结构复试实战预测五套卷
● 摘要
一、应用题
1． 将关键字序列（7, 8, 30，11，18, 9，14）散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组。散列函数是：
列法，要求装填（载）因子为0.7。
（1）请画出所构造的散列表。
（2）分别计算等概率情况下查找成功和查找不成功的平均查找长度。
【答案】（1）要求装填因子为0.7, 数组的长度应该为7/0.7=10, 数组下标为0〜9。各关键字的散列函数值如下表：
采用线性探测法再散列法处理冲突，所构造的散列表为：
（2）查找成功时，在等概率情况下，查找表中每个元素的概率是相等的，因此是根据表中元素个数来计算平均查找长度，各关键字的比较次数如下表所示：
故查找成功的平均查找长度为（1+1+1+1+3+3+2）/7=12/7。
在不成功的情况下，由于任意关键字key , H （key ）的值只能是0〜6之间，H （key ）为0需要比较3次，H （key ）为1需要比较2次，H （key ）为2需要比较1次，H （key ）为3需要比较2次，H （key ）为4需要比较1次，H （key ）为5需要比较5次，H （key ）为6需要比较4次，共7种情况，如下表所示：
所以，在等概率下，查找失败的平均查找长度为：（3+2+1+2+1+5+4）/7=18/7。
处理冲突采用线性探测再散
2． 假定有下列，矩阵（n 为奇数）
如果用一维数组B 按行主次序存储A 的非零元素，问：
（1）A 中非零元素的行下标与列下标的关系；
（2）给出A 中非零元素的下标
位在B 中的位置公式。
【答案】（1）主对角线上元素的坐标是i=j，副对角线上元素的坐标i 和j 有
所以A 中非零元素的行下标和列下标的关系是或 的关系，与B 中的下标R 的关系； 给出利用的下标定（3）假定矩阵中每个元素占一个存储单元且B 的起始地址为（2）非零元素分布在两条主、副对角线上，除对角线相交处一个元素（下称“中心元素”）外，其余每行都有两个元素。主对角线上的元素，在向量B 中存储的下标
是
副对角线上的元素，在中心元素前，在向量B
中存储的下标是
在中心元素后，其下标如下：
（3）在B 中的位置如下：
3． 在堆排序、快速排序和合并排序中：
（1）若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？
（2）若只从排序结果的稳定性考虑，则应选取哪种排序方法？
（3）若只从平均情况下排序最快考虑，则应选取哪种排序方法？
（4）若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？
【答案】（1）应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排序方法。 （2）应选取归并排序方法
（3）应选取快速排序方法
（4）应选取堆排序方法
4． 画出同时满足下列两个条件的两棵不同的二叉树。
（1）按前序遍历二叉树的顺序为ABCDE 。
（2）高度为5其对应的树（森林）的高度最大为4。
【答案】（1）满足条件的二叉树如图1所示：
图1
（2）满足条件的二叉树如图2所示：
图2
5． 主机H 通过快速以太网连接Internet , IP地址为
题 a 表
服务器S 的IP 地址为211.68.71.80。H 与S 使用TCP 通信时，在H 上捕获的其中5个IP 分组如题a 表所示。
请回答下列问题。
（1）题a 表中的IP 分组中，哪几个是由H 发送的? 哪几个完成了TCP 连接建立过程? 哪几个