特别说明
本书根据历年考研大纲要求并结合历年考研真题对该题型进行了整理编写，涵盖了这一考研科目该题型常考试题及重点试题并给出了参考答案，针对性强，考研复习首选资料。
版权声明
青岛掌心博阅电子书依法对本书享有专有著作权，同时我们尊重知识产权，对本电子书部分内容参考和引用的市面上已出版或发行图书及来自互联网等资料的文字、图片、表格数据等资料，均要求注明作者和来源。但由于各种原因，如资料引用时未能联系上作者或者无法确认内容来源等，因而有部分未注明作者或来源，在此对原作者或权利人表示感谢。若使用过程中对本书有任何异议请直接联系我们，我们会在第一时间与您沟通处理。
因编撰此电子书属于首次，加之作者水平和时间所限，书中错漏之处在所难免，恳切希望广大考生读者批评指正。
重要提示
本书由本机构编写组多位高分在读研究生按照考试大纲、真题、指定参考书等公开信息潜心整理编写，仅供考研复习参考，与目标学校及研究生院官方无关，如有侵权请联系我们立即处理。一、2021年石家庄铁道大学信息科学与技术学院912数据结构考研核心题库之应用题精编
1．已知一个大小为512个字长的存储，假设先后有6个用户申请大小分别为23,45,52,100,11和19的存储空间，然后再顺序释放大小为45,52,11的占用块。假设以伙伴系统实现动态存储管理。
(1)画出可利用空间表的初始状态。
(2)画出为6个用户分配所需要的存储空间后可利用空间表的状态以及每个用户所得到的存储块的起始地址。
(3)画出在回收3个占用块之后可利用空间表的状态。
【答案】因为，可利用空间表的初始状态图如图(1)所示。
当用户申请大小为23的内存块时，因，但没有大小为的块，只有大小为的块，故将的块分裂成两个大小为的块，其中大小为的一块挂到可利用空间表上，另一块再分裂成两个大小为的块。又将其中大小为的一块挂到可利用空间表上，另一块再分裂成两个大小为的块，一块的块挂到可利用空间表上，另一块分裂成两个大小为的块，其中一块挂到可利用
空间表上，另一块分给用户(地址0?31)。如此下去，最后每个用户得到的存储空间的起始地址如图(2)所示，6个用户分配所需要的存储空间后，可利用空间表的状态如图(3)所示。
在回收时，因为给申请45的用户分配了，其伙伴地址是0,在占用中，不能合并，只能挂到可利用空间表上。在回收大小为52的占用块时，其伙伴地址是192,也在占用。回收大小为11的占用块时，其伙伴地址是48,可以合并为大小为的块，挂到可利用空间表上。回收3个占用块之后可利用空间表的状态如图(4)所示。
图
图
图
图2．对如下算法，解答下列问题：
(1)该算法正确吗？循环结束条件能否满足？
(2)若将改为是否满足？
(3)若将结束条件处的条件改为，其它不变，是否正确？
(4)若仅将结束处条件改为，是否正确？
(5)试找出二叉树中各结点在栈中所处层次的规律。
【答案】(1)错误。循环结束条件不能满足，因为是在时执行的。
(2)错误。
(3)错误。
(4)正确。
(5)规律如下：每一结点的深度与其右孩子的深度相同；每一结点的深度比其左孩子的深度少1。
3．有以下程序，分析其中函数的时间复杂度。