首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
(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
81
问题
(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,将解答填入答题纸对应栏内。【说明】某城市拟开发一个基于web的城市黄页,公开发布该城市重要的组织或机构(以F统称为客户)的基本信息,方便城市生活。该系统的主要功能描述如下:(1)搜索信息:任何使用Internet的
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某网上药店允许顾客凭借医生开具的处方,通过网络在该药店购买处方上的药品。该网上药店的基本功能描述如下:(1)注册。顾客在买药之前,必须先在网上药店注册。注册过程中需填写顾客资料
阅读下列说明和图,回答问题1至问题4,将解答填入答题纸的对应栏内。【说明】某医院欲开发病人监控系统。该系统通过各种设备监控病人的生命体征,并在生命体征异常时向医生和护理人员报警。该系统的主要功能如下:(1)本地监控:定期获取病人的生命特征,如体温、血
阅读下列说明和图,回答问题1至问题4,将解答填入答题纸的对应栏内。【说明】某学校开发图书管理系统,以记录图书馆藏图书及其借出和归还情况,提供给借阅者借阅图书功能,提供给图书馆管理员管理和定期更新图书表功能。主要功能的具体描述如下:(1)处理借阅。借阅者
阅读下列说明和图,回答问题1至问题4,将解答填入答题纸的对应栏内。【说明】某电子商务系统采用以数据库为中心的集成方式改进购物车的功能,详细需求如下:(1)加入购物车。顾客浏览商品,点击加入购物车,根据商品标识从商品表中读取商品信息,并更新购物车表。
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】堆数据结构定义如下:对于n个元素的关键字序列{a1,a2,…,an},当且仅当满足下列关系时称其为堆。在一个堆中,若堆顶元素为最大元素,则称为大顶堆;若堆顶元素为最小元素
某高校欲开发一个成绩管理系统。记录并管理所有选修课程的学生的平时成绩和考试成绩,其主要功能描述如下。(1)每门课程都由3~6个单元构成,每个单元结束后会进行一次测试,其成绩作为这门课程的平时成绩。课程结束后进行期末考试,其成绩作为这门课程的考试成绩。(
已知3个类O、P和Q,类O中定义了一个私有方法F1和一个公有方法F2;类P中定义了一个公有方法F3,类P为类O的派生类;类Q为类P的派生类,它们的继承方式如下所示:classP:publicO{…};classQ:privateP{
软件测试是软件质量保证的主要手段之一,测试的费用已超过(10)的30%以上。因此提高测试的有效性非常重要。“高产”的测试是指(11)。根据国家标准GB8566-88计算机软件开发规范的规定,软件的开发和维护分为8个阶段,其中单元测试是在(12)阶段完成的;
随机试题
SIS家族编码产物的作用正确的是
甘麦大枣汤的病变部位是
患者,刘某,女,54岁,因血栓性浅静脉炎寻求康复治疗,不适宜的方法是
慢性肾小球肾炎的理想血压控制目标为
充填物过高,咬合时出现早接触可引起以亚砷酸失活剂置于邻面洞时,由于封闭不严,药物渗漏可引起
在美国债券市场中,机构投资者经常使用的三种综合类债券市场指数为()。I.莱恩指数Ⅱ.莱曼兄弟综合指数Ⅲ.所罗门兄弟投资级债券综合指数Ⅳ.美林国内市场指数
下列不属于市场风险的是()。
函数f(x)=中,x3的系数是().
左边图形由四个部分组成,各部分通过平面上的变化可以组成新图形,下列选项中,不是由这四个部分组成的是()。
下列叙述中正确的是()。
最新回复
(
0
)