首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在有n个无序无重复元素值的数组中查找第i小的数的算法描述如下:任意取一个元素r,用划分操作确定其在数组中的位置,假设元素r为第k小的数。若i等于k,则返回该元素值;若i小于k,则在划分的前半部分递归进行划分操作找第i小的数;否则在划分的后半部分递归进行划分
在有n个无序无重复元素值的数组中查找第i小的数的算法描述如下:任意取一个元素r,用划分操作确定其在数组中的位置,假设元素r为第k小的数。若i等于k,则返回该元素值;若i小于k,则在划分的前半部分递归进行划分操作找第i小的数;否则在划分的后半部分递归进行划分
admin
2012-05-21
47
问题
在有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
软件设计师上午基础知识考试
软考中级
相关试题推荐
SNMPv1是一个不安全的协议,管理站(Manager)与代理(Agent)之间通过(55)进行身份认证,由于认证信息没有加密,所以是不安全的。1998年公布的SNMPv3定义了基于用户的安全模型USM,其中的认证模型块结合(56)算法形成认证协议,产生了
在千兆以太网物理层标准中,采用长波(1300nm)激光信号源的是(63)。
Ipv6is(71)for"InternetProtocolVersion6"。Ipv6isthe"nextgeneration"protocoldesignbytheIETFto(72)thecurrentversion
在Linux操作系统中,用于测试smb.conf文件语法设置是否正确的命令是(61)。
在软件开发过程中常用图作为描述工具。如DFD就是面向(6)分析方法的描述工具。在一套分层DFD中,如果某一张图中有N个加工(Process),则这张图允许有(7)张子图。在一张DFD图中,任意两个加工之间(8)。在画分层DFD时,应注意保持(9)之间的平
在配置命令frame-relaymapip192.168.1.1dlci101broadcast中,数字101的含义是(53)。
WindowsServer2003操作系统中,其活动目录采用基于(65)格式的系统设计,建立了层次化的结构。
在SNMP管理模型中,关于管理信息库MIB的说法,正确的是(1)。SNMP实现管理功能的方式是(2)。SNMP网络管理模型中关于管理代理与委托代理的说法正确的是(3)。SNMP将一个值存储到指明变量中去使用(4)命令,而有关get操作命令的目的是(5)。
以太网介质访问控制策略可以采用不同的监听算法,其中一种是:一旦介质空闲就发送数据,假如介质忙,继续监听,直到介质空闲后立即发送数据,这种算法称为(1)监听算法,该算法的主要特点是(2)。(2011年下半年试题)(2)
Calculator is(66)for performing arithmetic operations, but that requires human intervention to alter its stored program, if any
随机试题
在工业给水系统中,可以分为()。
在现代信用货币制度下,经常出现的货币失衡现象是()。
在对基础货币产生影响的诸多因素中,由商业银行决定的因素是()。
下图为北半球中纬度某地,半个月内清晨6点出现的月相示意图。读图回问题。当月球出现在天际的乙位置时,有可能发生的现象是()。
领导科学的研究对象是领导。
“十五”期间,经济结构战略性调整的重点是( )。
如果老王是大学教师,又写过许多哲学论文,则他一定是哲学系的教师。这个断定是根据以下哪项作出的?
PropertyinAmerica:Thehousewins[A]Atfirstglancethisissurprising.Housepricestypicallynosediveduringrecession
Atransplantoperationissuccessfulonlyifdoctorscanpreventthebodyfromrejectingthe______organ.
He’snotour________son—weadoptedhimwhenhewasthree.
最新回复
(
0
)