当前位置：文档之家› 数据结构1800题和答案第8章动态存储管理

数据结构1800题和答案第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分）】

四、应用题

1．伙伴空间（名词解释）【西北工业大学 1999 一、4（3分）】

2．设内存中可利用空间已连成一个单链表，对用户的存储空间需求，一般有哪三种分配策略？

【北京科技大学 1999 一、6（2分）】

3．计算起始二进制地址为011011110000，长度为4（十进制）的块的伙伴地址是多少？

【中山大学1999一、2(3分)】

4．在一个伙伴系统中，已知某存储块的始址Ｘ＝（011011110000）2，大小为２4，则它的伙伴块的始址是多少？【北方交通大学 1996 一、1（5分）】

5．地址为（1664）10大小为（128）10的存储块的伙伴地址是什么？

地址为（2816）10大小为（64）10的存储块的伙伴地址是什么？【清华大学1996 四、】6．试叙述动态存储分配伙伴系统的基本思想，它和边界标识法不同点是什么？

【青岛大学 2000 十、（10分）】【中国人民大学 2000 一、1（4分）】

7．组织成循环链表的可利用空间表附加什么条件时，首次适配策略就转变为最佳适配策略？

【北方交通大学 1998 四、（8分）】

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分）】

第10题图：可利用空间表的状态图

实验三动态分区存储管理方式的主

实验三动态分区存储管理方式的主存分配回收一、实验目的深入了解动态分区存储管理方式主存分配回收的实现。二、实验预备知识存储管理中动态分区的管理方式。三、实验内容编写程序完成动态分区存储管理方式的主存分配回收的实现。实验具体包括：首先确定主存空间分配表；然后采用最优适应算法完成主存空间的分配和回收；最后编写主函数对所做工作进行测试。四、提示与讲解动态分区管理方式预先不将主存划分成几个区域，而把主存除操作系统占用区域外的空间看作一个大的空闲区。当作业要求装入主存时，根据作业需要主存空间的大小查询主存内各个空闲区，当从主存空间中找到一个大于或等于该作业大小的主存空闲区时，选择其中一个空闲区，按作业需求量划出一个分区装入该作业。作业执行完后，它所占的主存分区被收回，成为一个空闲区。如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。实现动态分区的分配和回收，主要考虑的问题有三个：第一，设计记录主存使用情况的数据表格，用来记录空闲区和作业占用的区域；第二，在设计的数据表格基础上设计主存分配算法；第三，在设计的数据表格基础上设计主存回收算法。首先，考虑第一个问题：设计记录主存使用情况的数据表格，用来记录空闲区和作业占用的区域。由于动态分区的大小是由作业需求量决定的，故分区的长度是预先不固定的，且分区的个数也随主存分配和回收变动。总之，所有分区情况随时可能发生变化，数据表格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在主

存中的起始地址和长度。由于分配时空闲区有时会变成两个分区：空闲区和已分分区，回收主存分区时，可能会合并空闲分区，这样如果整个主存采用一张表格记录已分分区和空闲区，就会使表格操作繁琐。主存分配时查找空闲区进行分配，然后填写已分配区表，主要操作在空闲区；某个作业执行完后，将该分区变成空闲区，并将其与相邻的空闲区合并，主要操作也在空闲区。由此可见，主存的分配和回收主要是对空闲区的操作。这样为了便于对主存空间的分配和回收，就建立两张分区表记录主存使用情况，一张表格记录作业占用分区的 “已分配区表”；一张是记录空闲区的“空闲区表”。这两张表的实现方法一般有两种，一种是链表形式，一种是顺序表形式。在实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固定，所以无论是“已分配区表”还是“空闲区表”都必须事先确定长度。它们的长度必须是系统可能的最大项数，系统运行过程中才不会出错，因而在多数情况下，无论是“已分配区表”还是“空闲区表”都有空闲栏目。已分配区表中除了分区起始地址、长度外，也至少还要有一项“标志”，如果是空闲栏目，内容为“空”，如果为某个作业占用分区的登记项，内容为该作业的作业名；空闲区表中除了分区起始地址、长度外，也要有一项“标志”，如果是空闲栏目，内容为“空”，如果为某个空闲区的登记项，内容为“未分配”。在实际系统中，这两表格的内容可能还要多，实验中仅仅使用上述必须的数据。为此, “已分配区表”和“空闲区表”在实验中有如下的结构定义。已分配区表的定义： #define n 10// 假定系统允许的最大作业数量为n struct {float address;// 已分分区起始地址 float length; // 已分分区长度，单位为字节 int flag;// 已分配区表登记栏标志, “0表”示空栏目，实验中只支持一个字符的作业名}used_table[n];// 已分配区表空闲区表的定义：

