《2022年哈尔滨工业大学数据结构考研复试核心题库[应用题+算法设计题].docx》由会员分享，可在线阅读，更多相关《2022年哈尔滨工业大学数据结构考研复试核心题库[应用题+算法设计题].docx（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2022年哈尔滨工业大学数据结构考研复试核心题库应用题+算法设计题 版权声明 本书根据最新复试要求并结合历年复试经验按照复试题型进行了整理编写，涵盖了这一复试科目该常考及重点复试试题并给出了参考答案，针对性强，由于复试复习时间短，时间紧张建议直接背诵记忆，考研复试首选资料。 青岛掌心博阅电子书依法对本书享有专有著作权，同时我们尊重知识产权，对本电子书部分内容参考和引用的市面上已出版或发行图书及来自互联网等资料的文字、图片、表格数据等资料，均要求注明作者和来源。但由于各种原因，如资料引用时未能联系上作者或者无法确认内容来源等，因而有部分未注明作者或来源，在此对原作者或权利人表示感谢。若使用过程中
2、对本书有任何异议请直接联系我们，我们会在第一时间与您沟通处理。 因编撰此电子书属于首次，加之作者水平和时间所限，书中错漏之处在所难免，恳切希望广大考生读者批评指正。 特别说明 本书由本机构编写组多位高分在读研究生按照考试大纲、真题、指定参考书等公开信息潜心整理编写，仅供考研复试复习参考，与目标学校及研究生院官方无关，如有侵权请联系我们立即处理。 一、应用题 1利用比较的方法进行排序，在最坏的情况下，能达到的最好时间复杂性是什么？请给出详细证明。 假定待排序的记录有。由于含n个记录的序列可能出现的状态有个，则描述个记录排序过程的判定树必须有个叶子结点。因为若少一个叶子，则说明尚有两种状态没有分辨
3、 出来。我们知道，若二叉树高度是，则叶子结点个数最多为，反之，若有个叶子结点，则 二叉树的高度至少为。这就是说，描述个记录排序的判定树必定存在一条长度为 的路径。即任何一个借助“比较”进行排序的算法，在最坏情况下所需进行的比较次数 至少是。根据斯特林公式，有。即借助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为。证毕。 2己知一个大小为512个字节长的存储，假设先后有6个用户申请大小分别为23、45、52、100、11和19的存储空间，然后再顺序释放大小为45、52和11的占用块。假设以伙伴系统实现动态存储管理。 画出可利用空间表的初始状态。 画出为6个用户分配所需要的存储空间后
4、可利用空间表的状态以及每个用户得到的存储块的起始地址。 画出在回收3个占用块之后可利用空间表的状态。 因为，所以可利用空间表的初始状态如图1所示。 图1可利用空间表的初始状态 为6个用户分配所需要的存储空间后可利用空间表的状态如图2所示。 图2分配后的可利用空间表每个用户得到的存储空间的起始地址见下表 表起始地址 在回收3个占用块之后可利用空间表的状态如图3所示。 图3回收后的可利用空间表 3将关键字序列散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组，散列函数为：，处理冲突采用线性探测再散列法，要求装填(载)因子为0.7。 (1)请画出所构造的散列表。 (2)分别计算等概率情况下，查找成功和查找不成功的平均查找长度。 (1)n=7，则。计算各关键字存储地址的过程如下。 构造的哈希表如下表所示。 (2)在等概率情况下： 由于任一关键字k，的值只能是之间，在不成功的情况下，为0需要比较3次，为1需要比较2次，为2需要比较1次，为3需要比较2次，为4需要比较1 次，为5需要比较5次，为6需要比较4次，共7种情况，如表所示。 所以有： 4己知待散列存储的关键字序列为，哈希函数为 ,哈希表为HT的长度为11,采用二次探测再散列法解决冲突，试构造此哈希表，并求出在等概率情况下的平均查找长度。 哈希表构造过程 第一步：