首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在有n个无序无重复元素值的数组中查找第i小的数的算法描述如下:任意取一个元素r,用划分操作确定其在数组中的位置,假设元素r为第k小的数。若i等于k,则返回该元素值;若i小于k,则在划分的前半部分递归进行划分操作找第i小的数;否则在划分的后半部分递归进行划分
在有n个无序无重复元素值的数组中查找第i小的数的算法描述如下:任意取一个元素r,用划分操作确定其在数组中的位置,假设元素r为第k小的数。若i等于k,则返回该元素值;若i小于k,则在划分的前半部分递归进行划分操作找第i小的数;否则在划分的后半部分递归进行划分
admin
2012-05-21
65
问题
在有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)算法形成认证协议,产生了
输入输出系统主要用三种方式与主机交换数据,对于这三种方式的描述正确的是(1)。
linux下在安装了Web服务器后,当在inted下启动时,在系统文件/etc/senices中要添加(54),在单独运行时,命令是(55)。Web系统的系统配置文件(56),它定义了服务器在DNS数据库中注册的主机名,这是通过(57)命令定义的。测试WW
DES算法属于加密技术中的(26)。
有关曼彻斯特码编码的正确叙述是(24)。
CMM模型将软件过程的成熟度分为5个等级,在(5)使用定量分析来不断地改进和管理软件过程。
在一个由多台路由器构成的网络中,一条途经多个路由器的线路断开了,判断是哪一个路由器发生故障的命令是(1)。在发现跨路由器ping不通的情况下,可用配置管理工具收集(2)信息进行分析。(2)
RMONv1只监视两层,即(1)的信息,可以有效监视每个网段,但不能分析网络全局的通信状况。RMONv2标准使得对网络的监控层次提高到(2)。它主要强调IP流量和应用程序的水平流量。RMON中,若想对网络上一段进行拥塞分析,可以从MIB组的(3)着手。
Flynn分类法基于信息流特征将计算机分成4类,其中()只有理论意义而无实例。
结点数目为n的二叉查找树(二叉排序树)的最小高度为(52)、最大高度为(53)。
随机试题
门脉性肝硬化并伴有上消化道出血时,下述哪项可诱发肝性脑病
财务成果的具体表现是盈利或亏损。()
“Youandme,fromoneworld,wearefamily.Fraverdream,athousandmiles,meetinginBeijing.Cometogether,putyourhandinmine.You
在一起斗殴致伤案件的侦查中,公安机关将犯罪嫌疑人朱某拘留,但一时难以查清谁是主要凶手,拘留期限届满时公安机关只好对朱某取保候审。()
设A为n阶实对称矩阵,秩(A)=n,Aij是A=(aij)n×m中元素aij(i,j=1,2,…,n)的代数余子式,二次型f(x1,x2,…,xn)=(Ⅰ)记X=(x1,x2,…,xn)T,把f(x1,x2,…,xn)写成矩阵形式,并证明二次型f(x)的
小王利用Word撰写专业学术论文时,需要在论文结尾处罗列出所有参考文献或书目,最优的操作方法是()。
Onesummerdaymyfathersentmetobuywireforourfarm.At16,Iliked【C1】______betterthandrivingourtruck,【C2】______this
Theywavedthewhiteflagasa______thattheywishtosurrender.
Ataroundageoffive,everychildhastomakethe【C1】______fromhometoschool.Childrenatthisagehaveanenormousamountto
Aninterpersonalrelationshipisarelativelylong-termassociationbetweentwoormorepeople.Thisassociationmay【B1】______e
最新回复
(
0
)