数据结构第8章例题与答案

第八章 动态存储管理
一、选择题
1. 动态存储管理系统中，通常可有（    ）种不同的分配策略。【长沙铁道学院 1998 三、3 (2分)】
a． 1            b.  2        c.  3        d.  4           e.  5
 
二、判断题
1．  在伙伴系统中的伙伴是指任意两块大小相同、位置相邻的内存块。（  ）
【北京邮电大学 2000 一、8(1分)】
2．  在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加闲置空间的碎片。（  ）【东南大学 2001 一、1-1 （1分）】【中山大学 1994  一、1（2分）】
 
三、填空题
1．起始地址为480,大小为8的块,其伙伴块的起始地址是_______;若块大小为32,则其伙伴块的起始地址为_______。【北方交通大学 1999 二、1（4分）】
2．二进制地址为011011110000，大小为（4）10和（16）10块的伙伴地址分别为：________、_________。
【上海大学 2002 二、2（2分）】
3．  无用单元是指________,例________【北方交通大学 1999 二、6（4分）】

8．已知一个大小为512个字长的存储，假设先后有6个用户申请大小分别为23，45，52，100，11和19的存储空间，然后再顺序释放大小为45，52，11的占用块。假设以伙伴系统实现动态存储管理。
（1） 画出可利用空间表的初始状态。
（2） 画出为6个用户分配所需要的存储空间后可利用空间表的状态以及每个用户所得到的存储块的起始地址。
（3） 画出在回收3个占用块之后可利用空间表的状态。【清华大学1998三(15分)】【同济大学 1999】
9．下图所示的伙伴系统中，回收两块首地址分别为768及128，大小为27的存储块，请画出回收后该伙伴系统的状态图。【北京邮电大学 1996 二、（10分）】
10．假设利用边界标识法，并以首次拟合策略分配，已知在某个时刻可利用空间表的状态如下图所示：
（注：存储块头部size域的值和申请分配的存储量均包括头部和尾部的存储空间。）
请画出：
（1）当系统回收一个起始地址为559，大小为45的空闲块之后的链表状态；
（2）系统继而在接受存储块大小为100的请求后，又回收一个起始地址为515，大小为44的空闲块之后的链表状态。【上海大学 2002 二、3（8分）】