数据结构考研分类复习真题 第八章 答案[4]

数据结构考研分类复习真题 第八章 答案[4]  

　　 ．因为 = 可利用空间表的初始状态图如 所示

　　当用户申请大小为 的内存块时 因 < <= 但没有大小为 的块 只有大小为 的块 故将 的块分裂成两个大小为 的块 其中大小为 的一块挂到可利用空间表上 另一块再分裂成两个大小为 的块 又将其中大小为 的一块挂到可利用空间表上 另一块再分裂成两个大小为 的块 一块 的块挂到可利用空间表上 另一块分裂成两个大小为 的块 其中一块挂到可利用空间表上 另一块分给用户(地址 — ) 如此下去 最后每个用户得到的存储空间的起始地址如图 个用户分配所需要的存储空间后可利用空间表的状态如图

　　在回收时 因为给申请 的用户分配了 其伙伴地址是 在占用中 不能合并 只能挂到可利用空间表上 在回收大小为 的占用块时 其伙伴地址是 也在占用 回收大小为 的占用块时 其伙伴地址是 可以合并为大小 的块 挂到可利用空间表上 回收 个占用块之后可利用空间表的状态如图

　　（注 在图 和 画上了占用块 从原理上 只有空闲块才出现在 可利用空间表 中 ）