2018年东北大学中荷生物医学与信息工程学院842计算机专业基础之数据结构考研强化五套模拟题
● 摘要
一、综合题
1． 索引顺序存取方法(ISAM)中，主文件已按关键字排序，为何还需要主关键字索引？
【答案】ISAM 是专为磁盘存取设计的文件组织方式。即使主文件关键字有序，但因磁盘是以盘组、柱面和磁道(盘面) 三级地址存取的设备，因此通常对磁盘上的数据文件建立盘组、柱面和磁道(盘面) 三级索引。在ISAM 文件上检索记录时，先从主索引(柱面索引的索引) 找到相应柱面索引。再从柱面索引找到记录所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直到查到为止；反之，若找遍该磁道而未找到所查记录，则文件中无此记录。
2． 试证明:同一棵二又树的所有叶结点，在前序序列、对称序序列以及后序序列中都按相同的相对位置出现(即先后顺序相同) ，例如前序，后序，对称序。
【答案】前序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。三种遍历中只是访问“根”结点的时机不同，对左右子树均是按左右顺序来遍历的，因此所有叶子都按相同的相对位置出现。
3． 设依以下次序给出关键字:34，16，19，21，5，49，24，62，3，17，45，8，构造3阶B-树。要求从空树开始，每插入一个关键字，画出一棵树。
【答案】如图所示:
图
4． 设LS 是一个线性表，，若采用顺序存储结构，则在等概率的前提下，
之间
的概率为插入一个元素需要平均移动的元素个数是多少?
若元素插在
与
【答案】需要分两种情况讨论:
(1)等概率(后插) ，插入位置0..n ，则平均移动个数为n/2。
(2)若不等概率，则平均移动的元素个数为
5． 一个ISAM 文件除了主索引外，还包括哪两级索引？ ，则插入一个元素需要平均移动的元素个数又是多少？
【答案】ISAM 文件有三级索引:磁盘组、柱面和磁盘，柱面索引存放在某个柱面上，若柱面索引较大，占多个磁道时，可建立柱面索引的索引——主索引。故还包括的两级索引是盘组和磁道。
6． 已知一个大小为512个字长的存储，假设先后有6个用户申请大小分别为23, 45, 52, 100, 11
和19的存储空间，然后再顺序释放大小为45, 52, 11的占用块。假设以伙伴系统实现态存储管理。
(1)画出可利用空间表的初始状态。
(2)画出为6个用户分配所需要的存储空间后可利用空间表的状态以及每个用户所得到的存储块的起始地址。
(3)画出在回收3个占用块之后可利用空间表的状态。
【答案】(1)因为，可利用空间表的初始状态图如图1所示:
图1可利用空间表的初始状态
(2)当用户申请大小为23的内存块时，因
98，但没有大小为2的块，只有大小为2的59块，故将2的块分裂成两个大小为2的块，其中一块挂到可利用空间表上，另一块再分裂成两个
大小为2的块。又将其中大小为2的一块挂到可利用空间表上，另一块再分裂成两个大小为277
656的块。其中一块2的块挂到可利用空间表上，另一块分裂成两个大小为2的块，其中一块挂到可
利用空间表上，另一块分给用户(地址0〜31) 。如此下去，最后每个用户得到的存储空间的起始地
址如图2所示，为6个用户分配所需要的存储空间后可利用空间表的状态如图3所示。
图2每个用户得到的存储空间的起始地址
图3可利用空间表的状态
(3)在回收时，因为给申请45的用户分配了大小为的块，其伙伴地址是0, 在占用中，不能合并，只能挂到可利用空间表上。在回收大小为52的占用块时，其伙伴地址是192, 也在占用。回收大小为11的占用块时，其伙伴地址是48, 可以合并为大小的块，挂到可利用空间表上。所以回收3个占用块之后可利用空间表的状态如图4所示: