首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知顺序表A,在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下,设计算法,将所有奇数号元素移到所有偶数号元素前。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。 (
已知顺序表A,在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下,设计算法,将所有奇数号元素移到所有偶数号元素前。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。 (
admin
2019-01-16
29
问题
已知顺序表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://jikaoti.com/ti/bufjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述中、苏分歧和中、苏同盟关系破裂的原因及其影响。
詹天佑自主设计修建了中国第一条铁路是在()。
阅读材料,回答以下问题:重庆中央党部,暨中央执监委员诸同志均鉴:今年4月,临时全国代表大会宣言,说明此次抗战之原因,曰:“自塘沽协定以来,吾人所以忍辱负重与倭国周旋,无非欲停止军事行动,采用和平方法,先谋北方各省之保全,再进而谋东北四省问题之合理解决,
根据以下《萨利克法典》的条文,分析公元5—6世纪法兰克人的社会状况:第3章,关于偷窃牛羊。(1)如果有人偷窃一头公牛或带犊的母牛,应罚付1400银币,折合35金币。第27章,关于各种盗窃。(6)如果有人闯入人家的园地,意图窃盗,应罚付600银币,折合1
最早以立法形式巩固大化改新成果的法令是()。
使徒兄弟会
一组记录的关键字为{25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序表,用归并排序方法对该序列进行一趟归并后的结果是()。
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
某中央处理器的数据通路如图所示。MDR为内存数据寄存器,PC为程序计数器,IR为指令寄存器。所有的单线箭头为控制微命令。(1)请说明图中部件X的名称和功能、寄存器Y的名称和功能。(2)请解释:为什么要设置T暂存器?(3)假定指
某单位有1个总部和6个分部,各个部门都有自己的局域网。该单位申请了6个C类IP地址202.115.10.0/24~202.115.15.0/24,其中总部与分部4共用一个C类地址。网络采用R1~R7共7台路由器,采用动态路由协议OSPF,并划分了3个OSP
随机试题
企业选择复用包装决策的目的是
男,50岁胃大部切除患者,出现贫血,其主要原因是
某妇,35岁,月经过多2年,自己发现下腹部包块3个月,贫血貌,妇检:宫颈光滑,子宫增大如男拳大小,活动,双侧附件区(-)。B超提示子宫巨大肌瘤。在当地医院行子宫切除术,术后48小时拔尿管后,尿液自阴道流出半年。损伤性尿瘘行修补的时间是()
纬度38°地区的多层住宅建筑的平屋面防水、保温构造,下列哪一种构造层次正确?[2001—085]
被控对象的时间常数反映了对象在阶跃作用下被控变量变化的快慢速度,为对象惯性大小的常数,时间常数(),()大,被控变量变化速度慢,控制较平稳。
下列关于公积金个人住房贷款的特点表述错误的是()。
下列有关医学的知识,说法正确的是()。
下列句子中,有歧义的一句是()。
剪刀:理发师:头发
在全国人大闭会期间,全国人大常委会根据国务院总理的提名,有权决定的人选不包括( )。
最新回复
(
0
)