首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
给定一组长度为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
35
问题
给定一组长度为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
软件设计师上午基础知识考试
软考中级
相关试题推荐
某基于微处理器的住宅系统,使用传感器(如红外探头、摄像头等)来检测各种意外情况,如非法进入、火警、水灾等。房主可以在安装该系统时配置安全监控设备(如传感器、显示器、报警器等),也可以在系统运行时修改配置,通过录像机和电视机监控与系统连接的所有传感
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某医院拟开发一套住院病人信息管理系统,以方便对住院病人、医生、护士和手术等信息进行管理。【需求分析】(1)系统登记每个病人的住院信息,包括:病
阅读下列说明和图,回答问题。【说明】某物品拍卖网站为参与者提供物品拍卖平台,组织拍卖过程,提供在线或线下交易服务。网站主要功能描述如下:(1)拍卖参与者分为个人参与者和团体参与者两种。不同的团体也可以组成新的团体参与拍卖活动。网站记录每个参与
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。【说明】假币问题:有n枚硬币,其中有一枚是假币,已知假币的重量较轻。现只有一个天平,要求用尽量少的比较次数找出这枚假币。【分析问题】将n枚硬币分成相等的两部分:(1)当n为偶数时,将
某仓库有两名发货员,一名审核员。当顾客提货时,只要发货员空闲,允许顾客进入仓库提货,顾客离开时,审核员检验顾客提货是否正确。其工作流程如右下图所示。为了利用PV操作正确地协调他们之间的工作,设置了两个信号量S1和S2,且S1的初值为2, S2的初值为1。图
实体联系模型(简称ER模型)中的基本语义单位是实体和联系。ER模型的图形表示称为ER图。联系可以同(37)实体有关。实体与实体之间的联系可以是(38)。利用ER模型进行数据库的概念设计,可以分成3步:首先设计局部ER,然后把各个局部ER模型综合成一个全局
软件测试是软件质量保证的主要手段之一,测试的费用已超过(10)的30%以上。因此提高测试的有效性非常重要。“高产”的测试是指(11)。根据国家标准GB8566-88计算机软件开发规范的规定,软件的开发和维护分为8个阶段,其中单元测试是在(12)阶段完成的;
信息系统设计方案中的操作界面部分,特别是输入界面设计—方案需要征求信息处理技术员的意见。在如下设计理念中,(70)是不正确的。
信息系统设计方案中的操作界面部分,特别是输入界面设计方案需要征求信息处理技术员的意见。在如下设计理念中,(66)是不正确的。
随机试题
某工业生产企业委托评估机构对其自用的办公用房(含办公楼和土地)进行抵押评估,评估基准日为2020年6月30日,评估对象基本情况,土地面积2200平方米,于2012年6月30日通过出让方式获得:房屋建筑面积为7700平方米,于2014年6月30日竣工投入使用
快餐:中式快餐:日式快餐
A.20%甘露醇B.5%碳酸氢钠C.大量生理盐水D.20%甘露醇或5%碳酸氢钠E.不可使用20%甘露醇或5%碳酸氢钠代谢性酸中毒宜用
以下因素与特发性血小板减少性紫癜发病无关的是
A.轻宣凉燥,理肺化痰B.增液润燥C.清养肺胃,降逆下气D.清宣温燥,润肺止咳E.清肺润燥,益气养阴桑杏汤的功效为
下列选项中,适合企业采用集中化战略的是()。
下列各项中,不属于按照“服务业”税目征收营业税的项目是()。
法律关系有纵向法律关系和横向法律关系之分,在以下法律关系中,属于横向法律关系的有哪些?()
BROWSE命令的作用是()。
AccommodationNearthetowncentre-SingleroomsavailableSunningdaleHotelFrench,German,SpanishandRussianspoken£150per
最新回复
(
0
)