首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知顺序表A,在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下,设计算法,将所有奇数号元素移到所有偶数号元素前。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。 (
已知顺序表A,在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下,设计算法,将所有奇数号元素移到所有偶数号元素前。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。 (
admin
2019-08-01
74
问题
已知顺序表A,在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下,设计算法,将所有奇数号元素移到所有偶数号元素前。
(1)给出算法的基本设计思想。
(2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。
选项
答案
(1)基本的设计思想:先将偶数号元素复制到一个辅助空间,然后整理数组剩下的奇数号元素,最后将辅助空间中的元素复制到数组的后半部分,但这种思路的空间复杂度为O(n)。 另一种思路: ①在数组尾部从后往前找到第一个奇数号元素,将此元素与其前面的偶数号元素交换。这样,就形成了两个前后相连且相对顺序不变的奇数号元素“块”。 ②暂存①中“块”前面的偶数号元素,将“块”内奇数号结点依次前移,然后将暂存的偶数号结点复制到空出来的数组单元中。就形成了三个连续的奇数号元素“块”。 ③暂存②中“块”前面的偶数号元素,将“块”内奇数号结点依次前移,然后将暂存的偶数号结点复制到空出来的数组单元中。就形成了四个连续的奇数号元素“块”。 ④如此继续,直到前一步的“块”前没有元素为止。 (2)算法的设计如下: void Swap(ElemType A[],int n) { int i=n,v=l: //i为工作指针,初始假设n为奇数,v为“块”的大小 ElemType temp: //辅助变量 if(n%2==0)i:n一1: //若n为偶数,则令i为n—1 while(i>1){ //假设数组从1开始存放。当i=1时,气泡浮出水面 temp=A[i一1]; //将“块”前的偶数号元素暂存 for(int j=0;j
2)。虽然时间复杂度为O(n
2
),但因n
2
前的系数很小,实际达到的效率是很高的。算法的空间复杂度为O(1)。
解析
转载请注明原文地址:https://kaotiyun.com/show/AkCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
1980-1987年撒哈拉以南非洲人均国民生产总值增长率为-2.9%。大部分国家经济急剧下滑,非洲的80年代被称“为失去发展的十年”。出现这现象关键原因在于这些国家
1940年毛泽东的《新民主主义论》:“而所谓民主主义,现在已不是旧范畴的民主主义,已不是日民主主义,而是新范畴的民主主义,而是新民主主义”。毛泽东分民主革命的两个阶段主要依据是
“中共二大宣言:加给中国人民,(无论是资产阶级、工人或农人)最大的痛苦的是资本帝国主义和军阀官僚的封建势力”。因此,反对帝国主义和封建势力的“民主主义的革命运动是极有意义的”由此引之,当时中共
世界天文史上最早实地测量子午线的记录是由谁进行的?()
论述科举制度的演变及其历史作用。
1947年,刘邓大军千里跃进大别山,揭开了战略反攻的序幕。 据此回答问题:之所以把中原地区作为反攻的方向,主要是由于该地区()
曾经来华留学,并在日本大化改新中发挥重要作用的是()。
编写一个算法,实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。
已知在二叉树中,T为根结点,*p和*q为二叉树中两个结点,试编写求距离它们最近的共同祖先的算法。
下列选项中,降低进程优先级的合理时机是____。
随机试题
事业部制按区域划分可分为产品事业部和区域事业部,请谈谈其各自的优缺点,并结合其优缺点试说明事业部制的优缺点。
()是计算机由工作状态转为等待状态的一种节能方式。
低应变反射波法检测桩身完整性,当激励源产生的压缩波向下传播时遇到桩身波阻抗变化的界面时,压缩入射波在波阻抗界面产生()。
某加油和CNG加气合建站设置了2个30m3的汽油储罐,1个50m3的柴油储罐,2个10m3的CNG储罐,则该加油加气合建站属于()。
发明专利申请一般需要经过初步审查和实质审查两个阶段;实用新型和外观设计申请只需经过初步审查。()
下列运动的物体中,受力平衡的是()。
从所给的四个选项中,选择最合适的一个填入问号处,使之呈现一定的规律性。
GenerationsofAmericanshavebeenbrought【C1】______tobelievethatagoodbreakfastisimportantforhealth.Eatingbreakfasta
A、Hestudiedcartooning.B、Hestayedathome.C、Hewentabroad.D、Heworkedforacompany.C信息明示题。由文章第三段末句可知,他参加了红十字会,待在法国直到战争结束
ThehomelessmakeupagrowingpercentageofAmerica’spopulation.【C1】______homelessnesshasreachedsuchproportionsthatlocal
最新回复
(
0
)