2017年郑州轻工业学院数据结构复试仿真模拟三套题
● 摘要
一、应用题
1． 假设计算机系统采用CSCAN （循环扫描）磁盘调度策略。使用2KB 的内存空间记录16384个磁盘块的空闲状态。
（1）请说明在上述条件下如何进行磁盘空闲状态的管理。
（2）设某单面磁盘旋转速度为每分钟6000转，每个磁道有100个扇区，相邻磁道间的平均移动时间为lms 。若在某时刻，磁头位于100号磁道处，并沿着磁道号增大的方向移动（如下图
，所示）磁道号请求队列为50, 90, 30, 120, 对请求队列中的每个磁道需要读取1个随机分布的扇区，则读完这4个扇区总共需要多少时间? 要求给出计算过程。
图
SSD 等），（3）如果将磁盘替换为随机访问的FLash 半导体存储器（如U 盘、是否有比CSCAN
更高效的磁盘调度策略? 若有，给出磁盘调度策略的名称并说明理由；若无，说明理由。
【答案】（1）采用位示图法管理磁盘空闲块，每一位表示一个磁盘块的状态，共需要16384/32=512个字节即2KB 的空间，正好可放在系统提供的内存中。
（2）采用CSCAN 调度算法，访问磁道的顺序和移动的磁道数如下表所示：
故移动的磁道数为20+90+20+40=170, 所花的时间为170ms 。由于转速为
花的时间为0.4ms 。综上所述，读取磁道上所有扇区所花的总时间为
第 2 页，共 25 页 则平均旋 转延迟为5ms ，总的旋转延迟时间为20ms ，读取一个扇区的平均时间为0.1ms , 故读取4个扇区所（3）采用先来先服务（FCFS ）调度策略更高效，因为Flash 半导体存储器的物理结构不需要
考虑寻道时间和旋转延迟，可直接按请求的先后顺序服务。
2． 两个字符串s1和s2的长度分别为m 和n 。求这两个字符串最大共同子串算法的时间复杂度
，并简要说明理由。 为T （m ，n ）。估算最优的T （m , n ）
【答案】最优的T （m ，n ）是D （n ）。串S2是串S1的子串，且在S1中的位置是1。开始求
出最大公共子串的长度恰是串S2的长度。一般情况下，
3． 已知一个大小为512个字长的存储，假设先后有6个用户申请大小分别为23，45，52，100，11和19的存储空间，然后再顺序释放大小为45，52，11的占用块。假设以伙伴系统实现态存储管理。
（1）画出可利用空间表的初始状态。
（2）画出为6个用户分配所需要的存储空间后可利用空间表的状态以及每个用户所得到的存储块的起始地址。
（3）画出在回收3个占用块之后可利用空间表的状态。
【答案】（1）因为可利用空间表的初始状态图如图1所示：
图1 可利用空间表的初始状态
（2）当用户申请大小为23的内存块时，因但没有大小为的块，只有大小为的块，
故将
的块分裂成两个大小为的块，其中一块挂到可利用空间表上，另一块再分裂成两个
大小为
的块。又将其中大小为的一块挂到可利用空间表上，
另一块再分裂成两个大小为的
块。其中一块的块挂到可利用空间表上，
另一块分裂成两个大小为的块，其中一块挂到可利用空间表上，另一块分给用户（地址0〜31）。如此下去，最后每个用户得到的存储空间的起始地址如图2所示，为6个用户分配所需要的存储空间后可利用空间表的状态如图3所示。
第 3 页，共 25 页
图2 每个用户得到的存储空间的起始地址
]
图3 可利用空间表的状态
（3）在回收时，因为给申请45的用户分配了大小为的块，其伙伴地址是0，在占用中，不能合并，只能挂到可利用空间表上。在回收大小为52的占用块时，其伙伴地址是192，也在占用。回收大小为11的占用块时，其伙伴地址是48，可以合并为大小的块，挂到可利用空间表上。所以回收3个占用块之后可利用空间表的状态如图4所示：
第 4 页，共 25 页
相关内容
相关标签