北航计算机考研材料：动态存储管理答案.doc

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

动态分区式存储管理

可变分区存储管理设计思路：整体思路：可变分区管理方式将内存除操作系统占用区域外的空间看做一个大的空闲区。当作业要求装入内存时，根据作业需要内存空间的大小查询内存中的各个空闲区，当从内存空间中找到一个大于或等于该作业大小的内存空闲区时，选择其中一个空闲区，按作业需求量划出一个分区装人该作业，作业执行完后，其所占的内存分区被收回，成为一个空闲区。如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。设计所才用的算法：采用最优适应算法，每次为作业分配内存时，总是把既能满足要求、又是最小的空闲分区分配给作业。但最优适应算法容易出现找到的一个分区可能只比作业所需求的长度略大一点的情行，这时，空闲区分割后剩下的空闲区就很小以致很难再使用，降低了内存的使用率。为解决此问题，设定一个限值min size，如果空闲区的大小减去作业需求长度得到的值小于等于min size，不再将空闲区分成己分分区和空闲区两部分，而是将整个空闲区都分配给作业。内存分配与回收所使用的结构体：为便于对内存的分配和回收，建立两张表记录内存的使用情况。一张为记录作业占用分区的“内存分配表”，内容包括分区起始地址、长度、作业名/标志（为0时作为标志位表示空栏目）；一张为记录空闲区的“空闲分区表”，内容包括分区起始地址、长度、标志（0表空栏目，1表未分配）。两张表都采用顺序表形式。关于分配留下的内存小碎片问题：当要装入一个作业时，从“空闲分区表”中查找标志为“ 1”（未分配）且满足作业所需内存大小的最小空闲区，若空闲区的大小与作业所需大小的差值小于或等于min size，把该分区全部分配给作业，并把该空闲区的标志改为“0”（空栏目）。同时，在已分配区表中找到一个标志为“ 0”的栏目登记新装人作业所占用分区的起始地址，长度和作业名。若空闲区的大小与作业所需大小的差值大于

目前最完整的数据结构1800题包括完整答案-第三章-栈和队列范文(汇编)

第3章栈和队列一选择题 1. 对于栈操作数据的原则是（）。【青岛大学 2001 五、2（2分）】 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 【上海海运学院 1997 二、1（5分）】【上海海运学院 1999 二、1（5分）】 3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。 A. 不确定 B. n-i+1 C. i D. n-i 【中山大学 1999 一、9(1分)】 4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的【武汉大学 2000 二、3】 5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，p N,若p N是n，则p i是( )。 A. i B. n-i C. n-i+1 D. 不确定【南京理工大学 2001 一、1（1.5分）】 6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 【北方交通大学 2001 一、3（2分）】 7. 设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。【中科院计算所2000一、10(2分)】 A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， E. 3，2，1，4， 8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 【南开大学 2000 一、1】【山东大学 2001 二、4 (1分)】【北京理工大学 2000 一、2（2分）】 9. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（）。 A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 【合肥工业大学 2001 一、1（2分）】 10. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是

分章练习题--存储管理

