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

admin2016-05-14 39

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

选项

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

解析

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

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

操作系统

理工类

相关试题推荐

随机试题

最新回复(0)

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

操作系统

理工类

一般地，入侵检测系统需要解决两个问题，一是如何充分并可靠地提取描述行为特征的数据，二是如何根据特征数据，高效并准确地判定____________。

网络系统可能存在的安全威胁主要来自哪些方面?

按照漏洞探测的技术特征，漏洞探测技术可以分为___________、基于主机的探测技术、基于目标的探测技术和基于网络的探测技术。

数字签名技术是一种实现___________认证和身份认证的重要技术。()

计算机网络系统面临的典型安全威胁中窃听指的是()

一般的，计算机病毒都是由___________从系统获取控制权，引导病毒的其他部分工作。()

试图把自己的程序加入或取代部分操作系统进行工作，具有很强的破坏力，可以导致整个系统瘫痪的病毒是___________。()

企业价格决策的目标是_______。

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

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

根据埃里克森的人格发展阶段理论，中学生人格发展的主要任务是获得()

患者，女性，婚后夫妇同居4年，未避孕而未受孕应属

咸秋石易胆矾易

依法对药品生产过程进行的审查、许可认证、检查的监督管理活动是国家药监局可根据需要直接组织对药品生产企业进行

下列各项中，不属于影响公司资本成本的因素是()。

根据《宪法》第一百一十一条的规定，城市和农村按居民居住地区设立的居民委员会或者村民委员会是基层()。

评估求助者一般心理健康水平时不正确的是()。(2004年6月三级真题)

班主任了解学生的内容不包括()。

Howoftenonehearschildrenwishingtheyweregrown—upsandoldpeoplewishingtheywere46again．Eachagehasitspleasureandi