首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
比较分别采用数组和链表两种数据结构实现最佳适应算法和最差适应算法的优缺点(要考虑分配和释放两个过程)。
比较分别采用数组和链表两种数据结构实现最佳适应算法和最差适应算法的优缺点(要考虑分配和释放两个过程)。
admin
2016-05-14
20
问题
比较分别采用数组和链表两种数据结构实现最佳适应算法和最差适应算法的优缺点(要考虑分配和释放两个过程)。
选项
答案
实现最佳适应算法时,空闲存储区管理表的组织方法可以采用顺序结构,也可采用链接结构。如采用顺序结构,空闲分区按地址由小到大的顺序登记在表中,分配时需要搜索所有的空闲分区,以在其中挑出一个满足分配大小的最小的分区,其算法的时间复杂度为O(N)。此种管理结构的释放算法可用顺序结构的首次适应法,不需要插入或删除一个空闲分区表项时,其时间复杂度为O(1),否则其算法的时间复杂度为O(N)。 当采用链接结构时,空闲区也可按由小到大的非递减次序排列。分配时总是从最小的第一项开始,这样第一次找到的满足条件的空闲区必定是最合适的。平均而言,只要搜索一半数目的空闲区表项就能找到最佳配合的空闲区,但寻找较大空闲区比较费时,其算法的时间复杂度为0(N)。采用按存储区大小排序的链接表会降低释放算法的效率。由于空闲区是按大小而不是按地址序号排序的,因此释放回收空闲区时要在整个链表上寻找地址相邻的前、后空闲区,合并后又要插入到合适的位置,因此释放算法比首次适应法和循环首次适应法耗时得多,尽管其算法的时间复杂度也为O(N),但其常数C要大得多。 实现最差适应算法时的空闲存储区表的组织方法一般都是采用按空闲块由大到小排序的链接表,因为如果采用按地址大小的顺序结构,那么该算法与首次适应法和最佳适应法比较起来就没有什么优点可言了。采用按存储区大小顺序排列的链接表的形式,虽然释放一个空闲块时速度较慢,算法的时间复杂度也为O(N),但分配时一次查找就行,成功不成功在此一举,算法的时间复杂度为O(1),其效率是一切算法中最高的一种,很适合实时系统。
解析
转载请注明原文地址:https://jikaoti.com/ti/XYEaFFFM
本试题收录于:
操作系统题库理工类分类
0
操作系统
理工类
相关试题推荐
下列说法中,符合CIDF体系结构原理的说法是()
简述攻击型漏洞探测的工作原理及特性。
恶意代码的关键技术主要有:生存技术、___________和隐藏技术。
执行入侵检测任务的硬件或软件统称为___________。
运筹学是一门研究如何有效地组织和管理_______的科学。()
运筹学是一门研究如何有效地组织和管理_______的科学。()
在网络操作系统中,由一组计算机构成的逻辑组织单元称为()
所谓原语就是只具有某种功能,运行时有________的小段程序。
对线性顺序访问地址空间最理想的页面置换算法是________。
静态测试指被测试程序不在机器上运行,而是采用_________和计算机辅助静态分析的手段对程序进行检测。
随机试题
钱澄之后期诗歌的特点是【】
佛教禅宗的______观点,启发理学家以人格的自我完善为齐家治国的出发点,以遵循“天理”为人格完善的唯一途径。()
A.候肺之气B.候胸中之气C.候心之气D.候肾之气三部九侯诊法中“中部天”的诊断意义是
采用投资收益率指标评价投资方案经济效果的缺点是()。
下列各项中,不属于利润分配核算业务的是()。
你对下属的基层部门下发一项活动的通知,先收到通知的部门提醒你,这个通知与原来你发的另一项工作时间上有冲突,你会怎么做?
工农民主政权时期最早确立8小时工作制的政策文件是()。
1938年5月至6月,毛泽东发表《论持久战》的讲演,总结抗战10个月来的经验,集中全党智慧,系统地阐明了持久抗战的总方针。这一方针
[*]
Whichgraphisthemantalkingabout?
最新回复
(
0
)