第四章存储器管理一、填空题 1、对内存的访问是通过一系列对指定进行读或写来实现的。 2、存储器一般分为外存、和高速缓存器。 3、为了提高运算速度和增强处理能力，可以在CPU和内存之间增加______________用来存放程序和数据，CPU可以直接存取其中信息。 4、将编译或汇编后得到的一组目标模块以及它们所需的库函数装配成一个完整的装入模块的过程称为。 5、用户程序经编译之后的每个目标模块都以0为基地址顺序编址，这种地址称为。 6、内存中各存储单元的地址是从统一的基地址顺序编址，这种地址称为。 7、从用户的源程序进入系统到相应程序在机器上运行，要经历的主要处理阶段有：编辑、编译、连接和运行。 8、源程序不能在机器上直接执行，要把源程序编译成处理机能识别的二进制。 9、动态重定位是程序执行期间每次访问内存之前进行重定位，这种变换是靠实现的。 10、动态重定位是程序执行期间每次之前进行重定位，这种变换是靠硬件地址变换机构来实现的。 11、把逻辑地址转变为内存的的过程称为重定位。 12、使用存储管理固定分区法时，内存中的分区个数和都固定。 13、为了提高内存的利用率，在可重定位分区分配方式中可通过________________技术来减少内存碎片。 14、使用动态重定位法，通过紧缩可以消除碎片，但需耗费大量的。 15、紧缩是通过移动内存中的程序数据，从而使得被连成一片，这就要求动态重定位技术支持。 16、所谓对换技术，就是为了解决内存不足的问题，令作业在内存和______________之间交换。 17、某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户表中已调入

实验五动态分区存储管理

实验五动态分区存储管理一、实验目的深入了解采用动态分区存储管理方式的内存分配回收的实现。通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解，熟悉动态分区存储管理的内存分配和回收。二、实验内容编写程序完成动态分区存储管理方式的内存分配回收。具体包括：确定内存空间分配表；采用最优适应算法完成内存空间的分配和回收；编写主函数对所做工作进行测试。三、设计思路整体思路：动态分区管理方式将内存除操作系统占用区域外的空间看成一个大的空闲区。当作业要求装入内存时，根据作业需要内存空间的大小查询内存中的各个空闲区，当从内存空间中找到一个大于或等于该作业大小的内存空闲区时，选择其中一个空闲区，按作业需求量划出一个分区装人该作业，作业执行完后，其所占的内存分区被收回，成为一个空闲区。如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。设计所采用的算法：采用最优适应算法，每次为作业分配内存时，总是把既能满足要求、又是最小的空闲分区分配给作业。但最优适应算法容易出现找到的一个分区可能只比作业所需求的长度略大一点的情行，这时，空闲区分割后剩下的空闲区就很小以致很难再使用，降低了内存的使用率。为解决此问题，设定一个限值minsize，如果空闲区的大小减去作业需求长度得到的值小于等于minsize，不再将空闲区分成己分分区和空闲区两部分，而是将整个空闲区都分配给作业。内存分配与回收所使用的结构体：为便于对内存的分配和回收，建立两张表记录内存的使用情况。一张为记录作业占用分区的“内存分配表”，内容包括分区起始地址、长度、作业名/标志（为0时作为标志位表示空栏目）；一张为记录空闲区的“空闲分区表”，内容包括分区起始地址、长度、标志（0表空栏目，1表未分配）。两张表都采用顺序表形式。

内存的动态存储管理

内存的动态存储管理一、实验内容编写程序实现动态分区存储管理方式的主存分配与回收。具体内容包括：首先确定主存空间分配表；然后采用最先适应算法完成主存空间的分配与回收；最后编写主函数对所做工作进行测试二、实验原理模拟存储管理中内存空间的管理和分配内存空间的管理分为固定分区管理方式，可变分区管理方式，页式存储管理，段式存储管理。题目：模拟内存分配与回收三、实验步骤（或过程）在Microsoft Visual C++ 6.0环境下运行 1．设计一个空闲分区表，空闲分区表通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲分区低端的空间。 2．设计一个内存分区表，可用链表管理，用以表示当前以内存使用情况。 3．设计一个进程申请队列以及进程完成后的释放顺序，实现主存的分配和回收。 4．要求每次分配和回收后把空闲分区的变化情况以及各进程的申请、释放情况以及各进程的申请、释放情况以图形方式显示、打印出来。最佳适应算法：该算法总是把满足要求、又是最小的空闲区分配给作业。检查空闲区说明表是否有满足作业要求的空闲区，也分为三种情况：大于，等于，小于。若检查到有“等于”的情况，就可以直接分配，若没有，则继续检查是否有“大于”的情况

