首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(2012年上半年上午试题65)现要对n个实数(仅包含正实数和负实数)组成的数组A进行重新排列,使得其中所有的负实数都位于正实数之前。求解该问题的算法的伪代码如下,则该算法的时间和空间复杂度为_________。 i=0;j=n-1 while i<1
(2012年上半年上午试题65)现要对n个实数(仅包含正实数和负实数)组成的数组A进行重新排列,使得其中所有的负实数都位于正实数之前。求解该问题的算法的伪代码如下,则该算法的时间和空间复杂度为_________。 i=0;j=n-1 while i<1
admin
2021-01-13
78
问题
(2012年上半年上午试题65)现要对n个实数(仅包含正实数和负实数)组成的数组A进行重新排列,使得其中所有的负实数都位于正实数之前。求解该问题的算法的伪代码如下,则该算法的时间和空间复杂度为_________。
i=0;j=n-1
while i<1 do
while A
<0 do
i=i+1;
while A[j]>0 do
j=j-1;
if i<1 do
交换A
和A[j]
选项
A、Θ(n)和Θ(n)
B、Θ(1)和Θ(n)
C、Θ(n)和Θ(1)
D、Θ(1)和Θ(1)
答案
C
解析
算法中用到了两个辅助变量i和i,算法的空间复杂度为Θ(1)。在重新排列过程中,从数组的两端进行比较,从i=0开始判断A
是否为负数,i为负数的时候,i=i+1,直到A
为正数;从j=n-1开始判断A
是否为正数,如果为正数,j=j-1,直到A[j]为负数。当i
和A[j]的值,然后继续判断A
和A[j]的值。数组A中的元素个数为n,A
<0和A[j]>的比较次数共为n+2次,i=i+l和j=j-1执行的次数最多为n+2次,if语句中的i<j的比较和交换A
和A[j]的操作分别最多执行n-1次,While循序的条件判断至多执行n次。可见,算法的时间复杂度为Θ(n)。
转载请注明原文地址:https://kaotiyun.com/show/itCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某运输公司决定为新的售票机开发车票销售的控制软件。图13-15给出了售票机的面板示意图以及相关的控制部件。售票机相关部件的作用如下所述:(1)目的地键盘用来输入行程目的地的
阅读下列说明和图,回答问题l至问题4,将解答填入答题纸的对应栏内。【说明】某公司欲开发招聘系统以提高招聘效率,其主要功能如下:(1)接受申请验证应聘者所提供的自身信息是否完整,是否说明了应聘职位,受理验证合格的申请,给应聘者发送致谢信息。(2)评
阅读下列说明和图,回答问题1至问题4,将解答填入答题纸的对应栏内。【说明】某电子商务系统采用以数据库为中心的集成方式改进购物车的功能,详细需求如下:(1)加入购物车。顾客浏览商品,点击加入购物车,根据商品标识从商品表中读取商品信息,并更新购物车表。
某集团公司拥有多个大型连锁商场,公司需要构建一个数据库系统以方便管理其业务运作活动。【需求分析结果】(1)商场需要记录的信息包括商场编号(编号唯一)、商场名称、地址和联系电话。某商场信息如表13-1所示。(2)每个商场包含不
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某软件公司欲设计实现一个虚拟世界仿真系统。系统中的虚拟世界用于模拟现实世界中的不同环境(由用户设置并创建),用户通过操作仿真系统中的l~2个机器人来探索虚拟世界。机器人维护着两个
(2021年下半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】设有n个货物要装入若干个容重为C的集装箱以便运输,这n个货物的体积分别为{s1,s2,…,sn},且有si≤C(1≤i≤n)。为
已知3个类O、P和Q,类O中定义了一个私有方法F1和一个公有方法F2;类P中定义了一个公有方法F3,类P为类O的派生类;类Q为类P的派生类,它们的继承方式如下所示:classP:publicO{…};classQ:privateP{
软件测试是软件开发中不可缺少的活动,通常(35)在代码编写阶段进行。检查软件的功能是否与用户要求一致是(36)的任务。
软件测试是软件质量保证的主要手段之一,测试的费用已超过(10)的30%以上。因此提高测试的有效性非常重要。“高产”的测试是指(11)。根据国家标准GB8566-88计算机软件开发规范的规定,软件的开发和维护分为8个阶段,其中单元测试是在(12)阶段完成的;
随机试题
关于刑法解释,下列哪一选项是错误的?()(2013/2/3)
Ifyoucansupplygoodsofthetypeandqualityrequired,wemayplaceregularordersforlargequantities.
食物中毒与其他急性疾病最本质的区别是
颞下颌关节关节囊的上后方附着于
肝阳化风可见()阴虚风动可见()
A.gp120B.Gp41C.P24D.P17E.P7具有诊断价值的HIV蛋白是
甲公司委托乙公司销售商品200件,商品已经发出,每件成本为60元。合同约定乙公司应按每件100元对外销售,甲公司按售价的10%向乙公司支付手续费。当期乙公司对外实际销售100件,开出的增值税专用发票上注明的销售价款为10000元,增值税税额为1700元。甲
课程理论的创始人是(),其强调学科基本结构的学习要与学生的认识发展水平相一致。因此在编制学科课程时,要依据学习者的思维发展水平,采用螺旋上升的方式编制课程。
阅读以下文字,回答下列问题。我们将“衰老”________为:机体的各个“组件”,特别是DNA,某些特殊蛋白质,碳水化合物和脂质(脂肪)所受到的随机损伤的大量累积,这一累积在生命初期就已经开始,并最终达到机体自我修复的极限。这种伤害会逐渐削弱细胞
A、Lenovocanuseaworld-famousbrandnameforsometime.B、Lenovocanhold18.9%ofthestocksofIBM.C、Lenovocanenterinto
最新回复
(
0
)