首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知数组A[1……n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想; (2)根据设计思想,采用C或C++
已知数组A[1……n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想; (2)根据设计思想,采用C或C++
admin
2013-07-12
27
问题
已知数组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://jikaoti.com/ti/QVajFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
第二次鸦片战争后,根据不平等条约开放对外通商口岸最多的省是()。
1861年俄国废除农奴制改革的主要作用是()。①造成资本的集中②扩大了国内市场③提供了自由劳动力④强化了中央集权
下列现象由中国近代社会的半殖民地半封建性质所决定的有()。①民族资产阶级提不出彻底的民主革命纲领②中国无产阶级先于中国民族资产阶级而产生③帝国主义在华的“租界”林立④中国革命必须走农村包围城市的道路
中共十六届五中全会提出,建设社会主义新农村的要求是生产发展和()。
建立中国道教史上第一个成熟的神仙系统的是()。
继承并发展德谟克利特和伊壁鸠鲁的“原子论”,认为宇宙万物都是由原子构成的,并按照物质本身所特有的规律发展的罗马共和国时期的哲学家()。
与前两次工业革命相比,第三次科技革命在能源结构上的主要变化是()
中古时代实行索贡巡行赋税征收方式的国家是()。
由元素序列(27,16,75,38,51)构造平衡二叉树,则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)是()。
随机试题
上颌第一磨牙的主要功能尖是
体外冲击波碎石的禁忌证中,下列哪项是错误的
( )是指有权代表国家投资的部门或机构以国有资产向公司投资的股份。
每股盈余最大化的缺点是没有考虑()。
《中小学班主任工作规定》指出,班主任是中小学日常思想品德教育和学生管理工作的主要实施者。下列说法正确的是()
阅读下文。回答下列题:教育的目的是什么?教育的目的就是帮助人获得生存与生活的本领。不管一个人将来从事什么工作,都必须能继续自己的生活,解决日常生活中的问题。但我们的教育一直有一种忽视和轻视日常生活的倾向,在教育中一直将知识的学习与日常生活相脱离。
材料注:东部地区包括北京、天津、河北、上海、江苏、浙江、福建、山东、广东、海南10个省(市);中部地区包括山西、安徽、江西、河南、湖北、湖南6个省;西部地区包括内蒙古、广西、重庆、四川、贵州、云南、西藏、陕西、甘肃、青海、宁夏、新疆12个省(市、自治区
下列描述中,属于冯.诺依曼体系结构的特点是()。①采用流水线技术;②指令和数据均以二进制表示;③存储程序并且存储时不区别数据和指令。
我国社会主义市场经济的特点是
NowthepoliticsofUShealthreformisinamessbuttheoddsonabillpassingintheendareimproving.Itwillnotbeatidy
最新回复
(
0
)