代码实现如下： #include #include #include #define n 64 //定义内存的大小 int a[n],count=0;//数组a用来保存内存使用状况1为已分配0为未分配，count用来记name 数组中元素个数 char name[n];//已分配内存的名称（字符类型） typedef struct linknode{ char pid; int start; int length; struct linknode *left,*right; }de_node; //进程节点结构体定义 //head1表示未分配内存队列头指针，head2便是已分配进程队列头指针 de_node *head1,*head2=NULL; struct linknode* creat()//创建一个进程节点 { int len,flag1=1;//用于表示进程是否可以创建 char id; struct linknode* p; p = (de_node *)malloc(sizeof(de_node));//试图在系统内存中开辟空间创建一个进程 if (p==NULL) //p为空，说明系统没有可用内存用于创建此模拟进程 { printf("系统没有足够的内存可供使用！\n");//输出 return(NULL);//返回空指针 } printf("请输入进程id(字符类型)和长度:");//为进程输入id和分配的长度 scanf("%c %d",&id,&len); fflush(stdin);//清除输入缓存 if((id>='a'&&id<='z'||id>='A'&&id<='Z')&&(len>0)){ for(int i=0;i

目前最完整的数据结构1800题包括完整答案树和二叉树答案

第6章树和二叉树部分答案解释如下。 12. 由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1，因为n=1001,所以1002=2n0+n1,在完全二叉树树中，n1只能取0或1,在本题中只能取0，故n=501，因此选E。 42.前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所以本题的A和B均对，单支树的特点是只有一个叶子结点，故C是最合适的，选C。A或B 都不全。由本题可解答44题。 47. 左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索为空（无后继），共2个空链域。 52．线索二叉树是利用二叉树的空链域加上线索，n个结点的二叉树有n+1个空链域。部分答案解释如下。 6．只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。 19．任何结点至多只有左子树的二叉树的遍历就不需要栈。 24. 只对完全二叉树适用，编号为i的结点的左儿子的编号为2i(2i<=n)，右儿子是2i+1（2i+1<=n） 37. 其中序前驱是其左子树上按中序遍历的最右边的结点（叶子或无右子女），该结点无右孩子。 38 . 新插入的结点都是叶子结点。 42. 在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点（该结点的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点（该结点的前驱指针指向祖先）。 44．非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。三.填空题

1.(1)根结点(2)左子树(3)右子树 2.(1)双亲链表表示法(2)孩子链表表示法(3)孩子兄弟表示法 3．p->lchild==null && p->rchlid==null 4.(1) ++a*b3*4-cd (2)18 5.平衡因子 6. 9 7. 12 8.(1)2k-1 (2)2k-1 9.(1)2H-1 (2)2H-1 (3)H=?log2N?+1 10. 用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结点”。设编号为i和j的结点在顺序存储中的下标为s 和t ,则结点i和j在同一层上的条件是?log2s?=?log2t?。 11. ?log2i?=?log2j?12.(1)0 (2)(n-1)/2 (3)(n+1)/2 (4) ?log2n?+1 13.n 14. N2+1 15.(1) 2K+1-1 (2) k+1 16. ?N/2? 17. 2k-2 18. 64 19. 99 20. 11 21.(1) n1-1 (2)n2+n3 22.(1)2k-2+1（第k层1个结点，总结点个数是2H-1，其双亲是2H-1/2=2k-2）(2) ?log2i?+1 23.69 24. 4 25.3h-1 26. ?n/2? 27. ?log2k?+1 28.(1)完全二叉树 (2)单枝树，树中任一结点（除最后一个结点是叶子外）,只有左子女或只有右子女。 29.N+1 30.(1) 128(第七层满，加第八层１个) (2) 7 31. 0至多个。任意二叉树，度为１的结点个数没限制。只有完全二叉树，度为１的结点个数才至多为1。 32．21 33.(1)2 (2) n-1 (3) 1 (4) n (5) 1 (6) n-1 34.(1) FEGHDCB (2)BEF（该二叉树转换成森林，含三棵树，其第一棵树的先根次序是 BEF） 35.(1)先序（2）中序 36. (1)EACBDGF （2）2 37.任何结点至多只有右子女的二叉树。 38.(1)a (2) dbe (3) hfcg 39.(1) . (2) ...GD.B...HE..FCA 40.DGEBFCA 41．(1)5 （2）略 42.二叉排序树 43.二叉树 44. 前序 45.(1)先根次序（2）中根次序46.双亲的右子树中最左下的叶子结点47.2 48.(n+1)/2 49.31（x的后继是经x的双亲y的右子树中最左下的叶结点） 50.(1)前驱 (2)后继 51.(1)1 (2)y^.lchild (3)0 (4)x (5)1 (6) y (7)x(编者注：本题按中序线索化) 52.带权路径长度最小的二叉树，又称最优二叉树 53.69 54.(1)6 (2)261 55.(1)80 (2)001（不唯一）56.2n0-1 57.本题①是表达式求值，②是在二叉排序树中删除值为x的结点。首先查找x，若没有x，则结束。否则分成四种情况讨论：x结点有左右子树；只有左子树；只有右子树和本身是叶子。 (1)Postoder_eval(t^.Lchild) (2) Postorder_eval(t^.Rchild) (3)ERROR(无此运算符)(4)A (5)tempA^.Lchild (6)tempA=NULL(7)q^.Rchild (8)q (9)tempA^.Rchild (10)tempA^.Item

