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

admin2023-02-06 61

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

学硕统考专业

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

课程计划是课程安排的整体规划，是根据教育目的以及不同层次和类型的学校的培养目标，由教育主管部门制定的有关学校教育教学的指导性文件。课程计划的主要内容不包括()。

由于正在创设国家级卫生城区，某地党委、政府多个主管部门联合行文时，在公文版头部分标明多个部门的发文字号。()

课程设计就是对课程的各种内容进行组织与开发。教师按照课程设计的总体思路，对某一个年级或几个年级设置的各门学科课程的内容，严格按照排定的课题顺序一个接一个地进行下去的课程设计方式是()。

关于教学过程的基本阶段，以下排列顺序正确的是()。

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

用有向无环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目为()。

下列选项中，属于流动资产特点的有()。

企业的现金清查小组应当在出纳人员不在场的情况下对企业库存现金进行定期或不定期清查。()

园林工人用一辆汽车将20棵行道树运往1公里的地方开始种植。在1公里处种第一棵，以后往更远处每隔50米种一棵，该辆汽车每次最多能运三棵树。当园林工人完成任务时，这辆汽车行程最短是()米。

毛泽东在《论十大关系》中提出的观点有()。

在一个空的表单中添加一个选项按钮组控件，该控件可能的默认名称是

Inafixedexchangeratesystem,speculativesellingofacurrencyisbasedonanticipationof

KimiyukiSudashouldbeaperfectcustomerforJapan’scarmakers.He’sayoung(34),successfulexecutiveatanInternet-service

Howdidthemantravelabroad?