首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在有n个无序无重复元素值的数组中查找第i小的数的算法描述如下:任意取一个元素r,用划分操作确定其在数组中的位置,假设元素r为第k小的数。若i等于k,则返回该元素值;若i小于k,则在划分的前半部分递归进行划分操作找第i小的数;否则在划分的后半部分递归进行划分
在有n个无序无重复元素值的数组中查找第i小的数的算法描述如下:任意取一个元素r,用划分操作确定其在数组中的位置,假设元素r为第k小的数。若i等于k,则返回该元素值;若i小于k,则在划分的前半部分递归进行划分操作找第i小的数;否则在划分的后半部分递归进行划分
admin
2012-05-21
71
问题
在有n个无序无重复元素值的数组中查找第i小的数的算法描述如下:任意取一个元素r,用划分操作确定其在数组中的位置,假设元素r为第k小的数。若i等于k,则返回该元素值;若i小于k,则在划分的前半部分递归进行划分操作找第i小的数;否则在划分的后半部分递归进行划分操作找第k-i小的数。该算法是一种基于______策略的算法。
选项
A、分治
B、动态规划
C、贪心
D、回溯
答案
A
解析
本题考查算法的设计策略。从题干可以看出,划分操作与快速排序中的划分操作是一样的,确定某个元素如r的最终位置,划分后,在r之前的元素都小于r,在r之后的元素都大于r(假设无重复元素)。因此可以据此确定r是数组中第几小的数。题干所述的算法把找第i小的数转换为确定任意一个元素是第几小的数,然后根据这个结果再在依据该元素划分后得到的结果在前一部分还是后一部分来继续确定某个元素为第几小的数,重复这种处理,直到找到第i小的数。这是分治策略的一个典型应用。
转载请注明原文地址:https://kaotiyun.com/show/GzRZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
宽带综合业务数字网B-ISDN的数据通信服务主要采用(53)。
在RAS上存在的两个RJ45的端口(“console”与“AUX”)的作用分别是什么?在第四步中,进入虚拟操作台后,在IOS环境下输入了如下的配置,请解释【1】~【4】处的标有下划线部分配置命令的含义。//配置服务器信息hostname
作为一种高可用性的网络信息系统应该具有较强的容错能力,提供容错的途径不包括(47)。
一幅分辨率为800×600×256色未压缩图像的数据量最小约为(10)KB。
为了进行差错控制,必须对传送的数据帧进行校验,由接收方检测数据传输是否出现差错,常用的差错控制方法是(34)。要检测接收的数据是否有错,最常用的方法是(35)。海明码是一种纠错码,采用海明码纠正一位差错,若信息位为7bit,则冗余位至少应为(36),CRC
完成路径选择功能是在OSI模型的(12)。
在面向对象方法中,把一组具有相同数据结构和相同操作的对象的集合定义为______ 。此定义包括一组数据属性和在数据上的一组合法操作。
采用脉码调制(PCM)方法对声音信号进行编码,若采样频率为8000Hz,量化级为256级,那么数据传输率要达到(10)。
在实施信元VC交换过程中,VPI、VCI的变化情况是(26)。
阅读下列说明和图,回答问题1~问题3,将解答填入答题纸的对应栏内。【说明】某城市的各国家公园周边建造了许多供游客租用的小木屋和营地,为此该城市设置了一个中心售票处和若干个区域售票处。游客若想租用小木屋或营地,必须前往中心售票处进行预定并用现金支付全额费
随机试题
胃肠道手术留置胃管时,拔胃管的指征是()。
下列测定路面平整度的方法中属于断面类的方法有()。
钢材的疲劳破坏可以用疲劳极限来表示,疲劳极限是指疲劳试验中试件在()作用下,在规定的周期基数内不发生断裂所能承受的最大应力。
根据债券定价原理,如果一种附息债券的市场价格等于其面值,则其到期收益率()其票面利率。
若某设备投资项目的期望投资收益率为16%,标准离差为0.08,则该设备投资项目标准离差率为()。
一个年轻的美国下级外交官在访问中国时,问了一个令他自己尴尬的问题:东方人怎么会如此令人费解。中国官员笑了笑,然后,温和地回答他:就西方人的缺乏观察力而言,他们的民族才是令人费解的。以下哪一个选项最好地反映了中国官员解释的要点( )
4,3,8,6,12,12,( )
根据商标法规定,下列属于商标侵权行为的有()。
Earlyanthropologists,followingthetheorythatwordsdeterminethought,believedthatlanguageanditsstructurewereentirel
Policiescateringtoalowtuitionintopuniversitiesmayturnouttobringnegativeeffect,JohnBlackburnregardsthenewfi
最新回复
(
0
)