首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在n个数的数组中确定其第i(1≤i≤n)小的数时,可以采用快速排序算法中的划分思想,对n个元素划分.先确定第k小的数,根据i和k的大小关系,进一步处理,最终得到第i小的数。划分过程中,最佳的基准元素选择的方法是选择待划分数组的(64)元素。此时,算法在最坏
在n个数的数组中确定其第i(1≤i≤n)小的数时,可以采用快速排序算法中的划分思想,对n个元素划分.先确定第k小的数,根据i和k的大小关系,进一步处理,最终得到第i小的数。划分过程中,最佳的基准元素选择的方法是选择待划分数组的(64)元素。此时,算法在最坏
admin
2019-07-12
57
问题
在n个数的数组中确定其第i(1≤i≤n)小的数时,可以采用快速排序算法中的划分思想,对n个元素划分.先确定第k小的数,根据i和k的大小关系,进一步处理,最终得到第i小的数。划分过程中,最佳的基准元素选择的方法是选择待划分数组的(64)元素。此时,算法在最坏情况下的时间复杂度为(不考虑所有元素均相等的情况)(65)。
(65)
选项
A、Θ(n)
B、Θ(lgn)
C、Θ(nlgn)
D、Θ(n
2
)
答案
A
解析
本题考查算法设计与分析的相关知识。中位数的含义:将一组数据按照由小到大(或由大到小)的顺序排列,如果数据的个数是奇数,则处于中间位置的数就是这组数据的中位数;如果数据的个数是偶数,则中间两个数据的平均数就是这组数据的中位数。根据题干的描述,选择的基准元素将数组分得越均匀越好,因此中位数是最佳选择。对于该问题,若每次都是选择中位数作为基准元素,则时间复杂度的递归式为:
T(n)=T(n/2)+cn
求解该递归式,得到T(n)=Θ(n)。
转载请注明原文地址:https://kaotiyun.com/show/khCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
请在下列选项中选择合适的答案,填入图3-1、图3-2的方框a和方框b。B的公钥,B的私钥,摘要算法,A的私钥,A的公钥,会话密钥按照图3-2中的方法发送邮件时,使用不同的密码体制加密消息和消息摘要,请用150字以内文字简要说明这样做的理由。
阅读以下说明和C++代码。【说明】传输门是传输系统中的重要装置。传输门具有Open(打开)、Closed(关闭)、Opening(正在打开)、StayOpen(保持打开)和Closing(正在关闭)五种状态。触发传输门状态转换的事件有click
根据问题描述,填写上图中(1)~(3)处联系的类型。联系类型分为一对一、一对多和多对多三种,分别使用1:1,1:n或1:*,m:n或*:*表示。若去掉权限表,并将权限表中的操作权限属性放在员工表中(仍保持管理和服务岗位的操作权限规定),则与原有设计相比
指出算法的流程图中(1)~(3)处的内容。指出测试用例设计中(4)~(9)处的内容。
在需求分析阶段,采用UML的用例图描述系统功能需求,如图1-6所示。指出图1-6中(1)(2)、(3)、(4)分别是哪个用例?指出UML中全局、局部、参数、自我、投票、广播、创建、注销和临时9个约束对于链接角色、消息和对象的作用。
阅读以下说明和VisualBasic码,将应填入(n)处的字名写在对应栏内[说明]设计一个计时程序。该程序用户界面由一个文本框(text1),两个按钮——命令按钮1(Command1)按钮、命令按钮(Command2)组成。程序运行后,用
求供应红色零件北京供应商的编号、名称和状态。求零件颜色不是白色和黑色的供应商状态为1的订单的数量。
多媒体技术的关键在于解决动态图像和声音的存储与传输问题。若不经压缩,以 VGA640×480点阵存储一幅256色的彩色图像大约需(56)MB存储空间,以9600bit/s的速度传输这幅图像大约需(57)秒,按我国电视PAL标准每秒25幅,一张650MB的光
传统的数据库基本上是由(38)组成的。(39)在技术和理论上已经成熟,成为当前商用数据库的主流。(40)技术是20世纪80年代中期引入的。目前,多媒体数据库基本上靠与关系模式相结合的(41)来支持。但当数据量大,数据结构复杂时,靠(41)很难适应。当前,在
随机试题
在数学教学中,教师常采用画示意图的方式来表达、分析问题,以帮助学生理解题目。这种方法所采用的学习策略是()。
现有一个三段的指令流水线,各段经过时间依次为△t,2△t,△t。请画出该流水线连续处理三条不相关指令的时空图,并计算流水线的吞吐率、加速比和效率。
access中账户权限没有继承性。()
下列溶剂极性由小到大的排列顺序是
背景某施工单位承包一机电工程施工项目,工程内容包括工艺热力管道安装和一座钢结构框架安装。合同规定,钢材等主材由建设单位供货。施工单位安排由该单位的甲、乙两个施工队分别承担施工任务。施工中发生如下事件:事件一:在工程中期进度质量大检查中,
决定是否买空或卖空期货合约的时候,交易者应该事先为自己确定( ),做好交易前的心理准备。
下列关于资产的税务处理的表述,正确的有()。
下列各项支出,应在企业应付职工薪酬中列支的有()。
清水断崖位于中国台湾省东部海岸,依山傍海,崖岸壁立,为台湾八大名胜之一。读图,回答下列问题。下列关于台湾岛河流水文特征的叙述正确的是()。
A、ItwasleftinDavid’soffice.B、ItwasleftinKate’soffice.C、Itwaslostinthetrainsomeday.D、ItwasleftintheJohns
最新回复
(
0
)