首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列算法说明和流程图,根据要求回答问题1~问题3。 [说明] 某机器上需要处理n个作业job1,job2,…,jobn,其中: (1)每个作业jobi(1≤i≤n)的编号为i,jobi有一个收益值P[i]和最后期限值d[i];
阅读下列算法说明和流程图,根据要求回答问题1~问题3。 [说明] 某机器上需要处理n个作业job1,job2,…,jobn,其中: (1)每个作业jobi(1≤i≤n)的编号为i,jobi有一个收益值P[i]和最后期限值d[i];
admin
2010-01-15
46
问题
阅读下列算法说明和流程图,根据要求回答问题1~问题3。
[说明]
某机器上需要处理n个作业job1,job2,…,jobn,其中:
(1)每个作业jobi(1≤i≤n)的编号为i,jobi有一个收益值P
和最后期限值d
;
(2)机器在一个时刻只能处理一个作业,而且每个作业需要一个单位时间进行处理,一旦作业开始就不可中断,每个作业的最后期限值为单位时间的正整数倍;
(3)job1~jobn的收益值呈非递增顺序排列,即p[1]≥p[2]≥…≥p[n];
(4)如果作业jobi在其期限之内完成,则获得收益p
;如果在其期限之后完成,则没有收益。
为获得较高的收益,采用贪心策略求解在期限之内完成的作业序列。图3-25是基于贪心策略求解该问题的流程图。
(1)整型数组J[]有n个存储单元,变量k表示在期限之内完成的作业数,J[1..k]存储所有能够在期限内完成的作业编号,数组J[1..k)里的作业按其最后期限非递减排序,即d[J[1]]≤…≤d[J[k]]。
(2)为了便于在数组J中加入作业,增加一个虚拟作业job0,并令d[0]=0,J[0]=0。
(3)算法大致思想是:先将作业job1的编号1放入J[1],然后,依次对每个作业jobi(2≤i≤n)进行判定,看其能否插入到数组J中。若能,则将其编号插入到数组J的适当位置,并保证J中作业按其最后期限非递减排列;否则不插入。
jobi能插入数组J的充要条件是:jobi和数组J中已有作业均能在其期限之内完成。
(4)流程图中的主要变量说明如下。
i:循环控制变量,表示作业的编号;
k:表示在期限内完成的作业数;
r:若jobi能插入数组J,则其在数组J中的位置为r+1;
q:循环控制变量,用于移动数组J中的元素。
选项
答案
这是一道考查贪心算法的流程图分析的试题。(1)空缺处表示第2个作业到第n个作业的主循环的条件判断,由于i是循环控制变量,因此(1)空缺处所填写的内容是i<=h。 注意到题干中给出的关键信息“J[1..k)存储所有能够在期限内完成的作业编号,数组J[1..k]里的作业按其最后期限非递减排序,即[*]”。换言之,数组J中的作业J[i](1≤i≤k)是在其期限之前完成的作业,且[*]。由图3-25给出的算法流程图可知,主循环内嵌套了两个循环,第1个循环判断当前考虑的作业i应该插入到J中的什么位置,用循环控制变量r表示当前考虑的J中的作业。使用虚拟作业J[0],允许作业较方便地插入到第1个位置。为了保证J中的作业期限按升序排序,作业J[r]若比作业i的期限大,则循环控制变量r要自减,因此(2)空缺处所填写的内容是d[J[r]]>d[i]。 d[J[r]]与r的关系只有两种:d[J[r]]>r,表示还可能在J[1]与J[r]之间插入作业“d[J[r]]=r,表示不可以在J[1]~J[r]之间插入作业i。d[J[r]]<r的情况不会存在,因为J中若有r个作业,那么最后一个作业的期限不可能小于r。当作业i大于等于作业J[r]的期限时,此时找到了作业i插入的位置,即r+1。第2个循环的作用是将作业J[r+1]……J[k]依次往后移动,此处用插入排序算法的思想。最后把作业i插入到 J[r+1]处,因此(3)空缺处所填写的内容是J[r+1]=i(或J[q+1]=i)。
解析
转载请注明原文地址:https://kaotiyun.com/show/RcDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
某公司采用的软件开发过程通过了CMM2认证,表明该公司(30)。
关于软件著作权产生的时间,表述正确的是(10)。
在统一建模语言(UML)中,描述系统与外部系统及用户之间交互的图是(8)。
计算机各功能部件之间的合作关系如下图所示。假设图中虚线表示控制流,实线表示数据流,那么a、b和c分别表示(5)。
软件测试按实施组织分,测试应该包括以下的(50)。①开发方测试②用户方测试③第三方测试④验收测试⑤确认测试
______不属于易用性测试范畴。A.软件产品使用户能理解软件是否合适以及如何能将软件用于特定的任务和使用条件的能力B.软件产品使用户能操作和控制它的能力C.对软件中的缺陷或失效原因进行诊断,或识别待修改部分的能力D.软件产品吸引用户的能力
某企业职工关系EMP(E_no,E_name,DEPT,E_addr,E_tel)中的属性分别表示职工号、姓名、部门、地址和电话;经费关系FUNDS(E_no,E_limit,E_used)中的属性分别表示职工号、总经费金额和已花费金额。若要查询部门为“开
编译和解释是实现高级程序设计语言的两种方式,其区别主要在于______。
ISO/IEC9126《软件工程产品质量》统一了多种质量模型。其中,下述关于软件使用质量的描述,不正确的是______。A.它测量用户在特定环境中能达到其目标的程度,不是测量软件自身的属性B.使用质量的属性分为4个特性:有效性、生产率、安全性和满意度
某汽车维修公司有部门、员工和顾客等实体,各实体对应的关系模式如下:部门(部门代码,部门名称,电话)员工(员工代码,姓名,部门代码)顾客(顾客号,姓名,年龄,性别)维修(顾客号,故障情况,维修日期,员工代码)假设每个部门允许有多部电话,则电话属性为
随机试题
枳实薤白桂枝汤中桂枝的作用
A.肝气上逆证B.胃气上逆证C.肺气上逆证D.肾气不固证E.脾气下陷证
A、禁止使用肟类复能剂B、不宜用肥皂水清洗皮肤C、静注毒扁豆碱D、及早大量使用维生素B6E、用解氟灵异烟肼中毒()。
费德勒认为影响领导方式有效性的情境因素包括()。
2008年北京奥运会上争夺奖牌的事实,使我们明白了一个道理:在失败还未成为最后的事实时,决不能轻易接受失败!在胜利尚存一丝微弱的希望时,仍要拼尽全力去争取胜利!否则,就不是真正的强者。由上述题干可推出以下哪个选项?
陕西出土的秦始皇兵马俑,其表面涂有生漆和彩绘,这为研究秦代军人的服色提供了重要信息。但兵马俑出土后,表面的生漆会很快发生翘皮和卷曲,造成整个彩绘层脱落,因此,必须用防护液和单体渗透两套方法进行保护,否则不能供研究使用。而一旦采用这两套方法对兵马俑进行保护,
组成计算机硬件系统的基本部分是()。
Whatdoesthewomanwantthemantodo?
A、Onlybreakfast.B、Onlylunch.C、Onlysupper.D、Alloftheabove.C由第二段中“Thesecartsservedlate-nightworkerswhowantedacup
DevelopinganAdvertisingCampaignGenerallyspeaking,fourmajorstepsareinvolvedinthedevelopmentofanadvertisingca
最新回复
(
0
)