首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知顺序表A,在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下,设计算法,将所有奇数号元素移到所有偶数号元素前。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。 (
已知顺序表A,在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下,设计算法,将所有奇数号元素移到所有偶数号元素前。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。 (
admin
2019-01-16
76
问题
已知顺序表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
学硕统考专业
相关试题推荐
春秋战国时期,提出“祸兮福之所倚,福兮祸之所伏”的思想家是()。
简述破坏圣像运动的过程、原因及其影响。
佛教向亚洲国家传播始于印度的哪个时代?()
古巴革命党是由古巴民族英雄、民族解放运动的领袖()于1892年在美国纽约建立的。
基辅罗斯国家对居民征税的方式是()。
我国历史上一次有周密计划、经过长期准备并利用宗教形式组织和发动的农民起义是()。
1936年,张学良和杨虎城发动的西安事变()。①是一次具有爱国意义的兵变②民族矛盾激化的结果③检验了中国社会各阶级的抗日态度④促成了抗日民族统一战线初步形成
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
某机字长32位,总线数据线宽度是16位,一个总线周期占用4个时钟周期,总线时钟频率为10MHz,则总线带宽是()。
设二维数组A[6][10],每个数组元素占用4个存储单元,若按行优先顺序存放的数组元素,a[0][O]的存储地址为860,则a[3][5]的存储地址为()。
随机试题
颅脑损伤病人GCS评分为13~15分表示()
A、β1受体B、β2受体C、M受体D、N1受体E、N2受体骨骼肌运动终板上的受体是
A.心包叩击音B.二尖瓣开瓣音C.喀喇音D.Austin一Flint杂音E.Graham一steell杂音严重主动脉瓣关闭不全者可听到
缺铁性贫血用铁剂治疗后的血象首先表现为
某男,35岁。归国人员。诊断为艾滋病2年,近日出现咯血及上消化道出血,B超提示:有胸腔积液;胸片提示:肺门淋巴结肿大及其周围结节样浸润,并有双侧间质性改变。本例患者治疗应使用
药物的安全范围是指
下列有关基础工程施工的说法中,正确的是()。
社会主义道德的核心内容和集中体现是爱国主义。
求积分D:|x|≤1,0≤y≤2.
TheHistoryofChineseAmericans[A]ChinesehavebeenintheUnitedStatesforalmosttwohundredyears.Infact,theChines
最新回复
(
0
)