首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知顺序表A,在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下,设计算法,将所有奇数号元素移到所有偶数号元素前。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。 (
已知顺序表A,在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下,设计算法,将所有奇数号元素移到所有偶数号元素前。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。 (
admin
2019-08-01
44
问题
已知顺序表A,在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下,设计算法,将所有奇数号元素移到所有偶数号元素前。
(1)给出算法的基本设计思想。
(2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。
选项
答案
(1)基本的设计思想:先将偶数号元素复制到一个辅助空间,然后整理数组剩下的奇数号元素,最后将辅助空间中的元素复制到数组的后半部分,但这种思路的空间复杂度为O(n)。 另一种思路: ①在数组尾部从后往前找到第一个奇数号元素,将此元素与其前面的偶数号元素交换。这样,就形成了两个前后相连且相对顺序不变的奇数号元素“块”。 ②暂存①中“块”前面的偶数号元素,将“块”内奇数号结点依次前移,然后将暂存的偶数号结点复制到空出来的数组单元中。就形成了三个连续的奇数号元素“块”。 ③暂存②中“块”前面的偶数号元素,将“块”内奇数号结点依次前移,然后将暂存的偶数号结点复制到空出来的数组单元中。就形成了四个连续的奇数号元素“块”。 ④如此继续,直到前一步的“块”前没有元素为止。 (2)算法的设计如下: void Swap(ElemType A[],int n){ int i=n,v=1; //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<v;j++) //将大小为v的“块”整体向前平移 A[i一1+j]=A[i+j] //从前往后依次向前平移 A[i+v一1]=temp: //暂存的奇数号元素复制到平移后空出的位置 i一一;v++; //指针向前,块大小增1 }//while } (3)一共进行了n/2次交换,每次交换的元素个数从1一n/2,因此时间复杂度为O(n
2
)。虽然时间复杂度为O(n
2
),但因n
2
前的系数很小,实际达到的效率是很高的。算法的空间复杂度为O(1)。
解析
转载请注明原文地址:https://kaotiyun.com/show/jACi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
列宁称马克思、恩格斯是“19世纪人类三个最先进国家中三种主要思潮的继承人和天才的完成者”。这里“三个最先进国家”指的是()。
晋察冀抗日根据地
马克思说:巴黎公社“只不过是在特殊条件下的一个城市起义”。其含义是()。
下列长征事件的正确顺序是()。 ①四渡赤水②召开遵义会议③吴起镇会师④飞夺泸定桥
对三国鼎立局面的形成起到关键性作用的战役是()。
甲骨文的发现是19世纪20世纪之交中国考古学最重要的发现之一,为重新认识三代的历史与文化奠定了基础,开辟了坦途,可称之为中国文化史的里程碑。根据所学知识回答问题:在甲骨文的研究流域,对甲骨文研究作出了重大贡献,被后人称为“甲骨四堂”的四位学者是(
三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P3每次用getev
下列几种排序方法中,要求内存量最大的是()。
如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题:(1)该TCP/IP网络使用的是哪一类IP地址。(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构
试比较脱机I/O和联机I/Oo
随机试题
政府机关、大学、军队、大型国企的宿舍区属于()。
简述职位分析问卷的优缺点。
下面有关社区的说法哪个是错误的
A.乳腺单纯切除术B.乳腺癌局部切除+腋窝淋巴结清扫术C.乳腺癌根治术D.乳腺癌改良根治术E.乳腺癌姑息切除术30岁,女性,左乳外上象限一1cm×1cm肿块,质硬,细胞学检查见癌细胞。应采取手术为
患者,男性,36岁,1天前搬家时腰扭伤。腰剧痛并向右下肢放射,不能平卧,咳嗽加剧,痛窜至足背,伴麻木,大小便正常。查体:腰背肌痉挛,L4~5椎旁压痛,腰向前弯曲受限,右下肢直腿抬高受限,膝腱与跟腱反射正常,肌力正常,足背与小腿外侧感觉过敏。下列的治疗方
容易闻及二尖瓣杂音的体位是
下列四个部位,哪个部位选用的建筑用料是正确的?[1999—119]
企业在员工培训过程中所发生的一切费用统称为()。
应用心理学的理论和技术,对来访者的心理活动和人格特征讲行评估和鉴定,从而确定其心理变化的程度和性质的过程。这是()
LookAfterYourVoiceOftenspeakersatameetingexperiencedrymouthsandaskforaglassofwater.Youcansolvetheprob
最新回复
(
0
)