实验五动态分区存储管理模拟

实验五动态分区存储管理模拟一、实验目的深入了解可变分区存储管理式主存分配回收的实现。二、实验预备知识可变分区存储管理式不预先将主存划分成几个区域，而把主存除操作系统占用区域外的空间看作一个大的空闲区。当进程要求装入主存时，根据进程需要主存空间的大小查询主存各个空闲区，当从主存空间找到一个大于或等于该进程大小要求的主存空闲区时，选择其中一个空闲区，按进程需求量划出一个分区装入该进程。进程执行完后，它所占的主存分区被回收，成为一个空闲区。如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。这个实验主要需要考虑三个问题： (1)设计记录主存使用情况的数据表格，用来记录空闲区和进程占用的区域； (2)在设计的数据表格基础上设计主存分配算法； (3)在设计的数据表格基础上设计主存回收算法。首先，考虑第一个问题：设计记录主存使用情况的数据表格，用来记录空闲区和进程占用的区域。由于可变分区的大小是由进程需求量决定的，故分区的长度是预先不固定的，且分区的个数也随主存分配和回收而变动。总之，所有分区情况随时可能发生变化，数据表格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在主存中的起始地址和长度。由于分配时空闲区有时会变成两个分区：空闲区和已分分区，回收主存分区时，可能会合并空闲分区，这样如果整个主存采用一表格记录已分分区和空闲区，就会使表格操作繁琐。主存分配

时查找空闲区进行分配，然后填写已分分区表，主要操作在空闲区；某个进程执行完成后，将该分区变成空闲区，并将其与相邻空闲区合并，主要操作也在空闲区。由此可见，主存分配和回收主要是对空闲区的操作。这样，为了便于对主存空间的分配和回收，就建立两分区表记录主存使用情况，一表格记录进程占用分区的“已分分区表”；一是记录空闲区的“空闲区表”。这两表的实现法一般有两种，一种是链表形式，一种是顺序表形式。在实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固定，所以无论是“已分分区表”还是“空闲区表”都必须事先确定长度。它们的长度必须是系统可能的最大项数，系统运行过程中才不会出错，因而在多数情况下，无论是“已分分区表”还是“空闲区表”都有空闲栏目。已分分区表中除了分区起始地址、长度外，也至少还要有一项“标志”，如果是空闲栏目，容为“空”，如果为某个进程占用分区的登记项，容为该进程的进程名；空闲区表中除了分区起始地址、长度外，也要有一项“标志”，如果是空闲栏目，容为“空”，如果为某个空闲区的登记项，容为“未分配”。在实际系统中，这两个表格的容可能还要更多，实验中仅仅使用上述必须的数据。为此，“已分分区表”和“空闲区表”在实验中有如下的结构定义：已分分区表的定义： #define n 10 //假定系统允的进程数量最多为n struct { float address; //已分分区起始地址 float length; //已分分区长度，单位为字节

