首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(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
79
问题
(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明和图,回答问题l至问题3,将解答填入答题纸的对应栏内。【说明】一个简单的图形编辑器提供给用户的基本操作包括:创建图形、创建元素、选择元素以及删除图形。图形编辑器的组成及其基本功能描述如下:(1)图形由文本元素和图元元素构成,图元元素包括线
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某城市的各国家公园周边建造了许多供游客租用的小木屋和营地,为此,该城市设置了一个中心售票处和若干个区域售票处。游客若想租用小木屋或营地,必须前往中心售票处进行预定并用现金支付全额
阅读以下说明和图,根据要求回答问题1~问题4。【说明】某大学欲开发一个基于web的课程注册系统,该系统的主要功能如下:1.验证输入信息(1)检查学生信息:检查学生输入的所有注册所需信息。如果信息不合法,返回学生信息不合法提示;如果合法,输出合法学生
阅读下列说明和图,回答问题l至问题4,将解答填入答题纸的对应栏内。【说明】某公司欲开发招聘系统以提高招聘效率,其主要功能如下:(1)接受申请验证应聘者所提供的自身信息是否完整,是否说明了应聘职位,受理验证合格的申请,给应聘者发送致谢信息。(2)评
阅读下列说明和图,回答问题1至问题4,将解答填入答题纸的对应栏内。【说明】某电子商务系统采用以数据库为中心的集成方式改进购物车的功能,详细需求如下:(1)加入购物车。顾客浏览商品,点击加入购物车,根据商品标识从商品表中读取商品信息,并更新购物车表。
阅读下列说明和Java代码,将应填入(n)处的字句写在答题纸的对应栏内。【说明】某软件公司现欲开发一款飞机飞行模拟系统,该系统主要模拟不同种类飞机的飞行特征与起飞特征。需要模拟的飞机种类及其特征如表17—3所示。为支持将来模拟更多种类的飞机,采用策
(2013年上半年下午试题四)阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】设有m台完全相同的机器运行n个独立的任务,运行任务i所需要的时间为tI,要求确定一个调度方案,使得完成所有任务所需要的时间最短。
一个系统的模块结构图如下所示,用{X,X,X}表示这个系统的测试模块组合。下面的选项中(20)表示自顶向下的测试,(21)表示三明治式测试。
软件测试是软件开发中不可缺少的活动,通常(35)在代码编写阶段进行。检查软件的功能是否与用户要求一致是(36)的任务。
软件测试是软件质量保证的主要手段之一,测试的费用已超过(10)的30%以上。因此提高测试的有效性非常重要。“高产”的测试是指(11)。根据国家标准GB8566-88计算机软件开发规范的规定,软件的开发和维护分为8个阶段,其中单元测试是在(12)阶段完成的;
随机试题
对离心泵错误的安装或操作方法是()。
下述哪种呕吐为反射性呕吐
冠心病患者术前应停服的药物不包括
唐某购买了一辆普通大客车从事运输。2008年5月1日,该车从北京一建筑工地载20名民工返乡,并收取了每人100元的车费。当夜2时许,行车途中,唐某及2名司乘人员堵住车门,其中一人手持铁棍,以“补票”为名,要乘客每人再补200元至300元车费,对不补票者不让
下列关于冲天炉技术经济指标的说法中,正确的是()。
在教育资源紧缺的地区,应该接受义务教育的适龄儿童、少年须通过相关考试方能入学。()
公文的语言风格应该是()。
设A为n阶矩阵,k为常数,则(kA)*等于().
STD总线是面向工业控制的(14)位控制总线,它共有(15)条信号线。
在关系数据库逻辑结构设计中,将一个实体类型转换成一个关系模式时,通常实体的属性就是关系的属性,【】就是关系的码。
最新回复
(
0
)