首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知数组A[1……n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想; (2)根据设计思想,采用C或C++
已知数组A[1……n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想; (2)根据设计思想,采用C或C++
admin
2013-07-12
65
问题
已知数组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
学硕统考专业
相关试题推荐
近代中国第一个系统介绍西方思想与文化名著的翻译家和启蒙思想家是()。
中华人民共和国恢复了在联合国合法席位的时间是()。
1861年俄国废除农奴制改革的主要作用是()。①造成资本的集中②扩大了国内市场③提供了自由劳动力④强化了中央集权
简述古巴导弹危机的过程。
周王室的两大官僚系统是()。
下列关于第三次科技革命的说法,不正确的是()。
为了加强对地方的控制,唐太宗根据山川形势,把全国划分成10个(),经常派官员监察地方官吏。
明治维新时期的土地改革,说法不正确的是()。
与前两次工业革命相比,第三次科技革命在能源结构上的主要变化是()
火的使用,是人类在征服自然的进程中所取得的伟大成果。人类开始使用天然火是在()。
随机试题
()是消化系统的起始部位。
A、15°B、60°C、70°D、80°E、140°上颌中切牙的唇面线与眶耳平面的交角约为
下列不属于骨髓增生异常综合症骨髓常见病态造血表现的是
下列关于债的移转的说法正确的是()。
系统误差可以消除,过失误差明显地歪曲试验结果,可以利用一定的准则从测得的数据中剔除,因此,在误差分析时只考虑随机误差即可。()
某拟建高速公路长105km,评价区域内无特殊生态敏感区和重要生态敏感区,则其生态影响评价需要的基本图件有()。
在薄壁墩与实心墩施工中,其控制要点不同之处有()。
A、 B、 C、 D、 B
编写如下程序:PrivateSubCommandl1-Click()DimxAsIntegerx=10Printfunl(x,12)+xEndSubPrivate.Functionfunl(mAsInteger,nAsInte
A、8hours.B、8o’clock.C、11hours.D、11o’clock.C在这个对话中,女士询问图书馆周六什么时间开馆,男士回答从上午8点到下午7点,一共是11个小时,故选C。
最新回复
(
0
)