在有n个无序无重复元素值的数组中查找第i小的数的算法描述如下：任意取一个元素r，用划分操作确定其在数组中的位置，假设元素r为第k小的数。若i等于k，则返回该元素值；若i小于k，则在划分的前半部分递归进行划分操作找第i小的数；否则在划分的后半部分递归进行划分

admin2012-05-21 37

问题在有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)

软件设计师上午基础知识考试

软考中级

在面向数据流的设计方法中，一般把数据流图中的数据流划分为(16)两种。

宽带综合业务数字网B-ISDN的数据通信服务主要采用(53)。

在进行消息认证时，经常利用安全单向散列函数产生消息摘要。安全单向散列函数不需要具有(57)特性。

某计算机的时钟频率为400MHz，测试该计算机的程序使用4种类型的指令。每种指令的数量及所需指令时钟数(CPI)如下表所示，则该计算机的指令平均时钟数约为(4)。

帧中继系统设计的主要目标是用于互连多个(5)。

以下不能在Linux系统核心态下执行的指令是(22)。

TheBorderGatewayProtocol(BGP)isaninterautonomoussystem(6)protocol．TheprimaryfunctionofaBGPspeakingsystemistoex

Developingreliable　software　on　time　and　within(66).represents　a　difficult　endeavor　for　many　organizations.　　　Usually　business　s

下列哪种材料为窝沟封闭剂的主要成分()

X线下见右上肺有多发的厚壁空洞，周围有较广泛的纤维条索影。应首先考虑的是

持站台票乘车，铁路运输企业应当补收票款，并按照规定加收票款，拒不交付的，可以责令下车。()

已知三元二次型χTAχ的平方项系数都为0，α＝(1，2，－1)T满足Aα＝2α．①求χTAχ的表达式．②求作正交变换χ＝Qy，把χTAχ化为标准二次型．

下列关于OSPF协议的描述中，正确的是()。

Readthefollowingarticleandchoosethebestword,foreachspace.Forquestions26-45,markoneletterA,B,CorDonyour

Whatdoesthemanrequestthatthewomando?

软件设计师上午基础知识考试

软考中级

在面向数据流的设计方法中，一般把数据流图中的数据流划分为(16)两种。

宽带综合业务数字网B-ISDN的数据通信服务主要采用(53)。

在进行消息认证时，经常利用安全单向散列函数产生消息摘要。安全单向散列函数不需要具有(57)特性。

某计算机的时钟频率为400MHz，测试该计算机的程序使用4种类型的指令。每种指令的数量及所需指令时钟数(CPI)如下表所示，则该计算机的指令平均时钟数约为(4)。

帧中继系统设计的主要目标是用于互连多个(5)。

以下不能在Linux系统核心态下执行的指令是(22)。

TheBorderGatewayProtocol(BGP)isaninterautonomoussystem(6)protocol．TheprimaryfunctionofaBGPspeakingsystemistoex

Developingreliable software on time and within(66).represents a difficult endeavor for many organizations. Usually business s

下列哪种材料为窝沟封闭剂的主要成分()

X线下见右上肺有多发的厚壁空洞，周围有较广泛的纤维条索影。应首先考虑的是

持站台票乘车，铁路运输企业应当补收票款，并按照规定加收票款，拒不交付的，可以责令下车。()

已知三元二次型χTAχ的平方项系数都为0，α＝(1，2，－1)T满足Aα＝2α．①求χTAχ的表达式．②求作正交变换χ＝Qy，把χTAχ化为标准二次型．

下列关于OSPF协议的描述中，正确的是()。

Readthefollowingarticleandchoosethebestword,foreachspace.Forquestions26-45,markoneletterA,B,CorDonyour

Whatdoesthemanrequestthatthewomando?

Developingreliable　software　on　time　and　within(66).represents　a　difficult　endeavor　for　many　organizations.　　　Usually　business　s