首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知数组A[1……n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想; (2)根据设计思想,采用C或C++
已知数组A[1……n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想; (2)根据设计思想,采用C或C++
admin
2013-07-12
49
问题
已知数组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; whi1e(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/crxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
1966年至1976年间在我国发生的全局性、长时间的“左”倾严重错误是()。
美国首次提出争夺世界霸权的纲领性文件是()。
国民政府统治确立后,中国社会仍存在革命条件并成为唯一选择的主要原因是()。
概述人民公社运动发生的原因、错误、危害及主要教训。
西藏自治区的设立时间是()。
第一国际成立的时间是()。
东欧国家的私有化方式一般有四种,其中波兰采取的主要方式是()
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为:MAX{从w到v的最短距离|w属于V(G))如果v是有向图G中具有的最小偏心度的顶点,则称顶点v是G的中心点。
一个UDP用户的数据报的数据部分长为8192字节。那么通过以太网来传播该UDP数据报时,最后一个IP分片的数据长度是()。
某公司的局域网设置如下所示,两个局域网通过路由器连接到NAT、服务器上,并且通过NAT服务器连接到Internet上。局域网1的掩码是192.168.14.0/25,局域网2的掩码是192.168.14.128/25,NAT服务器的内部IP地址为192.1
随机试题
沉默的谈判对手的心理特征是()
尿崩症侏儒症
男,25岁。发热伴皮肤出血点2周,查体:双下肢皮肤可见出血点,胸骨下段压痛(+),肝肋下3cm,脾肋下1.5cm。血液检查:Hb105g/L,WBC2.0×109/L,分类可见幼稚细胞,PLT35×109/L。最可能的诊断是()
A、溶菌酶含片B、西地碘含片C、硝酸银溶液D、氯己定含漱剂E、地塞米松粘贴片能够卤化细菌的体蛋白,杀菌力强的是()。
当机械波在媒质中传播,一媒质质元的最大形变量发生在()。
我国车辆购置税的适用区域在“中华人民共和国境内”,这里的“中华人民共和国境内”是指()。
下列不属于经济周期中复苏和繁荣阶段可能出现的一般特征的是()。
下列关于房地产权属登记的概念,说法不正确的是()。
在Word中,如果要在“插入”和“改写”状态之间切换,可以按()键。
Becausestereotypesarestandardizedand______ideasofgroups,basedonsomeprejudices,theyarenotderived______objectivefac
最新回复
(
0
)