首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
给定一组长度为n的无序序列,将其存储在一维数组a[O..n-1]中。现采用如下方法找出其中的最大元素和最小元素:比较a[O]和a[n-1],若a[0]较大,则将二者的值进行交换;再比较a[1]和a[n-2],若a[1]较大,则交换二者的值;然后依次比较a[
给定一组长度为n的无序序列,将其存储在一维数组a[O..n-1]中。现采用如下方法找出其中的最大元素和最小元素:比较a[O]和a[n-1],若a[0]较大,则将二者的值进行交换;再比较a[1]和a[n-2],若a[1]较大,则交换二者的值;然后依次比较a[
admin
2021-01-13
41
问题
给定一组长度为n的无序序列,将其存储在一维数组a[O..n-1]中。现采用如下方法找出其中的最大元素和最小元素:比较a[O]和a[n-1],若a[0]较大,则将二者的值进行交换;再比较a[1]和a[n-2],若a[1]较大,则交换二者的值;然后依次比较a[2]和a[n-3]、 a[3]和a[n-4]、…,使得每一对元素中的较小者被交换到低下标端。重复上述方法,在数组的前n/2个元素中查找最小元素,在后n/2个元素查找最大元素,从而得到整个序列的最小元素和最大元素。上述方法采用的算法设计策略是(64)。
选项
A、动态规划法
B、贪心法
C、分治法
D、回溯法
答案
C
解析
本题考查算法设计基础知识。任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小,解题所需的计算时间往往也越少,从而也较容易处理。分治法的设计思想是:将一个难以直接解决的大问题分解成一些规模较小的相同问题,以便各个击破,分而治之。如果规模为n的问题可分解成k个子问题(1<k≤n),且这些子问题互相独立且与原问题相同。递归地求解这些问题,然后将各子问题的解合并得到原问题的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划法求解的问题,经分解得到的子问题往往不是独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,以至于最后解决原问题需要耗费指数级时间。动态规划算法,通常可按以下几个步骤进行:找出最优解的性质,并刻画其结构特征;递归地定义最优值;以自底向上的方式计算出最优值;根据计算最优值时得到的信息,构造一个最优解。回溯法有“通用的解题法”之称,用它可以系统地搜索一个问题的所有解或任一解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树。贪心法是一种不追求最优解,只希望得到较为满意解的方法。贪心法一般可以快速得到满意的解,因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心法常以当前情况为基础作最优选择,而不考虑各种可能的整体情况,所以贪心法不要回溯。
转载请注明原文地址:https://kaotiyun.com/show/wkCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明和Java代码,将应填入(n)处的字句写在答题纸的对应栏内。【说明】某大型商场内安装了多个简易的纸巾售卖机,自动售出2元钱一包的纸巾,且每次仅售出一包纸巾。纸巾售卖机的状态如图17—7所示。采用状态(State)模式来实现该纸巾售卖机,
某宾馆拟开发一个宾馆客房预订子系统,主要是针对客房的预订和入住等情况进行管理。【需求分析结果】(1)员工信息主要包括员工号、姓名、出生年月、性别、部门、岗位、住址、联系电话和密码等信息。岗位有管理和服务两种。岗位为“管理”的员工可以更改
某公司的主要业务是出租图书和唱碟。由于业务需求,该公司委托希赛公司开发一套信息管理系统。该系统将记录所有的图书信息、唱碟信息、用户信息、用户租借信息等。希赛公司决定采用面向对象的分析和设计方法开发此系统。图14-3所示为某类图书或唱碟被借阅时应记录的信息,
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某公司欲开发一个管理选民信息的软件系统。系统的基本需求描述如下:(1)每个人(Person)可以是一个合法选民(Eligible)或者无效的选民(Ineligi
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某大型匹萨加工和销售商为了有效管理生产和销售情况,欲开发一匹萨信息系统,其主要功能如下:(1)销售。处理客户的订单信息,生成销售订单,并将其记录在销售订单表中。
阅读下列说明和图,回答问题1~问题3,将解答填入答题纸的对应栏内。【说明】某网上购物平台的主要功能如下:(1)创建订单。顾客(Customer)在线创建订单(Order),主要操作是向订单中添加项目、从订单中删除项目。订单中应列出所订购的商品(Pro
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。【说明】一个无向连通图G点上的哈密尔顿(Hamiltion)回路是指从图G上的某个顶点出发,经过图上所有其他顶点一次且仅一次,最后回到该顶点的路径。哈密尔顿回路算法的基础如下:假设图G存在
ISO/IEC 9126软件质量模型中第一层定义了六个质量特性,并为各质量特性定义了相应的质量子特性,其中易分析子特性属于软件的(31)质量特性。
设计高质量的软件是软件设计追求的一个重要目标。可移植性、可维护性、可靠性、效率、可理解性和可使用性等都是评价软件质量的重要方面。可移植性反映出把一个原先在某种硬件或软件环境下正常运行的软件移植到另—个硬件或软件环境下,使该软件也能正确地运行的难易程度。为了
信息系统设计方案中的操作界面部分,特别是输入界面设计—方案需要征求信息处理技术员的意见。在如下设计理念中,(70)是不正确的。
随机试题
教学对象:初二(1)班,男、女各20人。学习内容:快速跑单元第2次课(各种跑的练习)。教学条件:篮球场2块,跳绳40根。请根据上述条件设计:(1)本次课的教学目标。(2)运用跳绳进行准备活动、各种跑的练习及身体素质练习的方法和组织形式。
系统性红斑狼疮脏器损害最常见的是()
有机磷农药口服中毒,出现症状的时间是
依据市场原则建立起来的中心地体系,上级中心地可以支配下级中心地()的商服活动。
在评估资本预算项目时,ABC公司的管理会计师想要掌握经营性收益与项目年限发生变化后对于该项目内部收益的影响。该会计师最有可能使用的方法是
与形式训练说迁移理论观点联系最为紧密的是()。
古希腊人将神塑造为生动逼真的人的形象,这在一定程度上体现了古希腊的:
若=______.
打开工作簿文件EXCEL.XLSX。选择“地区”和“总产量(吨)”两列数据区域的内容建立“簇状圆锥图”,图表标题为“水果产量统计图”,图例位置靠上;将图插入到表A12:E28单元格区域,保存EXCEL.XLSX文件。
Womenstillhaveanuneasyrelationshipwithpowerandthetraitsnecessarytobealeader.Thereisthisinternalizedfearthat
最新回复
(
0
)