已知顺序表A，在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下，设计算法，将所有奇数号元素移到所有偶数号元素前。 (1)给出算法的基本设计思想。 (2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。 (3)说明你所设计算法的时

admin2023-02-06 102

问题已知顺序表A，在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下，设计算法，将所有奇数号元素移到所有偶数号元素前。
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。

选项

答案(1)基本的设计思想：先将偶数号元素复制到一个辅助空间，然后整理数组剩下的奇数号元素，最后将辅助空间中的元素复制到数组的后半部分，但这种思路的空间复杂度为O(n)。另一种思路： ①在数组尾部从后往前找到第一个奇数号元素，将此元素与其前面的偶数号元素交换。这样，就形成了两个前后相连且相对顺序不变的奇数号元素“块”。 ②暂存①中“块”前面的偶数号元素，将“块”内奇数号结点依次前移，然后将暂存的偶数号结点复制到空出来的数组单元中。就形成了三个连续的奇数号元素“块”。 ③暂存②中“块”前面的偶数号元素，将“块”内奇数号结点依次前移，然后将暂存的偶数号结点复制到空出来的数组单元中。就形成了四个连续的奇数号元素“块”。④如此继续，直到前一步的“块”前没有元素为止。 (2)算法的设计如下： [*] (3)一共进行了n／2次交换，每次交换的元素个数从1-n／2，因此时间复杂度为O(n²)。虽然时间复杂度为O(n²)，但因n²前的系数很小，实际达到的效率是很高的。算法的空间复杂度为O(1)。

解析

转载请注明原文地址:https://kaotiyun.com/show/QEwD777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

在学习“一天中太阳高度的变化和运动方位的变化”时，地理老师让学生通过留意学校内物体在不同时刻其影子的长短以及其影子的方位变化来学习。该老师所用的教学方法属于()。

在教育过程中，教师要理解、尊重、鼓励学生个性发展，成为学生的知心朋友，但同时也要与学生拉开一定的距离，维护教师的权威。两者处理不好，就容易构成矛盾。这反映了()。

教育要适应儿童身心发展的规律，所以教育必须被动迁就儿童身心发展的现有水平和特点。()

板书要求整齐、规范、美观，因此板书的文字、图表等格式要统一，不得有变化。()

培养正确的集体舆论的方法是()。

教师应当崇尚科学精神，树立终身学习理念，拓宽知识视野，更新知识结构。()

下列年份中，在职职工参保人数同比增速大小排序错误的是()。

某企业举行职业技能大赛，3个下属分公司均选2名员工参赛。若同一分公司的员工比赛时出场顺序不能相邻，则参赛的6名员工不同的出场顺序共有：

在双向链表存储结构中，删除P所指的结点时须修改指针()。

正常人体温一般维持在37℃左右，这是由于在下丘脑体温调节中枢控制下，使_和_平衡的结果。

简述新时代青年如何成就出彩人生。

A．溃疡呈环形与肠的长轴垂直B．溃疡呈长椭圆形与肠的长轴平行C．溃疡呈烧瓶状口小底大D．溃疡表浅呈地图状

肺结核病人应采取

湿性坏疽常发生在

适用于建筑的天窗、采光屋顶、阳台及须有防盗、防抢功能要求的营业柜台的遮挡部位的安全玻璃是()。

设矩阵，若集合Ω={1，2}，则线性方程组Ax=b有无穷多解的充分必要条件为()。

表是SQL语言()、()、()的基本数据结构。

ApersonbecomespartoftheChristiancommunitythroughbaptism—itisamatterofchoice【21】______birth.TheChristianc

A、Peopleallovertheworldenjoyfeedingbirds.B、Preparedbirdfoodisrarelyseeninshopsandmarkets.C、Feedingbirdsisno

计算机408

学硕统考专业

在学习“一天中太阳高度的变化和运动方位的变化”时，地理老师让学生通过留意学校内物体在不同时刻其影子的长短以及其影子的方位变化来学习。该老师所用的教学方法属于()。

在教育过程中，教师要理解、尊重、鼓励学生个性发展，成为学生的知心朋友，但同时也要与学生拉开一定的距离，维护教师的权威。两者处理不好，就容易构成矛盾。这反映了()。

教育要适应儿童身心发展的规律，所以教育必须被动迁就儿童身心发展的现有水平和特点。()

板书要求整齐、规范、美观，因此板书的文字、图表等格式要统一，不得有变化。()

培养正确的集体舆论的方法是()。

教师应当崇尚科学精神，树立终身学习理念，拓宽知识视野，更新知识结构。()

下列年份中，在职职工参保人数同比增速大小排序错误的是()。

某企业举行职业技能大赛，3个下属分公司均选2名员工参赛。若同一分公司的员工比赛时出场顺序不能相邻，则参赛的6名员工不同的出场顺序共有：

在双向链表存储结构中，删除P所指的结点时须修改指针()。

正常人体温一般维持在37℃左右，这是由于在下丘脑体温调节中枢控制下，使___________和___________平衡的结果。

简述新时代青年如何成就出彩人生。

A．溃疡呈环形与肠的长轴垂直B．溃疡呈长椭圆形与肠的长轴平行C．溃疡呈烧瓶状口小底大D．溃疡表浅呈地图状

肺结核病人应采取

湿性坏疽常发生在

适用于建筑的天窗、采光屋顶、阳台及须有防盗、防抢功能要求的营业柜台的遮挡部位的安全玻璃是()。

设矩阵，若集合Ω={1，2}，则线性方程组Ax=b有无穷多解的充分必要条件为()。

表是SQL语言()、()、()的基本数据结构。

ApersonbecomespartoftheChristiancommunitythroughbaptism—itisamatterofchoice【21】______birth.TheChristianc

A、Peopleallovertheworldenjoyfeedingbirds.B、Preparedbirdfoodisrarelyseeninshopsandmarkets.C、Feedingbirdsisno

正常人体温一般维持在37℃左右，这是由于在下丘脑体温调节中枢控制下，使_和_平衡的结果。