首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知数组A[1……n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想; (2)根据设计思想,采用C或C++
已知数组A[1……n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想; (2)根据设计思想,采用C或C++
admin
2014-12-08
37
问题
已知数组A[1……n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。
(1)给出算法的基本设计思想;
(2)根据设计思想,采用C或C++或JAVA语言表述算法,关键之处给出注释;
(3)说明你所设计算法的时间复杂度和空间复杂度。
选项
答案
(1)算法的基本设计思想如解析所述。 (2)用C语言算法描述如下: void Adjust(int A[]){ //调整数组A,使得A的左边为负整数,右边为正整数 int i=1,j=n,temp; while(i
0&&i
解析
本题主要考查线性表的顺序存储结构(这里为数组)的应用。算法的基本设计思想是先设置好上、下界和轴值,然后分别从数组前端查找正整数和从数组末端查找负整数,找到后进行交换,直到上、下界相遇。
具体做法是:设置两个指示器i和j,其中i=1,j=n;当A
为正整数,A[j]为负整数时,A
和A[j]交换;否则,A
为负整数时,则i++;A[j]为正整数时,则j--。这样,
可使算法的时间复杂度为O(n)。
转载请注明原文地址:https://kaotiyun.com/show/44xi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
试述格拉古兄弟改革的内容和意义。(北京师范大学1999年世界上古史真题)
简述大运河开凿的原因及其意义。
三国时期,魏、蜀、吴三国灭亡的历史顺序是()。
国共合作之后,红军改编为八路军,其中原是红四方面军的是()
马克思为第一国际起草的文件有()。①《共产党宣言》②《临时章程》③《成立宣言》④《资本论》
简述从十月革命胜利到第二次世界大战爆发前夕苏俄(苏联)与主要资本主义国家关系演变的基本情况。
最晚到汉武帝时期,出现了我国第一部算学著作(),它记载了用竿标测日影以求日高的方法,从而认识了勾股定理。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
下列有关曲辕犁的表述正确的是()①曲辕犁早在中国汉代即已使用了②曲辕犁在中国出现至少比欧洲早一千多年③我国古代的农业工具和农耕技术曾长期居世界领先地位④处于“蒸汽时代”的欧洲农业技术革新,滞后于同时代工业的发展
美国的垄断组织主要采取的形式是()。
随机试题
A.滴虫性阴道炎B.真菌性阴道炎C.老年性阴道炎D.幼女性阴道炎E.阿米巴阴道炎用碱性溶液冲洗阴道可提高疗效的是
骨肉瘤的特点是______。
28岁初孕妇,妊娠32周,头痛5日就诊。查血压160/110mmHg,脉搏94次/分,面色苍白。子宫长度26cm,臀先露,骶右后,胎心144次/分,尿蛋白(+++),水肿(±)。
苯巴比妥
某犯罪集团多次抢劫银行,数额巨大,打死打伤数人。对此案的审理,人民法院最多应该在多长的时间内宣判:
鸿儒股份有限公司(以下简称鸿儒公司)为增值税一般纳税人,适用的增值税税率为17%。商品销售价格均不含增值税额,所有劳务均属于增值税应税劳务。销售实现时结转销售成本。鸿儒公司销售商品和提供劳务均为主营业务。2×10年12月,鸿儒公司销售商品和提供劳务的资料如
甲、乙等企业拟联合组建设立“A有限责任公司”(以下简称A公司),公司章程的部分内容为:公司股东会除召开定期会议外,还可以召开临时会议,临时会议须经代表1/2以上表决权的股东、1/2以上的董事或1/2以上的监事提议召开。在申请公司设立登记时,工商行政管理机构
下列会计事项中,可能会影响企业期初留存收益的有()。
IP数据报的报文格式如下图所示。在没有选项和填充的情况下,报头长度域的值为
Atfirstthecompanyrefusedtopurchasetheequipment,butthisdecisionwas______revised.
最新回复
(
0
)