首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
比较分别采用数组和链表两种数据结构实现最佳适应算法和最差适应算法的优缺点(要考虑分配和释放两个过程)。
比较分别采用数组和链表两种数据结构实现最佳适应算法和最差适应算法的优缺点(要考虑分配和释放两个过程)。
admin
2016-05-14
40
问题
比较分别采用数组和链表两种数据结构实现最佳适应算法和最差适应算法的优缺点(要考虑分配和释放两个过程)。
选项
答案
实现最佳适应算法时,空闲存储区管理表的组织方法可以采用顺序结构,也可采用链接结构。如采用顺序结构,空闲分区按地址由小到大的顺序登记在表中,分配时需要搜索所有的空闲分区,以在其中挑出一个满足分配大小的最小的分区,其算法的时间复杂度为O(N)。此种管理结构的释放算法可用顺序结构的首次适应法,不需要插入或删除一个空闲分区表项时,其时间复杂度为O(1),否则其算法的时间复杂度为O(N)。 当采用链接结构时,空闲区也可按由小到大的非递减次序排列。分配时总是从最小的第一项开始,这样第一次找到的满足条件的空闲区必定是最合适的。平均而言,只要搜索一半数目的空闲区表项就能找到最佳配合的空闲区,但寻找较大空闲区比较费时,其算法的时间复杂度为0(N)。采用按存储区大小排序的链接表会降低释放算法的效率。由于空闲区是按大小而不是按地址序号排序的,因此释放回收空闲区时要在整个链表上寻找地址相邻的前、后空闲区,合并后又要插入到合适的位置,因此释放算法比首次适应法和循环首次适应法耗时得多,尽管其算法的时间复杂度也为O(N),但其常数C要大得多。 实现最差适应算法时的空闲存储区表的组织方法一般都是采用按空闲块由大到小排序的链接表,因为如果采用按地址大小的顺序结构,那么该算法与首次适应法和最佳适应法比较起来就没有什么优点可言了。采用按存储区大小顺序排列的链接表的形式,虽然释放一个空闲块时速度较慢,算法的时间复杂度也为O(N),但分配时一次查找就行,成功不成功在此一举,算法的时间复杂度为O(1),其效率是一切算法中最高的一种,很适合实时系统。
解析
转载请注明原文地址:https://kaotiyun.com/show/BONx777K
本试题收录于:
操作系统题库理工类分类
0
操作系统
理工类
相关试题推荐
作为一个防护体系,当入侵者要发起攻击时,每一步都需要花费时间,攻击成功花费的时间就是___________。
若X企业的网络系统拓扑结构如下图所示,请尝试对X企业的网络安全解决方案进行分析。
在计算机病毒检测手段中,下面关于特征代码法的表述,错误的是()
简述攻击型漏洞探测的工作原理及特性。
从工作原理角度看,防火墙主要可以分为哪两类?防火墙的主要实现技术有哪些?
某厂计划生产甲、乙两种产品,具体情况如下:试建立能获得最大利润的生产计划内线性规划模型,并列出其单纯形初表。
在求最大流量问题中,已知从起点到它相邻的三个结点每分钟最多可通过30,25,40辆汽车,则从终点每分钟可输出的汽车辆数是()
假设要用解线性规划问题的单纯形法来求解某个具有n行(n个供应者)m列(m个需求点)的运输问题,则在构成这线性规划问题的模型中,必须具有()
进程存在的唯一标志是()
任何一个文件使用前都要先打开,即把________送到内存。
随机试题
创造有高度审美价值的艺术意象是一切艺术家的共同目标,这从中西美学哪些论题中可以看出?()
小儿肠套叠的诊断依据
走黄与内陷的病机主要区别是
A、白细胞B、红细胞管型C、乳糜尿D、血红蛋白尿E、胆红素尿血管内溶血时,尿中可见()。
色调主要分为()。
某镇居民喜食鸡肉和羊肉,近几年镇政府大力提倡发展养鸡业,市场上鸡肉供给大幅增加。假定羊肉供给未变,这会使()。①鸡肉价格下降,需求量增加②羊肉价格上升,需求量增加③鸡肉需求量减少,价格上升④羊肉需求量减少。价格下降
犯罪预备与犯罪未遂的主要区别在于________实行犯罪与否。
A、 B、 C、 D、 A
Inthesimplestterms,amarketistheplacewheresellermeetsbuyertoexchangeproductsformoney.Traditionalmarketsstill
A、Employfewerstaff.B、Keepcustomerwaitlonger.C、Payattentiontoonlinesales.D、Chargemoreshippingfees.C四个选项与新闻中的几条商家策
最新回复
(
0
)