目前最完整的数据结构1800题包括完整答案第五章数组和广义表

第 5 章数组和广义表一、选择题 1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。【燕山大学 2001 一、2 （2分）】 A. 13 B. 33 C. 18 D. 40 2. 有一个二维数组A[1:6，0:7] 每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组的体积是（①）个字节。假设存储数组元素A[1，0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是（②）。若按行存储，则A[2，4]的第一个字节的地址是（③）。若按列存储，则A[5，7]的第一个字节的地址是（④）。就一般情况而言，当（⑤）时，按行存储的A[I，J]地址与按列存储的A[J，I]地址相等。供选择的答案：【上海海运学院 1998 二、2 （5分）】 ①-④： A．12 B. 66 C. 72 D. 96 E. 114 F. 120 G. 156 H. 234 I. 276 J. 282 K. 283 L. 288 ⑤： A．行与列的上界相同 B. 行与列的下界相同 C. 行与列的上、下界都相同 D. 行的元素个数与列的元素个数相同 3. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( )。 A. BA+141 B. BA+180 C. BA+222 D. BA+225 【南京理工大学 1997 一、8 （2分）】 4. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（）。【福州大学 1998 一、10 (2分)】 A. 808 B. 818 C. 1010 D. 1020 5. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000 的内存单元中，则元素A[5，5]的地址是( )。【南京理工大学 2001 一、13 （1.5分）】 A. 1175 B. 1180 C. 1205 D. 1210 6. 有一个二维数组A[0:8,1:5],每个数组元素用相邻的4个字节存储，存储器按字节编址，假设存储数组元素A[0,1]的第一个字节的地址是0，存储数组A的最后一个元素的第一个字节的地址是（①）。若按行存储，则A[3,5]和 A[5,3]的第一个字节的地址是（②）和（③）。若按列存储，则A[7,1]和A[2,4]的第一个字节的地址是（④）和（⑤）。【上海海运学院 1996 二、1 （5分）】 ①-⑤:A.28 B.44 C.76 D.92 E.108 F.116 G.132 H.176 I.184 J.188 7. 将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（）。供选择的答案： A. 198 B. 195 C. 197 【北京邮电大学 1998 二、5 （2分）】 8. 二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中（）内的正确答案。（1）存放A至少需要（）个字节；（2）A的第8列和第5行共占（）个字节；（3）若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素（）的起始地

动态分区存储管理

《操作系统》课程实验报告实验名称：动态分区存储管理姓名：学号：地点：指导老师：专业班级：

一、实验目的： 1、熟悉并掌握动态分区分配的算法。 2、熟悉并掌握动态分区中分区回收的各种情况，并能够实现分区合并。二、实验内容：用高级语言模拟实现动态分区存储管理，要求： 1、分区分配算法至少实现首次适应算法、最佳适应算法和最坏适应算法中的至少一种。熟悉并掌握各种算法的空闲区组织方式。 2、分区的初始化——可以由用户输入初始分区的大小。（初始化后只有一个空闲分区，起始地址为0，大小是用户输入的大小） 3、分区的动态分配过程：由用户输入作业号和作业的大小，实现分区过程。 4、分区的回收：用户输入作业号，实现分区回收，同时，分区的合并要体现出来。（注意：不存在的作业号要给出错误提示！） 5、分区的显示：任何时刻，可以查看当前内存的情况（起始地址是什么，大小多大的分区时空闲的，或者占用的，能够显示出来） 6、要求考虑：（1）内存空间不足的情况，要有相应的显示；（2）作业不能同名，但是删除后可以再用这个名字；（3）作业空间回收是输入作业名，回收相应的空间，如果这个作业名不存在，也要有相应的提示。三、实验代码 #include #include #define SIZE 800 // 内存初始大小 #define MINSIZE 5 // 碎片最小值 enum STATE { Free, Busy }; struct subAreaNode { int addr; // 起始地址 int size; // 分区大小 int taskId; // 作业号 STATE state; // 分区状态 subAreaNode *pre; // 分区前向指针 subAreaNode *nxt; // 分区后向指针 }subHead; // 初始化空闲分区链 void intSubArea() { // 分配初始分区内存

操作系统课程设计动态分区分配存储管理

操作系统课程设计动态分区分配存储管理吕霆计算机10-01班设计题目学号专业班级学生姓名指导教师

第一章课程设计概述 1.1 设计任务: 动态分区分配存储管理 1.2 设计要求建立描述内存分配状况的数据结构；建立描述进程的数据结构；使用两种方式产生进程：（a）自动产生，（b）手工输入；在屏幕上显示内存的分配状况、每个进程的执行情况；建立分区的分配与回收算法，支持紧凑算法；时间的流逝可用下面几种方法模拟：（a）按键盘，每按一次可认为过一个时间单位； (b) 响应WM_TIMER；将一批进程的执行情况存入磁盘文件，以后可以读出并重放；支持算法：首次适应算法、循环首次适应算法、最佳适应算法：最坏适应算法。1.3 设计目的旨在让我们更好的了解动态分区管理方面的知识. 第二章原理及算法描述 2.1动态分区分配算法原理首次适应算法 * 算法概述：分配内存时，从链首开始顺序查找，找到满足的空闲分区则划出空间分配，余下的空闲空间仍保留在空闲链表中 * 实现方法：分配时从数组第一个元素开始比较，若符合条件则将该元素减去对应作业的值循环首次适应算法 * 算法概述：由首次适应算法演变，只是每次分配改为由上一次找到的空闲分区开始查找 * 实现方法：在首次适应算法的基础上增加一个值用于记录找到的空闲分区的位置最佳适应算法 * 算法概述：每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区

分配给作业 * 实现方法：我们决定每次分配先把空闲分区按从小到大的顺序排列，然后将第一个匹配分区分配给作业最坏适应算法 * 算法概述：每次为作业分配内存时，总是挑选一个最大的空闲分区分割给作业使用 * 实现方法：算法与最佳适应算法几乎相同，仅在排序时把空闲分区表按从大到小的顺序排列，所以未作详细注释回收分区当进程运行完毕释放内存时,系统根据回收区的首址,从空闲区链(表)中找到相应的插入点,此时可能出现以下四种情况之一; 1)回收区与插入点的前一个空闲分区F1相邻接,此时应将回收区与插入点的前一分区合并,不必为回收区分配新表项,而只需修改其前一分区F1的大小. 2)回收分区与插入点的后一空闲分区F2相邻接,此时也可将两分区合并,形成新的空闲分区,但用回收区的首址作为新空闲区的首址,大小为两者之和. 3)回收区同时与插入点的前,后两个分区邻接,此时将三个分区合并,使用F1的表项和F1的首址,取消F2的表项,大小为三者之和. 4)回收区既不与F1相邻接,又不与F2邻接.这时应为回收区单独建立一新表项,填写回收区的首址和大小,并根据其首址插入到空闲链中的适当位置. 紧凑算法通过移动内存中的作业的位置,以把原来多个分散的小分区拼接成一个大分区的方法. 第三章开发环境此程序是本人利用c++语言在vs2012的开发环境中实现的第四章程序实现--数据结构 #include #include #include using namespace std; ofstream stream;//输出流对象 int ary1[20][4];//内存分配状态 int ary2[20][3];//空闲分区状态 int ary3[10];//进程分配状态

