【考研题库】2020年中国海洋大学数据结构考研复试核心题库[应用题+算法设计题]

版权声明

本书根据最新复试要求并结合历年复试经验按照复试题型进行了整理编写，涵盖了这一复试科目该常考及重点复试试题并给出了参考答案，针对性强，由于复试复习时间短，时间紧张建议直接背诵记忆，考研复试首选资料。

青岛掌心博阅电子书依法对本书享有专有著作权，同时我们尊重知识产权，对本电子书部分内容参考和引用的市面上已出版或发行图书及来自互联网等资料的文字、图片、表格数据等资料，均要求注明作者和来源。但由于各种原因，如资料引用时未能联系上作者或者无法确认内容来源等，因而有部分未注明作者或来源，在此对原作者或权利人表示感谢。若使用过程中对本书有任何异议请直接联系我们，我们会在第一时间与您沟通处理。

因编撰此电子书属于首次，加之作者水平和时间所限，书中错漏之处在所难免，恳切希望广大考生读者批评指正。

特别说明

本书由本机构编写组多位高分在读研究生按照考试大纲、真题、指定参考书等公开信息潜心整理编写，仅供考研复试复习参考，与目标学校及研究生院官方无关，如有侵权请联系我们立即处理。

一、应用题

1．数组以行为主序存储，设第一个元素的首地址是78,每个元素的长度为4，试求元素的存储首地址。

【答案】元素的存储首地址为958。三维数组以行为主序存储，其元素地址公式为:

其中，是各维的下界和上界，是各维元素个数，L是一个元素所占的存储单元数。

2．一个算法所需时间由下述递归方程表示，试求出该算法的时间复杂性的级别(或阶)(以大形式表示)。

其中:n是问题的规模，为简单起见，设n是2的整数幂。

【答案】设，亦即。

所以有，所以该算法的时间复杂度为。

3．设有6个有序表A、B、C、D、E、F，分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排序。要求通过5次两两合并，将6个表最终合并成一个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题：

(1)请写出完整的合并过程，并求出最坏情况下比较的总次数。

(2)根据你的合并过程，描述n个不等长升序表的合并策略，并说明理由。

【答案】(1)6个表的合并顺序如图所示，实际上相当于以各有序表的长度为权值构建一棵哈夫曼树。

图

根据该哈夫曼树，6个序列的合并过程如下。

第1次合并：表A与表B合并，生成含有45个元素的表AB。

第2次合并：表AB与表C合并，生成含有85个元素的表ABC。

第3次合并：表D与表E合并，生成含有110个元素的表DE。

第4次合并：表ABC与表DE合并，生成含有195个元素的表ABCDE。

第5次合并：表ABCDE与表F合并，生成含有395个元素的表ABCDEF。

由于合并两个长度分别为m和n的有序表，最坏情况下需要比较m+n-1次，故最坏情况下比较的总次数计算如下。

第1次合并：最多比较次数=10+35-1=44。

第2次合并：最多比较次数=45+40-1=84。

第3次合并：最多比较次数=50+60-1=109。

第4次合并：最多比较次数=85+110-1=194。

第5次合并：最多比较次数=195+200-1=394。

比较总次数最多=44+84+109+194+394=825。

(2)各表的合并策略是：在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序，可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。

4．己知一个大小为512字的内存，假设先后有6个用户提出大小分别为23、45、52、100、11和19的分割请求，此后大小为45、52和11的占用块顺序释放。假设以伙伴系统实现动态存储管理。

(1)请写出可利用空间表的初始状态；

(2)请写出6个用户进入之后，每个用户所分配的存储块的大小和起始地址；

(3)请写出在回收三个用户释放的存储块之后，空闲块的大小和起始地址。

【答案】(1)可利用空间表的初始状态如下图所示。

图

(2)设大小为512字的内存的起始地址为p，则有

第一个用户分配的存储块的大小为，起始地址为p;

第二个用户分配的存储块的大小为，起始地址为；

第三个用户分配的存储块的大小为，起始地址为；

第四个用户分配的存储块的大小为，起始地址为；

第五个用户分配的存储块的大小为，起始地址为；

第六个用户分配的存储块的大小为，起始地址为％

(3)大小为的空闲块有两个，起始地址为和；

大小为的空闲块有两个，起始地址为和；

大小为的空闲块有两个，起始地址为。

5．已知待排序的序列为试完成下列各题。

(1)根据以上序列建立一个堆(画出第一步和最后堆的结果图)，希望先输出最小值。

(2)输出最小值后，如何得到次小值(并画出相应结果图)。

【答案】(1)建小堆

(2)求次小值