首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知数组A[1……n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想; (2)根据设计思想,采用C或C++
已知数组A[1……n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想; (2)根据设计思想,采用C或C++
admin
2013-07-12
54
问题
已知数组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
学硕统考专业
相关试题推荐
19世纪中后期的日本资本主义尚未得到充分发展,但却成功地推翻了幕府的统治并进行了明治维新,其主要原因是()
下列不属于清统治者加强文化专制和思想控制的是()
中国人民抗日战争胜利的基本经验和历史意义。
1925年10月签订《洛迦诺公约》后,法国外长白里安认为:“我国的安全比以往任何时候都更有保障了。”对此说法不正确的一项是()。
1988年起,苏联民族矛盾激化,民族分离运动加剧,第二次较大规模的民族冲突是()。
改革开放以后,我国农村产业结构巨大的转变表现在()。
1543年,发表了解剖学专著《人体结构》的是()。
某机字长32位,采用定长操作码,单字长指令,共有机器指令100条,CPU内部有通用寄存器32个,可作变址寄存器用,存储器按字节编址,指令拟用直接寻址、间接寻址、变址寻址和相对寻址等4种寻址方式。(1)分别画出寻址方式由操作码指出和寻址方式由专用字
在二叉树的顺序存储中,每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系,因此可与三叉链表对应。若某二叉树共有n个结点,采用三叉链表存储时,每个结点的数据域需要d个字节,每个指针域占用4个字节,若采用顺序存储,则最后一个结点下标为k(
随机试题
根据医师执业注册制度,受理申请医师注册的卫生行政部门在收到注册申请后,应在自收到申请之日起多少日内作出准予注册或不予注册的书面答复
A.受纳与腐熟水谷B.主津C.贮藏与排泄胆汁D.主液E.贮尿和排尿小肠功能为
在管线布置中。除满足一般规定外,还应按专门规范或标准设计,哪种地区情况不属此类?[2003年第75题]
规划用电负荷的控制指标包括()。
下列各条中,()是英国密尔顿•凯恩斯(MiltonKeynes)规划的特点。
能鉴别学业水平高低、能力强弱的测验表明其()很高。
敬业主要是规范公民与职业的道德关系,奉献主要是规范公民与社会的道德关系和对待他人的()。
关于行政决策枢纽系统的说法,不正确的是()。
求下列极限:
Itwaslateintheafternoon,andIwasputtingthefinaltouchonapieceofwritingthatIwasfeelingprettygoodabout.Iwa
最新回复
(
0
)