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

admin2023-02-06 81

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

学硕统考专业

美育，又称美感教育。下列选项中，不属于美育的主要任务的是()。

教师不仅肩负传道授业解惑的职责，致力于发展学生的智力，而且要培育学生良好的思想品德，促进学生的身心健康发展。这主要体现的是教师劳动的()特点。

下列关于课程计划编制原则的说法正确的是()。

关于教师和学生关系的两个对立观点是()。

学生的认知发展虽然具有一定的方向和先后顺序，但是这种发展是可逆的。()

教育法律关系中两个最重要的主体是()。

人体已经适应了地表生活，进入太空后，难免会出现________反应，毕竟细胞间的相互作用与在地表时迥异。填入画横线分最恰当的一项是：

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

经颞窗彩色多普勒检查脑动脉，哪一根血管检查成功率最高

液压传动可以实现无级变速。()

用递归法求1+2+3+4+5

不会引起胸腔积液的疾病是

来源于动物成熟雄体香囊中的干燥分泌物的药材是

关于原始凭证的错误更正，《会计法》主要有哪些规定?

某普通合伙企业的合伙人包括有限责任公司甲、乙，自然人丙、丁。根据合伙企业法律制度的规定，下列情形中，属于当然退伙事由的是()。

建立假说的有效工具是()。

根据《中华人民共和国人民警察使用警械和武器条例》的规定，不属于人民警察使用警械和武器的基本原则的是：

猪：猪肝