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

admin2023-02-06 69

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

学硕统考专业

板书要求整齐、规范、美观，因此板书的文字、图表等格式要统一，不得有变化。()

以下选项除了()都是教师仪容仪态需要遵守的要求。

在实际教学过程中，张老师采用画小红花、插小红旗等方式鼓励学生的德育方法是()。

以下选项中体现“学生学习方式转变”的新课程观点是()。

有老师说：“我们分快慢班的目的是满足不同孩子的教育需求，这是遵循教育规律，尊重儿童认知发展差异的举措。”　要求：对上述观点做出判断和分析。要求条理清晰，观点明确，350字左右。

根据利润表，可以进行()

静脉营养中加入精氨酸的作用包括()。

为健全测绘应急保障工作机制，有效整合利用测绘资源，提高应急测绘保障能力，为应对突发事件提供高效有序的测绘保障，国家制定了《测绘应急保障预案》，其依据是()。

下列因素的变动会使得债券价值呈同向变动的是()。

员工工作绩效是()的函数。

企业债权投资获得的利息收入属于让渡资产使用权收入，()(2017年)

关于火车票签证规定，()不办理改签。

下列选项中不属于常模参照测验的是()。

下列命令中，属于Java编译命令的是()。

计算机408

学硕统考专业

板书要求整齐、规范、美观，因此板书的文字、图表等格式要统一，不得有变化。()

以下选项除了()都是教师仪容仪态需要遵守的要求。

在实际教学过程中，张老师采用画小红花、插小红旗等方式鼓励学生的德育方法是()。

以下选项中体现“学生学习方式转变”的新课程观点是()。

有老师说：“我们分快慢班的目的是满足不同孩子的教育需求，这是遵循教育规律，尊重儿童认知发展差异的举措。” 要求：对上述观点做出判断和分析。要求条理清晰，观点明确，350字左右。

根据利润表，可以进行()

静脉营养中加入精氨酸的作用包括()。

为健全测绘应急保障工作机制，有效整合利用测绘资源，提高应急测绘保障能力，为应对突发事件提供高效有序的测绘保障，国家制定了《测绘应急保障预案》，其依据是()。

下列因素的变动会使得债券价值呈同向变动的是()。

员工工作绩效是()的函数。

企业债权投资获得的利息收入属于让渡资产使用权收入，()(2017年)

关于火车票签证规定，()不办理改签。

下列选项中不属于常模参照测验的是()。

下列命令中，属于Java编译命令的是()。

有老师说：“我们分快慢班的目的是满足不同孩子的教育需求，这是遵循教育规律，尊重儿童认知发展差异的举措。”　要求：对上述观点做出判断和分析。要求条理清晰，观点明确，350字左右。