首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在有n个无序无重复元素值的数组中查找第i小的数的算法描述如下:任意取一个元素r,用划分操作确定其在数组中的位置,假设元素r为第k小的数。若i等于k,则返回该元素值;若i小于k,则在划分的前半部分递归进行划分操作找第i小的数;否则在划分的后半部分递归进行划分
在有n个无序无重复元素值的数组中查找第i小的数的算法描述如下:任意取一个元素r,用划分操作确定其在数组中的位置,假设元素r为第k小的数。若i等于k,则返回该元素值;若i小于k,则在划分的前半部分递归进行划分操作找第i小的数;否则在划分的后半部分递归进行划分
admin
2012-05-21
46
问题
在有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
软件设计师上午基础知识考试
软考中级
相关试题推荐
在图8-7所示的网络拓扑结构的分支机构路由器上,正确的拨号映射配置语句是(53)。
Linux系统中在下列(62)文件中指定了网络路由信息。
以下网络地址中属于PrivateAddress的是(47)。
IPv4地址可以划分为{网络号,主机号}两部分。在下面的地址标记中,用0表示所有比特为0,用-1表示所有比特为1。以下选项中,(15)不能作为目标地址,(16)不能作为源地址,(17)只能用于本机测试,(18)用于内部网络。IPv6使用了更大的地址空间,每
采用UML进行软件设计时,可用(5)关系表示两类事物之间存在的特殊/一般关系,用聚集关系表示事物之间存在的整体/部分关系。
在OSI参考模型中,实现节点到节点的流量控制、分组路由等功能的协议层是(28)。
TheBorderGatewayProtocol(BGP)isaninterautonomoussystem(6)protocol.TheprimaryfunctionofaBGPspeakingsystemistoex
下图为DARPA提供的公共入侵检测框架示意图,该系统由四个模块组成,其中模块①~④对应的正确名称为____________。
在设计测试用例时,(41)是用得最多的一种黑盒测试方法。在黑盒测试方法中,等价类划分方法设计测试用例的步骤是:①根据输入条件把数目极多的输入数据划分成若十个有效等价类和若干个无效等价类。②设计一个测试用例,使其覆盖(42)尚未被覆盖的有效等
Developingreliable software on time and within(66).represents a difficult endeavor for many organizations. Usually business s
随机试题
南蜇的主要产地是________。
少尿定义为24小时尿量小于
(2007年第25题)核酸变性后,可产生的效应是
滴丸剂检查法应取滴丸剂多少丸,精密称总重量,求得平均丸重
招标代理服务收费标准中规定,中标金额在1000万~5000万元的工程招标项目,按中标金额的()取费。
“从物到感觉和思想”与“从感觉和思想到物”是两条根本对立的认识路线,它属于()。
台湾岛西海岸布袋盐场形成的条件是()。
所有优秀的学管老师都关心学生的利益;所有关心学生利益的学管老师在满足学生需求方面都很开明;在满足学生需求方面不开明的所有学管老师都不是优秀的学管老师。下列哪项可以由上文推出?
Ethernet交换机实质上是一个多端口的()。
InAristophanes’Lysistratawomenareseenasthemeansofbringingpeaceandgoodsensetoawar-tornworld.
最新回复
(
0
)