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

admin2023-02-06 110

问题已知顺序表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

学硕统考专业

问题解决是个体在日常生活中思维活动最普遍、最重要的形式。从19世纪末开始，心理学家就不断使用实验方法来研究问题解决。以下属于问题解决研究的实验有()。

布鲁纳认为不论教师教什么学科，务必使学生理解该学科的基本结构。依此而建立的课程理论是()。

我国地大物博，许多风景名胜和古迹分布在名山大川之中。下列关于我国风景名胜的叙述中，错误的是：

下列有关生活中常见的物理常识的叙述正确的是：

一只闹钟的秒针顶点距离表盘圆心4厘米，分针顶点距离表盘圆心3厘米。小王烧开一壶水的时间内，秒针顶点累计移动了40厘米。那么这一时间段内，分针顶点与表盘圆心的连线扫过的扇形面积为多少平方厘米?

有关二叉树下列说法正确的是()。

非主要矛盾

可复性牙髓炎行盖髓治疗术后复诊时间为

在民法理论上，权利人不行使权利的事实状态持续经过法定期间，即依法发生权利不受法律保护后果的制度称为()。

下列各项中，注册会计师评价内部审计的客观性时通常不需要考虑的是()。

依据新课程改革理念，我国明确区分义务教育与高中阶段教育，建立合理的课程结构，确立小学阶段的课程以分科课程为主。()

关于我国的兵役制度，下列说法不正确的是()。

在做完形填空时，对空格的知觉加工过程为()。

Theterm"formallearning"referstoalllearningwhichtakesplaceintheclassroomregardlessofwhethersuchlearningisinfo

设栈S的初始状态为空。元素a、b、c、d、e、f依次通过栈S，若出栈的顺序为b、d、c、f、e、a，则栈S的容量至少应该为()。

Nowadays,airtravelisvery【C1】______WearenotsurprisedwhenwewatchonTVthatapoliticianhastalkedwithFrenchPresiden