首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知顺序表A,在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下,设计算法,将所有奇数号元素移到所有偶数号元素前。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。 (
已知顺序表A,在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下,设计算法,将所有奇数号元素移到所有偶数号元素前。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。 (
admin
2019-01-16
83
问题
已知顺序表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
学硕统考专业
相关试题推荐
第一个五年计划的具体时间段是()。
布雷顿森林体系
简述西欧专制制度的特点。
概述公元前8—前6世纪希腊海外殖民的背景、范围及影响。
“二战”后主要资本主义国家经济恢复和发展的杠杆是()。①政府采取宏观调控政策②发展国家垄断资本主义③充分利用科技成果④加强国际经济联系
第一次国共合作采取了共产党员以个人身份加入国民党的“党内合作”方式。最早提出这种方式的是()。
17世纪英国资产阶级革命中,曾利用了古老文件同专制王权作斗争,这一古老文件是()。
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(logn)的算法,确定树中第k个结点的位置。
—棵二叉树的后序遍历序列为DABEC,中序遍历序列为DFBAC,则先序遍历序列为()。
(11分)某图形显示器的分辨率为640×480,刷新频率为50Hz,且假定水平回扫期和垂直回扫期各占水平扫描周期和垂直扫描周期的20%,试计算图形显示器的行频、水平扫描周期、每个像素的读出时间和视频带宽。若分辨率提高到1024×768,刷新频率提高到60H
随机试题
新生儿,诊断为单侧完全性唇裂颌并单侧完全性腭裂,同时伴有鼻部畸形。唇裂的正畸治疗应开始于
人体内蛋白质种类远多于基因数的主要原因是
女性,32岁,因半年来胸闷不适,近1周昏厥发作3次来门诊治疗应选择
下列不属于监理工作中质量控制具体措施的是()。
中国国际航空公司的规定是:航班起飞前4小时到起飞后,退票费用是票面的()。
社会工作的功能不仅在个人及其()层面发挥作用,而且在社会整体的层面也发挥作用。
埃里克森的理论认为,人格的发展是一个逐渐形成的过程,12—18岁阶段的发展任务是培养()。
某计算机的存储系统由Cache一主存系统构成,Cache的存取周期为10ns,主存的存取周期为50ns。在CPU执行一段程序时,Cache完成存取的次数为4800次.主存完成的存取次数为200次,该Cache一主存系统的效率是()。
根据《选举法》的规定,对于乡级的人大代表,可以向县级人大常委会提出罢免要求的人数是()
甲、乙、丙三人合伙经营一电器商场,效益不佳,已欠债2万元。三人经协商一致邀有经营能力的丁加入到合伙之中,丁在被告知合伙经营状况后出资加入其中,并以合伙人的身份参与经营。两年后,该电器商场因故停业。对丁入伙前电器商场对外所欠的2万元债务,依法应当( )。
最新回复
(
0
)