首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知数组A[1……n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想; (2)根据设计思想,采用C或C++
已知数组A[1……n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想; (2)根据设计思想,采用C或C++
admin
2014-12-08
35
问题
已知数组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
学硕统考专业
相关试题推荐
列举二战期间中国政府参加的重要国际会议,并论述这些会议对中国的影响
1948年,南斯拉夫对从苏联照搬来的“行政命令式的国家集权式”体制进行改革逐步形成有自己特色的建设社会主义的理论和方法,其核心是()。
下面条约没有涉及德国的赔款问题的是()。
下列历史事件发生的先后顺序是()①“铁幕”演说②马歇尔计划③北大西洋公约
以下选项中中原王朝对西藏管辖设置机构对应有误的一项是()。
下列选项中,不是由晁错提出的是()
外国侵略者通过不平等条约取得的特权中,按时间先后顺序排列应是()。①外国商船和军舰可以在长江各口岸自由航行②外国人可以在通商口岸开设工厂③可在通商口岸建立教堂④领事裁判权和片面最惠国待遇
穆斯林定居印度后,形成以阿拉伯语字母为基础的语言是()
巴黎和会上,英国既与法国联合抵制美国称霸世界,又与美国联合反对法国过分削弱德国的要求,英国这样做的目的是()。
二战期间,下列四次战役的时间先后顺序是()①莫斯科战役②诺曼底登陆③不列颠之战④阿拉曼战役
随机试题
下列选项中不属于生物群落的组成成分的是()
细菌内毒素的特征是
足少阳胆经悬钟穴位于
A.呼吸道感染B.心力衰竭C.心律不齐D.亚急性感染性心内膜炎E.栓塞风心病二尖瓣狭窄伴房颤最易出现
给水管道安装完成确认无误后,必须进行系统的水压试验,室内给水管道试验压力为工作压力的( )。
甲公司采用资产负债表债务法核算所得税,适用的所得税税率为25%。2016年6月30日,甲公司将一栋写字楼出租给乙公司,并采用公允价值模式进行后续计量。该写字楼原价为20000万元,预计使用寿命为20年,采用年限平均法计提折旧,预计净残值为0。假设税法对该投
小学二年级的品德与生活课上,王老师告诉同学们要遵守国家法律制度,保护野生动物。王老师拿出了各种图片,向大家介绍了大熊猫、金丝猴、穿山甲等国家保护动物。同学们都非常高兴地辨识这些图片,了解到了保护动物的常识。两周后的一个周末,小明和家人去郊外游玩,在一个农庄
Charliecamefromapoorvillage.Hisparentshad【C1】______moneytosendhimtoschoolwhenhewasyoung.Theboywasverysad.
阅读材料,回答问题:材料1在五千年的历史长河中,作为民族精神的核心,爱国主义始终是中华民族团结统一的精神纽带,始终是凝聚力和向心力的基本源泉,始终是推动中国社会发展进步的巨大力量。这种精神,寄托着对民族命运的拳拳之心,倾注了对中华大地的
AntsHaveBigImpactonEnvironmentas"EcosystemEngineers"ResearchbytheUniversityofExeterhasrevealedthatantshav
最新回复
(
0
)