比较分别采用数组和链表两种数据结构实现最佳适应算法和最差适应算法的优缺点(要考虑分配和释放两个过程)。

admin2016-05-14 22

问题比较分别采用数组和链表两种数据结构实现最佳适应算法和最差适应算法的优缺点(要考虑分配和释放两个过程)。

选项

答案实现最佳适应算法时，空闲存储区管理表的组织方法可以采用顺序结构，也可采用链接结构。如采用顺序结构，空闲分区按地址由小到大的顺序登记在表中，分配时需要搜索所有的空闲分区，以在其中挑出一个满足分配大小的最小的分区，其算法的时间复杂度为O(N)。此种管理结构的释放算法可用顺序结构的首次适应法，不需要插入或删除一个空闲分区表项时，其时间复杂度为O(1)，否则其算法的时间复杂度为O(N)。当采用链接结构时，空闲区也可按由小到大的非递减次序排列。分配时总是从最小的第一项开始，这样第一次找到的满足条件的空闲区必定是最合适的。平均而言，只要搜索一半数目的空闲区表项就能找到最佳配合的空闲区，但寻找较大空闲区比较费时，其算法的时间复杂度为0(N)。采用按存储区大小排序的链接表会降低释放算法的效率。由于空闲区是按大小而不是按地址序号排序的，因此释放回收空闲区时要在整个链表上寻找地址相邻的前、后空闲区，合并后又要插入到合适的位置，因此释放算法比首次适应法和循环首次适应法耗时得多，尽管其算法的时间复杂度也为O(N)，但其常数C要大得多。实现最差适应算法时的空闲存储区表的组织方法一般都是采用按空闲块由大到小排序的链接表，因为如果采用按地址大小的顺序结构，那么该算法与首次适应法和最佳适应法比较起来就没有什么优点可言了。采用按存储区大小顺序排列的链接表的形式，虽然释放一个空闲块时速度较慢，算法的时间复杂度也为O(N)，但分配时一次查找就行，成功不成功在此一举，算法的时间复杂度为O(1)，其效率是一切算法中最高的一种，很适合实时系统。

解析

转载请注明原文地址:https://kaotiyun.com/show/BONx777K

本试题收录于：操作系统题库理工类分类

操作系统

理工类

相关试题推荐

随机试题

最新回复(0)

比较分别采用数组和链表两种数据结构实现最佳适应算法和最差适应算法的优缺点(要考虑分配和释放两个过程)。

操作系统

理工类

计算机网络安全是指利用管理控制和技术措施，保证在一个网络环境里，信息数据的__________、完整性及可使用性受到保护。()

在入侵检测分析模型中，状态转换方法属于___________检测。

系统型病毒一般传染硬盘___________和磁盘DOS引导扇区。

在计算机病毒检测手段中，下面关于特征代码法的表述，错误的是()

NAT有三种类型：静态NAT、动态地址NAT和___________。

库存管理的目标主要是保证企业按科学的计划实现_生产，并且使_达到最低。

设备的动态分配算法有利于提高设备的利用率，但如果使用不当，则有可能造成________。

在一页式存储管理的系统中，内存容量为128KB，被划分为64块，若按下列页表，试求出有效逻辑地址4567所对应的物理地址。页号块号02142638437

在组通信中，组是定义为在某一系统中相互有关系的________的集合。

静态测试指被测试程序不在机器上运行，而是采用_________和计算机辅助静态分析的手段对程序进行检测。

个人品德的形成。

关于溶血性贫血的定义，下列正确的是

公正不仅指形式上的类似，更强调公正的

(2007年)当RLC串联电路发生谐振时，一定有()。

高处作业时，安全网应随着建筑物升高而提高，安全网距离工作面的最大高度不超过()m。

巴洛克建筑发展到后期成为超级巴洛克建筑，后来在以下哪个西方殖民地地区流行_______。

若有关系（课程编号，课程名称，学号，姓名，成绩），要得到关系中有多少门不同的课程名称，应使用的关系运算是

IcametoliveherewhereIamnowbetweenWoundedKneeCreekandGrassCreek.Otherscametoo,andwemadetherelittlegrayho

比较分别采用数组和链表两种数据结构实现最佳适应算法和最差适应算法的优缺点(要考虑分配和释放两个过程)。

操作系统

理工类

计算机网络安全是指利用管理控制和技术措施，保证在一个网络环境里，信息数据的__________、完整性及可使用性受到保护。()

在入侵检测分析模型中，状态转换方法属于___________检测。

系统型病毒一般传染硬盘___________和磁盘DOS引导扇区。

在计算机病毒检测手段中，下面关于特征代码法的表述，错误的是()

NAT有三种类型：静态NAT、动态地址NAT和___________。

库存管理的目标主要是保证企业按科学的计划实现_______生产，并且使_______达到最低。

设备的动态分配算法有利于提高设备的利用率，但如果使用不当，则有可能造成________。

在一页式存储管理的系统中，内存容量为128KB，被划分为64块，若按下列页表，试求出有效逻辑地址4567所对应的物理地址。页号块号02142638437

在组通信中，组是定义为在某一系统中相互有关系的________的集合。

静态测试指被测试程序不在机器上运行，而是采用_________和计算机辅助静态分析的手段对程序进行检测。

个人品德的形成。

关于溶血性贫血的定义，下列正确的是

公正不仅指形式上的类似，更强调公正的

(2007年)当RLC串联电路发生谐振时，一定有()。

高处作业时，安全网应随着建筑物升高而提高，安全网距离工作面的最大高度不超过()m。

巴洛克建筑发展到后期成为超级巴洛克建筑，后来在以下哪个西方殖民地地区流行_______。

若有关系（课程编号，课程名称，学号，姓名，成绩），要得到关系中有多少门不同的课程名称，应使用的关系运算是

IcametoliveherewhereIamnowbetweenWoundedKneeCreekandGrassCreek.Otherscametoo,andwemadetherelittlegrayho

库存管理的目标主要是保证企业按科学的计划实现_生产，并且使_达到最低。