首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知顺序表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=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
学硕统考专业
相关试题推荐
以下不属于泰州学派的哲学思想的是()。
真理标准问题大讨论
巴黎和会上,英美主张把原德国在山东的权利转让给日本,华盛顿会议又表示支持中国让日本归还山东的要求,英美态度发生变化的根本原因是()。
【井冈山革命根据地】
租庸调制对农业生产的最大作用是()。
1980-1987年撒哈拉以南非洲人均国民生产总值增长率为-2.9%。大部分国家经济急剧下滑,非洲的80年代被称“为失去发展的十年”。出现这现象关键原因在于这些国家
下列关于20世纪历史的叙述,全部错误的是()。①朝鲜建国的时间早于中国②1948年3月,英国、法国、比利时、荷兰、卢森堡5国缔结了《合作和集体防御条约》即《五国和约》③1950年,周恩来到达莫斯科,中苏缔结了《中苏互不侵犯条约》,标志着社会主
新文化运动前期的指导思想是()。
下列几种排序方法中,要求内存量最大的是()。
设有A,B,C,D4台主机都处在同一个物理网络中,A主机的IP地址是192.155.28.112,B主机的IP地址是192.155.28.120,C主机的IP地址是192.155.28.135,D主机的IP地址是192.155.28.202。共
随机试题
驾驶机动车在路口看到这种信号灯亮时,要加速通过。
Onafivetothreevote,theSupremeCourtknockedoutmuchofArizona’simmigrationlawMonday—amodestpolicyvictoryforthe
考虑诊断可能是你决定为该患者选用哪类抗生素
关于世界银行咨询服务(采购)最低费用评审方法的表述中,不正确的是()。
构成建设工程投资的要素包括人工、材料、施工机械等,要素价格是由( )形成的。
下列属于货币经纪公司的服务对象的有()。
教学从其本质上讲是【】
根据以下资料,回答下列小题。能够从上述资料中推出的是()。
Goingdownahillislike______.We______getridofbadhabits.
Despitetheweb,wewatchmoretelevisionthanever.Inthechaosoftoday’smediaandtechnologybrawl—iPodvs.Zune,Googl
最新回复
(
0
)