首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列算法说明和流程图,根据要求回答问题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
66
问题
阅读下列算法说明和流程图,根据要求回答问题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)表示。(37)
标识符在高级语言源程序中的作用不包括______。
以下关于软件测试原则的叙述中,正确的是______。①测试开始得越早,越有利于发现缺陷②测试覆盖率和测试用例数量成正比③测试用例既需选用合理的输入数据,又需要选择不合理的输入数据④应制定测试计划并严格执行,排除随意性
某企业研发信息系统的过程中,______不属于数据库管理员(DBA)的职责。
对现有软件系统中一些数据处理的算法进行改进,以提高效率,从而更快地响应用户的服务要求。这种行为属于____________维护。
下述说法错误的是(46)。
某软件项目的活动图如下图所示,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,边上的数字表示活动的持续时间(天)。活动EH最多可以晚开始①天而不影响项目的进度。由于某种原因,现在需要同一个工作人员完成BC和BD,则完成该项目的最少时间为②天
在结构化分析方法中,用于行为建模的模型是①,其要素包括②。①处应填入?
根据《计算机软件保护条例》的规定,著作权法保护的计算机软件是指________________。
下面为C语言程序,边界值问题可以定位在(45)。 int data(3), int i, for(i=1, i<=3, i++)data(i)=100
随机试题
在Windows7资源管理器的文件属性对话框中,除了可以设置文件的只读、隐藏属性外,可以通过“高级属性”对话框进行设置的文件属性有________。
讲授法
凡是承认世界具有统一性的哲学都属于()
患儿男性,5岁,因“发热、咳嗽6天,胸痛3天”入院。6天前受凉后出现发热,最高40.6℃,伴畏寒,咳嗽较剧烈。干咳为主,痰不易咳出。2天前出现左侧胸痛,持续性,有时诉腹痛,部位不固定,可忍受,为钝痛。当地医院予头孢曲松钠静脉输液2天,症状无明显改善。病来患
姜黄的功效是牛膝的功效是
环境随机振动法是当前实桥振型测定常用和较为有效的方法。()
下列哪个软件是专业刻录软件?()
Imagineaworldinwhichweareassignedanumberthatindicateshowinfluentialweare.Thisnumberwouldhelpdetermine【C1】___
表达式{∧2005-10-310:0:0}-{∧2005-10-39:0:0}的数据类型是【】。
Somecoupleshireaweddingplannerwhilemanyorganizetheirweddingthemselves.
最新回复
(
0
)