首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知顺序表A,在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下,设计算法,将所有奇数号元素移到所有偶数号元素前。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。 (
已知顺序表A,在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下,设计算法,将所有奇数号元素移到所有偶数号元素前。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。 (
admin
2019-08-01
80
问题
已知顺序表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
学硕统考专业
相关试题推荐
清廷实行厘金制度的时间是()。
武则天时期,为了管理天山以北的广大区域而设立了()。
日本法西斯与德国法西斯相比,突出的特点是()
我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说,如炎帝和黄帝两个部落曾战于(),结果黄帝取得了胜利。
骑士团是罗马教皇推行反宗教改革的工具,其中在波罗的海南岸发挥重要作用的骑士团是()。
1141年,金与南宋双方签订协议,规定以淮水和大散关为宋金的分界线,此协议称为()。
1947年,刘邓大军千里跃进大别山,揭开了战略反攻的序幕。据此回答问题:中共中央将战略决战的方向首先指向的是()
格拉古兄弟改革
一个TCP连接总是以1KB的最大段发送TCP段,发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时,如果接下来的4个RTT(往返时间)时间内的TCP段的传输都是成功的,那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时,拥塞窗口大小是
已知有6个顶点(顶点编号为0~5)的有向带权图G,其邻接矩阵A为上三角矩阵,按行为主序(行优先)保存在如下的一维数组中。要求:求图G的关键路径,并计算该关键路径的长度。
随机试题
____________是指组织在长期的实践活动中所形成的并且为组织成员普遍认可和遵循的具有本组织特色的价值观念、团体意识、工作作风、行为规范和思维方式的总和。
在血浆中主要结合运输磺胺类药物的蛋白质是
腓骨颈骨折易损伤
青霉素在碱性条件下水解生成的降解产物为
工程监理单位和监理工程师应当按照( )实施监理,并对建设工程安全生产承担监理责任。
根据以下资料,回答下列问题。2011年上半年,我国国内生产总值为204459亿元。其中,第一产业增加值15700亿元,同比增长3.2%;第二产业增加值102178亿元,增长11.0%;第三产业增加值86581亿元,增长9.2%。从环比看,二季度国
理性情绪治疗模式对人的心理失调的原因和机制进行了深入的分析,提出比较有影响的ABC理论,其中A代表()。
我国在南极新建的科学考察站是什么?
鸦片战争后十年,英国人发现他们仍未达到发动战争的目的,拥有庞大人口的中国,消费英国商品仍不及荷兰的一半。当时英国人将出现这一问题的原因归结于()。
信赖保护原则是行政法的一项基本原则,是指政府对自己作出的行为或承诺应守信用,不得随意变更,反复无常。根据上述定义,下列违反信赖保护原则的是()。
最新回复
(
0
)