首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
给定一组长度为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
29
问题
给定一组长度为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://jikaoti.com/ti/PdG7FFFM
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明和Java代码,将应填入(n)处的字句写在答题纸的对应栏内。【说明】某公司的组织结构图如图17—9所示,现采用组合(Composition)设计模式来设计,得到如图17—10所示的类图。其中Company为抽象类,定义了在组织结构图上添
阅读下列说明和图,回答问题1~问题3,将解答填入答题纸的对应栏内。【说明】Pay&Drive系统(开多少付多少)能够根据驾驶里程自动计算应付的费用。系统中存储了特定区域的道路交通网的信息。道路交通网由若干个路段(RoadSeg
阅读下列说明和C代码,回答【问题1】至【问题3】,将解答写在答题纸的对应栏内。【说明】采用归并排序对n个元素进行递增排序时,首先将n个元素的数组分成各含n/2个元素的两个子数组,然后用归并排序对两个子数组进行递归排序,最后合并两个已经排
阅读下列说明,回答问题。【说明】某省针对每年举行的足球联赛,拟开发一套信息管理系统,以方便管理球队、球员、主教练、主裁判、比赛等信息。【需求分析】(1)系统需要维护球队、球员、主教练、主裁判、比赛等信息。球队信息主要包括:球队编号
阅读下列说明和C++代码,将应填入___________(n)处的字句写在答题纸的对应栏内。【说明】某大型购物中心欲开发一套收银软件,要求其能够支持购物中心在不同时期推出的各种促销活动,如打折、返利(例如,满300返100)等。现采用策略(Strate
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。【说明】假币问题:有n枚硬币,其中有一枚是假币,已知假币的重量较轻。现只有一个天平,要求用尽量少的比较次数找出这枚假币。【分析问题】将n枚硬币分成相等的两部分:(1)当n为偶数时,将
阅读下列说明,回答问题,将解答填入答题纸的对应栏内。【说明】某创业孵化基地管理若干孵化公司和创业公司,为规范管理创业项目投资业务,需要开发一个信息系统。请根据下述需求描述完成该系统的数据库设计。【需求描述】(1)记录孵化公司和创业公司的信息。孵化
某软盘有40个磁道,磁头从一个磁道移至另一个磁道需要5ms。文件在磁盘上非连续存放,逻辑上相邻数据块的平均距离为10个磁道,每块的旋转延迟时间及传输时间分别为100ms 25ms,则读取一个100块的文件需要(24)时间。
文法G=({E),{+,*,(,),a},P,E),其中P由下列产生式组成E->E+E|E*E|(E)|a。它生成由a,+,*,(,)组成的算术表达式,该文法在乔姆斯基分层中属于(16)型文法,其对应的自动机是(17),如产生句子a*a+a,它的派生树是(
下列关于dpi的叙述中,(58)是正确的。 ①每英寸的bit数 ②每英寸像素点 ③dpi越高图像质量越低 ④描述分辨率的单位
随机试题
A.阳胜则热,阴胜则寒B.阳虚则寒,阴虚则热C.阴盛格阳,阳盛格阴D.阴损及阳,阳损及阴寒热真假证的病机是
使用固体催化剂时一定要防止其中毒,若中毒后其活性可以重新恢复的中毒是()。
可直接激活蛋白激酶C的物质是
寒邪的特点是
将会使债券的发行利率提高的因素有()。
地陪在带领旅游团用第一餐时,应做好的工作有()。
随着现代科技的飞速发展,玩微信、晒微博、软件打车、软件预约家政、互联网支付等新生事物正逐渐融人和改变着人们的生活,但是这些新生事物在带来便利的同时也造成了一些社会问题,政府为此也正在制定相关举措引导他们正常发展。这种情况说明()。
罗杰斯的“有意义学习”与奥苏伯尔的“有意义学习”的区别在于()
清朝的灭亡给中国带来了一个真正的时代,社会震荡,世事忙乱,人们也没有心思去品咂一下这次历史变更的苦涩原味,匆匆忙忙赶路去了。直到1927年6月1日。大学者王国维先生在颐和园投水而死,才让全国的有心人肃然深思。王国维先生的死因众说纷纭,我们且
设f(x)是在区间[1,+∞)上单调减少且非负的连续函数,an=一1nf(x)dx(n=1,2,…).证明:证存在;
最新回复
(
0
)