数据结构的习题大全,考研必做!
第八章 动态存储管理
一.选择题 1C
二.判断题 1.错误 2.正确 三.填空题
3+1
1.(1)480+8=488(480 %2=0) (2)480-32=448 2.(1)011011110100 (2)011011100000
3.用户不再使用而系统没有回收的结构和变量。例如,p=malloc(size); ,p=null; 四.应用题
1. 在伙伴系统中,无论占用块或空闲块,其大小均为2的k(k为≥0的正整数)次幂。若内
m012m
存容量为2,则空闲块大小只能是2,2,2, ,2。由同一大块分裂而得的两个小块
109
互称“伙伴空间”,如内存大小为2的块分裂成两个大小为2的块。只有两个“伙伴空间”才能合并成一个大空间。
k
起始地址为p,大小为2的内存块,其伙伴的起始地址为:
k k+1k k+1k
buddy(p,k)=p+2 (若p % 2=0),或buddy(p,k)=p-2 (若p % 2=2) 2.首次拟合法;从链表头指针开始查找,找到第一个≥所需空间的结点即分配。
最佳拟合法:链表结点大小增序排列,找到第一个≥所需空间的结点即分配。
最差拟合法:链表结点大小逆序排列,总从第一个结点开始分配,将分配后结点所剩空间插入到链表适当位置。
首次拟合法适合事先不知道请求分配和释放信息的情况,分配时需查询,释放时插在表头。 最佳拟合法适用于请求分配内存大小范围较宽的系统,释放时容易产生存储量很小难以利用的内存碎片,同时保留那些很大的内存块以备将来可能发生的大内存量的需求,分配与回收均需查询。 最差拟合法适合请求分配内存大小范围较窄的系统,分配时不查询,回收时查询,以便插入适当位置。
3. 011011110100 4.011011100000 5.(1)buddy(1664,7)=1664-128=1536 (2)buddy(2816,6)=2816+64=2880
6.动态存储分配伙伴系统的基本思想请参见上面题1。边界标识法在每块的首尾均有“占用”/“空闲”标志,空闲块合并方便。伙伴系统算法简单,速度快,但只有互为伙伴的两个空闲块才可合并,因而易产生虽空闲但不能归并的碎片。
7.组织成循环链表的可利用空间表的结点大小按递增序排列时, 首次适配策略就转变为最佳适配策略。
9
8.因为512=2,可利用空间表的初始状态图如8-1所示。
4559
当用户申请大小为23的内存块时,因2<23<=2,但没有大小为2的块,只有大小为2的
988
块,故将2的块分裂成两个大小为2的块,其中大小为2的一块挂到可利用空间表上,另一块
77
再分裂成两个大小为2的块。又将其中大小为2的一块挂到可利用空间表上,另一块再分裂
665
成两个大小为2的块,一块2的块挂到可利用空间表上,另一块分裂成两个大小为2的块,其中一块挂到可利用空间表上,另一块分给用户(地址0—31)。如此下去,最后每个用户得到的存储空间的起始地址如图8-2, 6个用户分配所需要的存储空间后可利用空间表的状态如图8-3。
6
在回收时,因为给申请45的用户分配了2,其伙伴地址是0,在占用中,不能合并,只能挂到可利用空间表上。在回收大小为52的占用块时,其伙伴地址是192,也在占用。回收大小
5
为11的占用块时,其伙伴地址是48,可以合并为大小2的块, 挂到可利用空间表上。回收3个占用块之后可利用空间表的状态如图8-4。

1
目前最完整的数据结构1800题包括完整答案 第七章 图答案_IT/计算机_专业资料。...深度优先 23.宽度优先遍历 24.队列 25.因未给出存储结构,答案不唯一。本题按...
√ 部分答案解释如下。 1、 头结点并不“仅起”标识作用,并且使操作统一。另外,头结点数据域可写入链表长度, 或作监视哨。 4.两种存储结构各有优缺点,应根据...
目前最完整的数据结构1800题包括完整答案 第一章 绪论_IT/计算机_专业资料。目前...【武汉交通科技大学 1996 一、4 (2 分) 】 A.动态结构、静态结构 B.顺序...
目前最完整的数据结构1800题包括完整答案目前最完整的数据结构1800题包括完整答案隐藏>> 第四章 串一、选择题 1.B 2.E 3.C 4.A 5.C 6.A 7.1D 7.2F ...
将会提前完成 【北方交通大学 1999 一、7 (3 分)【北京工业大学 1999 一、1 (2 分)】】二、判断题 1.树中的结点和图中的顶点就是指数据结构中的数据元素...
最完整的数据结构1800题含答案第1章 绪论 一、选择...动态结构、静态结构 B.顺序结构、链式结构 C.线性...在顺序存储结构中,有时也存储数据结构中元素之间的...
最完整的数据结构1800题包括完整答案第9章 查找_理学_高等教育_教育专区。今日...cs3简单制作动态搞笑图片160份文档 2014年度细分行业报告汇集 2014年移动互联网O2O...
目前最完整的数据结构1800题包括完整答案 第四章 串 目前最完整的数据结构1800题...串既可以采用顺序存储,也可以采用链式存储 2 若串 S1=‘ABCDEFG’, S2=‘...
第八章动态存储管理 习题带... 4页 2财富值 目前最完整的数据结构1800... ...数据结构1800题与答案是数据结构考研必备,收集了历年考研各高校数据结构的真题。数...
热门文档