首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在有n个无序无重复元素值的数组中查找第i小的数的算法描述如下:任意取一个元素r,用划分操作确定其在数组中的位置,假设元素r为第k小的数。若i等于k,则返回该元素值;若i小于k,则在划分的前半部分递归进行划分操作找第i小的数;否则在划分的后半部分递归进行划分
在有n个无序无重复元素值的数组中查找第i小的数的算法描述如下:任意取一个元素r,用划分操作确定其在数组中的位置,假设元素r为第k小的数。若i等于k,则返回该元素值;若i小于k,则在划分的前半部分递归进行划分操作找第i小的数;否则在划分的后半部分递归进行划分
admin
2012-05-21
75
问题
在有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
软件设计师上午基础知识考试
软考中级
相关试题推荐
为了进行差错控制,必须对传送的数据帧进行校验。要纠正出3位错,码字之间的海明距离最小值应为(16)。
以下网络地址中属于PrivateAddress的是(47)。
使用netstat-an命令可显示所测试网络的(42)。
在尽量节省资金的情况下,同时将原有设备充分利用(原来用HUB来连接各网段),应如何改善网络性能,增加什么设备?并说出理由。当公司需要将计算机按部门划分成虚拟网络,而一个部门可能分散在不同的地方且不能由一个联网设备连接时,但不需要不同部门之间的计算机通信
为了进行差错控制,必须对传送的数据帧进行校验,由接收方检测数据传输是否出现差错,常用的差错控制方法是(34)。要检测接收的数据是否有错,最常用的方法是(35)。海明码是一种纠错码,采用海明码纠正一位差错,若信息位为7bit,则冗余位至少应为(36),CRC
总线型拓扑结构和环型拓扑结构的主要缺点是(19)。
与routeprint具有相同功能的命令是____________。
阅读以下预备知识、函数说明和C代码,将应填入(n)处的字句写在对应栏内。[预备知识]①对给定的字符集合及相应的权值,采用哈夫曼算法构造最优二叉树,并用结构数组存储最优二叉树。例如,给定字符集合{a,b,c,d}及其权值2、7、4、5,可构造如图
阅读下列说明和C程序,将应填入(n)处的字句写在对应栏中。[说明]借助一个栈结构,可实现二叉树的非递归遍历算法。InOrderTraverse数实现中序非递归遍历,遍历过程如下:若不是空树,根节点入栈,进入左子树;若已
为了解决进程间的同步和互斥问题,通常采用一种称为(21)机制的方法。若系统中有5个进程共享若干个资源R,每个进程都需要4个资源R,那么使系统不发生死锁的资源R的最少数目是(22)。
随机试题
光电跟踪气割机可以根据图样进行气割。()
A.α受体阻断剂B.β受体阻断剂C.α受体激动剂D.β受体激动刺E.胆碱能神经阻滞剂异丙肾上腺素属于
患儿男,5岁。因咽喉痛、发热和吞咽困难就诊,体格检查时发现患儿颈前淋巴结肿大,为确定是否为白喉,留取咽拭子进行涂片镜检。革兰染色见到革兰阳性杆菌成簇排列,Albert染色见到浅绿色的杆状菌,菌体上有深绿色的颗粒,该颗粒称为
A.破裂孔B.卵圆孔C.眶上裂D.圆孔E.颈动脉孔下颌神经出颅经
某工程案卷内建设工程档案的保管密级有秘密和机密,保管期限有长期和短期,则该工程档案的( )。
悬挑空调板的受力钢筋应布置在板的()。
实施内容反应技术时,要注意()。
站赤(兰州大学2003年中国古代史真题)
中断分为哪几种类型?请给出各自的含义。
Inwhatnowseemsliketheprehistorictimesofcomputerhistory,theearth’spostwarera,therewasquiteawide-spreadconcer
最新回复
(
0
)