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

admin2023-02-06 53

问题已知顺序表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://jikaoti.com/ti/6vPiFFFM

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

教师劳动所创造的价值，并不是以物化的形式表现出来的，而是作为一种潜在价值因素存在于学生身上。这说明教师劳动具有滞后性的特点。()

有些学生喜欢把作业拖到最后一刻才开始做，考试前的复习也尽可能拖延到最后一天才开始。学生的上述现象属于()。

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

探究学习的实施过程包括()阶段。

学习者为了提高学习的效果和效率，有目的、有意识地制订有关学习过程的复杂方案。这称为()。

量子计算机是一类遵循量子力学规律进行高速数学和逻辑运算、存储及处理量子信息的物理装置，运行的是量子算法，处理速度大大超过传统计算机。量子计算机具有超高运算速度的原理在于()。

乳香、没药的共同功效是

患者，女性，34岁。子宫内膜检查所见：腺体缩小，内膜水肿消失，螺旋小动脉痉挛性收缩，有坏死、内膜下血肿。护士根据检查结果判断该内膜为月经的

某工程双代号时标网络计划执行到第4周末和第10周末时，检查其实际进度如下图前锋线所示，检查结果表明()。

在美国的银行监管体制下，被称为功能监管者的是()。

1990年11月26日，新中国第一家证券交易所()成立。

产品的标准成本由()构成。

设α1，α2，α3均为线性方程组Ax=b的解，下列向量中α1一α2，α1一2α2+α3，(α1一α3)，α1+3α2—4α3，是导出组Ax=0的解向量的个数为()

【S1】【S2】

A、Inabank.B、Inapostoffice.C、Atastop.D、Attheschoolgate.B女士问男士空运这个行李要多少钱。男士称了一下,有3磅。由此可知，男士应该是邮递公司的职员,故选B。