首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知数组A[1……n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想; (2)根据设计思想,采用C或C++
已知数组A[1……n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想; (2)根据设计思想,采用C或C++
admin
2014-12-08
41
问题
已知数组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
学硕统考专业
相关试题推荐
下列哪一项最符合《附益法》的主要内容?()
表明第一次国共合作全面破裂的事件是()。
晚清时期下列武装力量出现的先后顺序是
下列选项中,不是由晁错提出的是()
“二战”爆发的原因是多种因素综合作用的结果,其中最根本的因素是()。
()自幼随父在西域成长,深悉西域道里、风土和政治情况。他编著的《西域记》一书,是范晔撰《后汉书.西域传》的重要根据。
1934年9月苏联加入国联,对此说法错误的一项是()。
最早以立法形式巩固大化改新成果的法令是()。
“二战”期间,美国研制了原子弹并用于实践;1946年美国投入使用的第一台电子计算机最初是用于计算炮弹弹道的;德国人研制成功的远程液体火箭是用于空袭英国的。以上史实说明()。
如果互联的局域网高层分别采用TCP/IP协议与SPX/IPX协议,那么我们可以选择的多个网络互联设备应该是()。
随机试题
五味子、五倍子均可用于治疗
根据《建筑施工场界噪声排放标准GB12523——2011规定,混凝土搅拌机夜间施工时的施工噪声应控制在()dB(A)以内。
根据民事诉讼法的规定,因不动产纠纷提起的诉讼,由()人民法院管辖。
业主可以是个人、集体、国家,在实际操作中,具备业主身份的情况有()。
下列资产损失,属于由企业自行计算在企业所得税前扣除的有()。
关于留置权的效力,下列说法正确的有()。
儿童从事一项活动能够善始善终,说明他的注意具有很好的()。
朱珂是北京市向阳路中学的一名老师。学校近期将召开一次家长会,校领导决定由她负责制作家长会通知。请根据考生文件夹下的相关资料及示例,按下列要求帮助朱珂老师完成家长会通知的制作工作:将纸张大小设为A4,上、左、右页边距均为2.5厘米,下边距为2厘米,页眉、
つかれたので、東京に着いたら、すぐホテルにとまりました。とまり
Afterthedevastatingearthquake,the______armywasimmediatelycalledintoevacuatetheweakandinjured.
最新回复
(
0
)