首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列算法说明和流程图,根据要求回答问题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
65
问题
阅读下列算法说明和流程图,根据要求回答问题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
软件设计师下午应用技术考试
软考中级
相关试题推荐
在面向对象技术中,(43)是一组具有相同结构、相同服务、共同关系和共同语义的(44)集合,其定义包括名称、属性和操作。(44)
面向对象分析需要找出软件需求中客观存在的所有实体对象(概念),然后归纳、抽象出实体类。(26)是寻找实体对象的有效方法之一。
在IPv4向IPv6的过渡期间,如果要使得两个IPv6结点可以通过现有的IPv4网络进行通信,则应该使用(27);如果要使得纯IPv6结点可以与纯IPv4结点进行通信,则需要使用(28)。(28)
在以阶段划分的编译器中,符号表管理和()贯穿于编译器工作始终。
某指令流水线由5段组成,各段所需要的时间如下图所示。连续输入10条指令时的吞吐率为(6)。
传统编译器进行词法分析、语法分析、代码生成等步骤的处理时,前一阶段处理的输出是后一阶段处理的输入,则采用的软件体系结构风格是①。该体系结构的优点不包括②。①处应填入?
某系统中有一个中央数据存储,模块A负责接收新来的数据并修改中央数据存储中的数据,模块B负责访问中央数据存储中的数据,则这两个模块之间的耦合类型为________________。若将这两个模块及中央数据合并成一个模块,则该模块的内聚类型为_________
某软件项目的活动图如下图所示,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,边上的数字表示活动的持续时间(天),则完成该项目的最少时间为________________天。活动FG的松弛时间为________________天。
在各种不同的软件需求中,()描述了产品必须要完成的任务,可以在用例模型中予以说明。
某汽车维修公司有部门、员工和顾客等实体,各实体对应的关系模式如下:部门(部门代码,部门名称,电话)员工(员工代码,姓名,部门代码)顾客(顾客号,姓名,年龄,性别)维修(顾客号,故障情况,维修日期,员工代码)假设每个部门允许有多部电话,则电话属性为
随机试题
怎样处理车辆在行驶中车灯闪烁,喇叭呜叫?
德育的对象是受教育者,受教育者包括()
为加强土地管理,2008年6月,A省切实加大了土地调控力度,A省政府出台了《关于加强全省土地调控工作的通知》。同时还制定了相应的配套措施。一是切实做好被征地农民社会保障工作。二是制止违规集资合作建房,切实落实城镇廉租住房资金,全面建立住房保障制度。三是进一
进口设备外贸手续费的计算公式为:外贸手续费=()×人民币外汇牌价×外贸手续费率。
钢结构一级焊缝不得有()等缺陷。
期末计提短期借款利息时,应借记的账户是()。
某企业12月31日的所有者权益总额为45000万元,其中盈余公积为8000万元。由董事会提议,股东大会批准,将盈余公积200万元用于弥补当年亏损,2000万元用于转增资本(已办妥有关的转增手续)。在不考虑其他因素影响的情况下,该企业用盈余公积弥补亏损、转增
P酒店有200间客房,都是双人标准客房,但也可以出租给一个客人。2011年,客房的租金是出租给一个客人时为680元,出租给两个客人时为880元。2011年度平均客房和床位占有率分别是63%和47%,财务报表中列示的全年客房出租收入为32764986元。
Afterreachingits【21】in1990s,journalismseemstobecastinbleakandgrimprospects.Weareenduringtheworst【22】intheadv
The【B1】______profession,or"showbusiness",attractsmanyyoungpeople.【B2】______,onlyveryfewcanhopetobecomefamousand【
最新回复
(
0
)