首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知顺序表A,在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下,设计算法,将所有奇数号元素移到所有偶数号元素前。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。 (
已知顺序表A,在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下,设计算法,将所有奇数号元素移到所有偶数号元素前。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。 (
admin
2019-08-01
48
问题
已知顺序表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
学硕统考专业
相关试题推荐
赋税是我国古代国家宏观管理经济的重要手段。 据此回答问题:乾隆年间的税种有()
下列哪两个国家是第二次工业革命的发源地和“中心”?
1939年前后,中国政治思想界展开关于三民主义问题争论的根本原因是()。
三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P3每次用getev
若干个等待访问磁盘者依次要访问的柱面为20,44,40,4,80,12,76,假设每移动一个柱面需要3毫秒时间,移动臂当前位于40号柱面,请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。(1)先来先服务算法;(2)最短寻找时间
已知一组关键字为(26,36,41,38,44,15,68,12,6,51,25),用链地址法解决冲突。假设装填因子a=0.75,散列函数的形式为H(K)=KMODP,回答下列问题:(1)构造散列函数。(2)画出散列表。(
Demandpaging算法是paging算法在虚拟存储空间管理的扩展。其主要的改进是:仅当需要访问某页面时,如果它不在内存,把它调入内存。按照这个思路,将segmentation算法(段式存储管理算法)扩展到虚拟存储空间管理,也可以产生类似的算法,不妨
试比较脱机I/O和联机I/O。
试比较脱机I/O和联机I/Oo
随机试题
独立说
在Windows中,要移动某一个窗口时,应先将鼠标指在
A.高钾血症B.低钾血症C.高钠血症D.低钠血症E.低钙血症猫肠梗阻,灌肠和静脉注射5%葡萄糖盐水治疗后症状缓解,每天灌服糖水、营养餐和呋塞米。1周后,该猫无力,头向患侧屈曲,心电图T波异常,Q-T间期延长和U波增高。可能伴随的是()
关于DiGeorge综合征,下列哪项是错误的
对垄断进行管制的经济政策包括()。
31,37,25,49,1,()。
刘某从甲家具公司购买发票上称为橡木的沙发一组,一年半后,经友人告知,该沙发其实为橡胶木,一字之差,价钱相差甚远。经鉴定,果然如此。刘某遂要求甲家具公司退货赔款。对此,下列表述中,错误的是( )。
将法的本质归结为理性,是以下哪些法学家的观点()
被置于中国传统文化“三不朽”之首的是()
区域D:(χ2+y2)2≤χ2-y2所围成的面积为_______.
最新回复
(
0
)