动态分区存储管理的模拟实现

计算机科学与工程学院学生实验报告专业计算机科学与技术班级学号姓名课程名称操作系统课程类型专业必修课实验名称动态分区存储管理的模拟实现实验目的： 1.熟悉动态分区存储管理方式下，主存空间的分配和回收算法。 2.提高C语言编程能力。实验内容：假设主存当前状态如右表所示：系统采用最佳适应分配算法为作业分配主存空间，而且具有紧凑技术。请编程完成以下操作： (1). 输出此时的已分配区表和未分配区表； (2). 装入 Job3(15K)，输出主存分配后的已分配区表和未分配区表； (3). 回收 Job2所占用的主存空间，输出主存回收后的已分配区表和未分配区表； (4).装入 Job4(130K)，输出主存分配后的已分配区表和未分配区表。实验要求 1.数据结构参考定义如下，也可根据需要进行改进： (1)已分配区表： #define n 10 /*假定系统允许的最大作业数量为n，n值为10*/ struct {int number; /*序号*/ int address; /*已分配分区起始地址，单位为KB */ int length; /*已分配分区长度，单位KB*/ float flag; /*已分配区表登记栏标志，0：空表项，否则为作业名；*/

}used_table[n]; /*已分配区表*/ (2)未分配区表： #define m 10 /*假定系统允许的空闲区表最大为m，m值为10*/ struct {int number; /*序号*/ int address; /*空闲区起始地址，单位为KB */ int length; /*空闲区长度，单位为KB*/ int flag; /*空闲区表登记栏标志，0：空表项；1：空闲区*/ }free_table[m]; /*空闲区表*/ 2.以allocate命名主存分配所用的过程或函数（算法参考课件），要将各种情况考虑周全。 3.以reclaim命名主存回收所用的过程或函数（算法参考课件），要将各种情况考虑周全。 4.画出算法实现的N-S流程图。 5.程序调试、运行成功后，请老师检查。实验步骤： 1.分配内存，结果如下图：

