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

admin2012-05-21 63

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

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

软考中级

采用相一幅调制(PAM)技术在带宽为32kHz的无噪声信道上传输数字信号，每个相位处都有两种不同幅度的电平。若要达到192kb/s的数据速率，至少要有(16)种不同的相位。

linux下在安装了Web服务器后，当在inted下启动时，在系统文件/etc/senices中要添加(54)，在单独运行时，命令是(55)。Web系统的系统配置文件(56)，它定义了服务器在DNS数据库中注册的主机名，这是通过(57)命令定义的。测试WW

VPN使用的隧道协议可以有那几类，分别有哪些协议?VPN路由器配置如下：请解释画线部分含义：Vpdn-group1(1)Accept-dialinprotocoll2tpvirtual-template1terminate

在OSI参考模型中，上层协议实体与下层协议实体之回的逻辑接口叫做服务访问点(SAP)。在Internet数据帧中，目的地址“000F781C6001”属于(17)的服务访问点。

《计算机病毒防治管理办法》是由(64)部门发布的。

委托开发完成的发明创造，除当事人另有约定的以外，申请专利的权利属于()所有。

李某受非任职单位委托，利用该单位实验室，实验材料和技术资料开发了一项软件产品。对该软件的权利归属，表达正确的是()。

王某是一名软件设计师，按公司规定编写软件文档，并上交文件存档，这些软件文档属于职务作品，且__________。(2013年上半年试题)

Calculator　is(66)for　performing　arithmetic　operations,　but　that　requires　human　intervention　to　alter　its　stored　program,　if　any

我国《公司法》规定的自愿解散的事由包括()

一支谈判队伍应包括的人员。

下列有关国家赔偿的说法哪一项是正确的：()

生产物流控制内容不包括()。

我国的能源条件可以概括为()。

下列有关法的特征的表述哪些是正确的?()

历史唯心主义的两个根本缺陷是()。

Collegestudentsaremorestressedoutthaneverbefore—atleastaccordingtothelatestfindingsofalarge,nationalsurveyth

设关系模式R＜U,F＞，其中U{H,I,J,K,L}，若F={H→IJ,J→K,IJK→L,L→H,L→K)，则F的最小函数依赖集Fmin={(54)}，关系模式R的候选关键字是(55)。

Thetendencyofaboytobecomeattachedtohismotherandtoresenthisfather______(被称作)the"OedipusComplex".

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

软考中级

采用相一幅调制(PAM)技术在带宽为32kHz的无噪声信道上传输数字信号，每个相位处都有两种不同幅度的电平。若要达到192kb/s的数据速率，至少要有(16)种不同的相位。

linux下在安装了Web服务器后，当在inted下启动时，在系统文件/etc/senices中要添加(54)，在单独运行时，命令是(55)。Web系统的系统配置文件(56)，它定义了服务器在DNS数据库中注册的主机名，这是通过(57)命令定义的。测试WW

VPN使用的隧道协议可以有那几类，分别有哪些协议?VPN路由器配置如下：请解释画线部分含义：Vpdn-group1(1)Accept-dialinprotocoll2tpvirtual-template1terminate

在OSI参考模型中，上层协议实体与下层协议实体之回的逻辑接口叫做服务访问点(SAP)。在Internet数据帧中，目的地址“000F781C6001”属于(17)的服务访问点。

《计算机病毒防治管理办法》是由(64)部门发布的。

委托开发完成的发明创造，除当事人另有约定的以外，申请专利的权利属于()所有。

李某受非任职单位委托，利用该单位实验室，实验材料和技术资料开发了一项软件产品。对该软件的权利归属，表达正确的是()。

王某是一名软件设计师，按公司规定编写软件文档，并上交文件存档，这些软件文档属于职务作品，且__________。(2013年上半年试题)

Calculator is(66)for performing arithmetic operations, but that requires human intervention to alter its stored program, if any

我国《公司法》规定的自愿解散的事由包括()

一支谈判队伍应包括的人员。

下列有关国家赔偿的说法哪一项是正确的：()

生产物流控制内容不包括()。

我国的能源条件可以概括为()。

下列有关法的特征的表述哪些是正确的?()

历史唯心主义的两个根本缺陷是()。

Collegestudentsaremorestressedoutthaneverbefore—atleastaccordingtothelatestfindingsofalarge,nationalsurveyth

设关系模式R＜U,F＞，其中U{H,I,J,K,L}，若F={H→IJ,J→K,IJK→L,L→H,L→K)，则F的最小函数依赖集Fmin={(54)}，关系模式R的候选关键字是(55)。

Thetendencyofaboytobecomeattachedtohismotherandtoresenthisfather______(被称作)the"OedipusComplex".

Calculator　is(66)for　performing　arithmetic　operations,　but　that　requires　human　intervention　to　alter　its　stored　program,　if　any