1、计算机专业基础综合数据结构（动态存储管理）历年真题试卷汇编 1及答案与解析一、单项选择题1 动态存储管理系统中，通常可有( )种不同的分配策略。【长沙铁道学院 1998三、3(2 分) 】（A）1（B） 2（C） 3（D）4（E）5二、填空题2 起始地址为 480，大小为 8 的块，其伙伴块的起始地址是_；若块大小为 32，则其伙伴块的起始地址为_。【北方交通大学 1999 二、1(4 分)】3 二进制地址为 011011110000，大小为(4)10 和(16)10 块的伙伴地址分别为：_、_。【上海大学 2002 二、2(2 分)】4 无用单元是指_，例如，_。【北方交通大学 1999 二
2、、6(4 分)】三、判断题5 在伙伴系统中的伙伴是指任意两块大小相同、位置相邻的内存块。( )【北京邮电大学 2000 一、8(1 分) 】（A）正确（B）错误6 在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加闲置空间的碎片。( )【东南大学 2001 一、1-1(1 分)】【中山大学 1994 一、1(2 分)】（A）正确（B）错误四、综合题7 伙伴空间。(名词解释) 【西北工业大学 1999 一、4(3 分)】8 设内存中可利用空间已连成一个单链表，对用户的存储空间需求，一般有哪三种分配策略?【 北京科技大学 1999 一、6(2 分) 】9 计算起始二进制地址
3、为 011011110000，长度为 4(十进制)的块的伙伴地址是多少?【中山大学 1999 一、2(3 分)】10 在一个伙伴系统中，已知某存储块的始址 X=(011011110000)2，大小为 24，则它的伙伴块的始址是多少?【北方交通大学 1996 一、1(5 分)】11 地址为(1664) 10 大小为(128) 10 的存储块的伙伴地址是什么?地址为(2816) 10 大小为(64)10 的存储块的伙伴地址是什么? 【清华大学 1996 四】12 试叙述动态存储分配伙伴系统的基本思想，它和边界标识法的不同点是什么?【中国人民大学 2000 一、1(4 分)】【青岛大学 2000 十
4、(10 分)】13 组织成循环链表的可利用空间表附加什么条件时，首次适配策略就转变为最佳适配策略?【 北方交通大学 1998 四(8 分) 】14 已知一个大小为 512 个字长的存储，假设先后有 6 个用户申请大小分别为23，45，52，100，11 和 19 的存储空间，然后再顺序释放大小为 45，52，11 的占用块。假设以伙伴系统实现动态存储管理。(1)画出可利用空间表的初始状态。(2)画出为 6 个用户分配所需要的存储空间后可利用空间表的状态以及每个用户所得到的存储块的起始地址。(3)画出在回收 3 个占用块之后可利用空间表的状态。【清华大学 1998 三(15 分)】【同济大学 1
5、999】15 下图所示的伙伴系统中，回收两块首地址分别为 768 及 128，大小为 27 的存储块，请画出回收后该伙伴系统的状态图。【北京邮电大学 1996 二(10 分)】15 假设利用边界标识法，并以首次拟合策略分配，已知在某个时刻可利用空间表的状态如下图所示。 (注：存储块头部 size 域的值和申请分配的存储量均包括头部和尾部的存储空间。)请画出：16 当系统回收一个起始地址为 559，大小为 45 的空闲块之后的链表状态；17 系统继而在接受存储块大小为 100 的请求后，又回收一个起始地址为 515，大小为 44 的空闲块之后的链表状态。【上海大学 2002 二、3(8 分)】计
6、算机专业基础综合数据结构（动态存储管理）历年真题试卷汇编 1答案与解析一、单项选择题1 【正确答案】 C二、填空题2 【正确答案】 480+8=488(48023+1=0) ，48032=4483 【正确答案】 01 1011 110100011011 1000004 【正确答案】 用户不再使用而系统没有回收的结构和变量，p=malloc(size)；，p=null；三、判断题5 【正确答案】 B6 【正确答案】 A四、综合题7 【正确答案】 在伙伴系统中，无论占用块还是空闲块，其大小均为 2 的 K(k 为0 的正整数)次幂。若内存容量为 2m，则空闲块大小只能是 20，2 1，2 2，2
7、m。由同一大块分裂而得的两个小块互称“伙伴空间” ，如内存大小为 210 的块分裂成两个大小为 29 的块。只有两个“伙伴空间” 才能合并成一个大空间。起始地址为 p，大小为 2k 的内存块，其伙伴的起始地址为：buddy(p，k)=p+2 k(若 p2 k+1=0)，或buddy(p，k)=p 一 2k(若 p2 k+1=2k)8 【正确答案】 首次拟合法：从链表头指针开始查找，找到第一个大于等于所需空间的结点即分配。最佳拟合法：链表结点大小增序排列，找到第一个大于等于所需空间的结点即分配。最差拟合法：链表结点大小逆序排列，总从第一个结点开始分配，将分配后结点所剩空间插入链表适当位置。首次拟
8、合法适合事先不知道请求分配和释放信息的情况，分配时需查询，释放时插在表头。最佳拟合法适用于请求分配内存大小范围较宽的系统，释放时容易产生存储量很小、难以利用的内存碎片，同时保留那些很大的内存块以备将来可能发生的大内存量的需求，分配与回收均需查询。最差拟合法适合请求分配内存大小范围较窄的系统，分配时不查询，回收时查询，以便插入适当位置。9 【正确答案】 11011110110 【正确答案】 11011111 【正确答案】 (1)buddy(1664，7)=1664 128=1536 (2)buddy(2816，6)=2816+64=288012 【正确答案】 动态存储分配伙伴系统的基本思想请参见
9、上面第 1 题。边界标识法在每块的首尾均有“ 占用 ”“空闲”标志，空闲块合并方便。伙伴系统算法简单，速度快，但只有互为伙伴的两个空闲块才可合并，因而易产生虽空闲但不能归并的碎片。13 【正确答案】 组织成循环链表的可利用空间表的结点大小按递增序排列时，首次适配策略就转变为最佳适配策略。14 【正确答案】 因为 512=29，可利用空间表的初始状态图如(1)所示。当用户申请大小为 23 的内存块时，因 245，但没有大小为 25 的块，只有大小为 29 的块，故将29 的块分裂成两个大小为 28 的块，其中大小为 28 的一块挂到可利用空间表上，另一块再分裂成两个大小为 27 的块。又将其中大
10、小为 27 的一块挂到可利用空间表上，另一块再分裂成两个大小为 26 的块，一块 26 的块挂到可利用空间表上，另一块分裂成两个大小为 25 的块，其中一块挂到可利用空间表上，另一块分给用户(地址031) 。如此下去，最后每个用户得到的存储空间的起始地址如图(2)所示，6 个用户分配所需要的存储空间后，可利用空间表的状态如图(3)所示。在回收时，因为给申请 45 的用户分配了 26，其伙伴地址是 0，在占用中，不能合并，只能挂到可利用空间表上。在回收大小为 52 的占用块时，其伙伴地址是 192，也在占用。回收大小为 11 的占用块时，其伙伴地址是 48，可以合并为大小为 25 的块，挂到可利
11、用空间表上。回收 3 个占用块之后可利用空间表的状态如图(4)所示。15 【正确答案】 因为 7682 7+1=0，所以 768 和 768+27=896 互为伙伴，伙伴合并后，首址为 768，块大小为 28。因为 7682 8+1=28，所以，首址 768、大小为 28 的块和首址 512、大小为 28 的块合并，成为首址 512、大小为 29 的空闲块。因为1282 7+1=27，其伙伴地址为 12827=0，将其插入可利用空间表中。回收后该伙伴系统的状态图如下图。16 【正确答案】 系统回收一个起始地址为 559，大小为 45 的空闲块后，因右侧起始地址 604 为空闲块，应与之合并。合并后，起始地址为 559，大小为 167 的空闲块。链表状态如图(1)所示。17 【正确答案】 系统在接受存储块大小为 100 的请求后，将大小为 117 的空闲块分出 100 给予用户。在回收一个起始地址为 5 15，大小为 44 的空闲块之后，因左侧起始地址为 462、大小为 53 和右侧起始地址为 559、大小为 167 均为空闲块，应与之合并。合并后，起始地址为 462、大小为 264 的空闲块。链表状态如图(2)所示。