动态分区存储管理系统分解

操作系统原理课程设计报告题目：动态分区分配存储管理系统所在学院：计算机科学与技术学院班级： 11级计算机科学与技术(非师) 学号： 20111202052 姓名：吴创连指导教师：黄侠剑 2014年3月18

目录 1 引言 (1) 2 需求分析 (1) 3 概要设计 (1) 4 详细设计 (1) 4.1问题描述和分析 (1) 4.2程序流程图 (2) 4.3数据结构体分析 (3) 4.4主要程序代码分析 (4) 5 调试与操作说明 (11) 5.1初始界面 (11) 5.2模拟内存分配 (12) 5.3回收内存界面 (12) 5.4最佳适应算法的实现 (13) 5.5最坏适应算法的实现 (13) 6总结与体会 (13)

1 引言操作系统是最重要的系统软件，同时也是最活跃的学科之一。我们通过操作系统可以理解计算机系统的资源如何组织，操作系统如何有效地管理这些系统资源，用户如何通过操作系统与计算机系统打交道。存储器是计算机系统的重要组成部分，近年来，存储器容量虽然一直在不断扩大，但仍不能满足现代软件发展的需要，因此，存储器仍然是一种宝贵而又紧俏的资源。如何对它加以有效的管理，不仅直接影响到存储器的利用率，而且还对系统性能有重大影响。而动态分区分配属于连续分配的一种方式，它至今仍在内存分配方式中占有一席之地。 2 需求分析动态分区分配是根据进程的实际需要，动态地为之分配内存空间。在实现动态分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配和回收操作这样三个问题。常用的数据结构有动态分区表和动态分区链。在对数据结构有一定掌握程度的情况下设计合理的数据结构来描述存储空间，实现分区存储管理的内存分配功能，应该选择最合适的适应算法（最佳适应算法，最坏适应算法），在动态分区存储管理方式中主要实现内存分配和内存回收算法，在这些存储管理中间必然会有碎片的产生，当碎片产生时，进行碎片的拼接等相关的内容。 3 概要设计本程序采用机构化模块化的设计方法，共分为两大模块。 1．最佳适应算法实现它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。 2.最坏算法实现最坏适应分配算法要扫描整个空闲分区或链表，总是挑选一个最大的空闲分区分割给作业使用。该算法要求将所有的空闲分区按其容量从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求。 4 详细设计 4.1 问题描述和分析系统应利用某种分配算法，从空闲分区链表中找到所需大小的分区，如果空闲分区大小

文档之家

数据结构1800题和答案第8章 动态存储管理