首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知顺序表A,在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下,设计算法,将所有奇数号元素移到所有偶数号元素前。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。 (
已知顺序表A,在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下,设计算法,将所有奇数号元素移到所有偶数号元素前。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。 (
admin
2019-01-16
52
问题
已知顺序表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
2)。虽然时间复杂度为O(n
2
),但因n
2
前的系数很小,实际达到的效率是很高的。算法的空间复杂度为O(1)。
解析
转载请注明原文地址:https://kaotiyun.com/show/neRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
法国里昂工人起义提出:“我们只有一个口号‘人人自由平等!’”英国宪章运动请愿书提出:“我们竭尽自由人的义务,就应享受自由人的权利。我们要求普遍选举。”这些要求表明()。①带有空想社会主义色彩②当时工人的要求还没有超出资产阶级民主主义的范畴
阅读材料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为仁,以神
中国共产党在民主革命时期的不同阶段实行了不同的土地政策,其主要的根据是()。
年鉴学派开创了总体史研究方法,其代表人物马克·布洛赫研究中世纪的代表作是()
下列哪两个国家是第二次工业革命的发源地和“中心”?
1908年安庆新军起义是由()领导的。
1947年,刘邓大军千里跃进大别山,揭开了战略反攻的序幕。据此回答问题:之所以把中原地区作为反攻的方向,主要是由于该地区()
电子计算机的发展经过了四代,①电子数值积分计算机(ENIAC);②集成电路计算机;③大规模集成电路计算机;④晶体管计算机;⑤人工智能计算机,其先后顺序是()。
(1)所有事件的最早发生时间如下:Ve(1)=0Ve(2)==5Ve(3)=6Ve(4)=max{ve(2)+3,ve(3)+6}=12Ve(5)=max{ve(3)+3,ve(4)+3}=15Ve(6)=ve(4)+4=16Ve(7)=ve
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(logn)的算法,确定树中第k个结点的位置。
随机试题
求幂级数1+2x+3x2+…+nxn-1+…的和函数
正常成人的视乳头直径约为
【背景资料】某机电安装公司,为进入某钢铁企业的建筑市场,采取低价中标的方法,承接了高炉热风炉鼓风机安装任务。由于利润低,施工单位资源投入不足,项目经理对工程积极性不大,造成施工准备不充分,影响了施工进度和质量。项目经理在电缆采购时只注重价格.使一些伪劣电
根据《企业所得税法》的规定,下列资产的税务处理正确的有()。
包装设计指的是对商品的()进行符合保护性、便利性、经济性、审美性和促销性的整体设计。
下列语句中,没有语病的一句为:
在一个半圆环上共有13个点,以这些点为顶点,可画出多少个三角形?
下列国家中,采用普通法院模式进行违宪审查的是()
证明:当0<a<b<π时,bsinb+2cosb+πb>asina+2cosa+πa.
Thegroundshouldnotbetoowetortoodry.Thegroundshouldbeneithertoowet______toodry.
最新回复
(
0
)