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

admin2023-02-06 76

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

学硕统考专业

“没有查出病就是健康”实质上忽视了人的心理健康。()

下列强调在学习过程中要把学与思辩证地结合起来的是()。

心理辅导的目标有两个：一是()，二是寻求发展。

“两个一百年目标”就是到新中国成立一百年时全面建成小康社会，到中国共产党成立一百年时建成富强民主文明和谐的社会主义现代化国家的目标。()

强调迁移的条件是两种学习必须遵循共同的内在原理，这是()。

有的学习者学习时需要绝对安静，有的则喜欢放着背景音乐学习，这属于学习风格偏好中的()。

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

下列关于教育目的的价值取向确立应注意的问题，说法正确的有()。

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

设备上的电气线路和器件发生故障，不必交电工，自己可拆卸修理。（）

过磷酸钙与堆肥一起施用能发挥更大肥效。

逻辑框架分析的首要任务是()。

适用于各级公路粒料类基层和底基层的是()。

低年级学生擅自离开座位时，教师忽略了他们，转而表扬那些保持不动的学生，离座率会下降。这是因为离座的学生受到了()。

坚持以人为本，就是要以实现人的全面发展为目标，从人民群众的根本利益出发谋发展、促发展，不断满足人民群众日益增长的物质文化生活需要。()

他()地向职代会提出，行政干部一定要倾听群众的呼声。

Doctorsalreadyknowthatpeoplewhosmokecandamagetheirhearing.ThelateststudyinthejournalTobaccoControl,【C1】______m

通过WindowsXP中的ping命令可以判定数据到达目的主机经过的路径，显示路径上各个路由器的值。

Forthispart,youareallowed30minutestowriteashortessayentitledShouldPrimarySchoolsOfferaForeignLanguageCourse