首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列算法说明和流程图,根据要求回答问题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
54
问题
阅读下列算法说明和流程图,根据要求回答问题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
软件设计师下午应用技术考试
软考中级
相关试题推荐
在各种不同的软件需求中,(36)描述了用户使用产品必须要完成的任务,可以用UML建模语言的(37)表示。(36)
下图是一个软件项目的活动图,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,则里程碑(33)在关键路径上。活动GH的松弛时间是(34)。(34)
ICMP协议属于因特网中的(27)协议,ICMP协议数据单元封装在(28)中传送。(27)
在数据库逻辑结构设计阶段,需要(20)阶段形成的(21)作为设计依据。(21)
假设某公司营销系统有营销点关系S(营销点,负责人姓名,联系方式)、商品关系P(商品名,条形码,型号,产地,数量,价格),其中,营销点唯一标识S中的每一个元组。每个营销点可以销售多种商品,每一种商品可以由不同的营销点销售。关系S和P的主键分别为(15),S
为检验某Web系统并发用户数是否满足性能要求,应进行()。
某开发小组的任务是开发一个大型软件产品的图形用户界面,宜采用()开发过程模犁。
某企业职工关系EMP(E_no,E_name,DEPT,E_addr,E_tel)中的属性分别表示职工号、姓名、部门、地址和电话;经费关系FUNDS(E_no,E_limit,E_used)中的属性分别表示职工号、总经费金额和已花费金额。若要查询部门为“开
给定包含n个正整数的数组A和正整数x,要判断数组A中是否存在两个元素之和等于x。先用插入排序算法对数组A进行排序,再用以下过程P来判断是否存在两个元素之和等于x。low=l;high=n;while(high>low)ifA[low]+A[hig
对于逻辑表达式(((a|b)‖(c>2))&&d<0),需要________________个测试用例才能完成条件组合覆盖。
随机试题
阅读材料并回答问题:如何以更好的质量实现经济社会的发展,是我们面临的也是必须要解决好的重大问题。在未来的发展中,资源环境对经济发展已构成严重制约,城乡之间、区域之间、经济与社会之间发展不平衡的矛盾趋于突出,资源相对短期、生态环境脆弱、环境容量不足
mRNA剪接过程中被去除的部分叫做
某猪场2岁种公猪,精神沉郁,步态强拘,拱背,腰部触诊敏感,常做排尿姿势。尿检可见红细胞、白细胞、盐类结晶、肾上皮细胞,该病可能的诊断是()
A.桂枝茯苓丸B.香棱丸C.启宫丸D.开郁种玉汤E.开郁二陈汤
甲河是多国河流,乙河是国际河流。根据国际法相关规则,下列哪些选项是正确的?(2011—卷一—74,多)
根据《建筑工程施工质量验收统一标准》GB50300—2013,建筑工程质量验收的最小单元是()。
根据《中华人民共和国村民委员会组织法》,村务监督委员会成员的产生方式是()。
案例下面是某求助者的WAIS-RC测验结果:根据以上测验得分,可以判断该求助者()
Manythingsmakepeoplethinkartistsareweird.Buttheweirdestmaybethis:artists’onlyjobistoexploreemotions,andyet
Yearsaftertheeconomicrecessionwitnessed_________businessrecoverythroughoutthewholenation.
最新回复
(
0
)