已知顺序表A，在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下，设计算法，将所有奇数号元素移到所有偶数号元素前。给出算法的基本设计思想。

admin2016-03-29 45

问题已知顺序表A，在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下，设计算法，将所有奇数号元素移到所有偶数号元素前。
给出算法的基本设计思想。

选项

答案基本的设计思想：先将偶数号元素复制到一个辅助空间，然后整理数组剩下的奇数号元素，最后将辅助空间中的元素复制到数组的后半部分，但这种思路的空间复杂度为O(n)。另一种思路： ①在数组尾部从后往前找到第一个奇数号元素，将此元素与其前面的偶数号元素交换。这样，就形成了两个前后相连且相对顺序不变的奇数号元素“块”。 ②暂存①中“块”前面的偶数号元素，将“块”内奇数号结点依次前移，然后将暂存的偶数号结点复制到空出来的数组单元中。就形成了三个连续的奇数号元素“块”。 ③暂存②中“块”前面的偶数号元素，将“块”内奇数号结点依次前移，然后将暂存的偶数号结点复制到空出来的数组单元中。就形成了四个连续的奇数号元素“块”。 ④如此继续，直到前一步的“块”前没有元素为止。

解析

转载请注明原文地址:https://kaotiyun.com/show/d2Ri777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

已知顺序表A，在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下，设计算法，将所有奇数号元素移到所有偶数号元素前。给出算法的基本设计思想。

计算机408

学硕统考专业

下面对官渡之战的表述正确的是()。

下列关于清朝设置台湾府的叙述，不正确的是()。

广西壮族自治区的设立时间是()。

概述20世纪初欧洲在世界优势地位的主要表现，并分析第一次世界大战对这种优势地位的影响。

简述公元前8世纪至公元前6世纪希腊海外殖民的背景、范围及影响。

我国最早的人工大运河邗沟是由()修建的。

19世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。

某计算机的Cache共有16块，采用2路组相联映射方式(即每组2块)。每个主存块大小为32字节，按字节编址。主存129号单元所在主存块应装入到的Cache组号是()。

42．设有带头结点的循环双链表表示的线性表L=(a1，a2，……，an-1，an)。设计在时间和空间上都尽可能高效的算法，将L改造成L=(a1，a2，……，an，……a4，a2)。要求：(1)给出算法的基本设计思想。(2)根据设计思想，

“乘法减少”和“加法增大”各用在什么情况下?

法律文书在形式上十分明显的特点是

高压电缆最内层的结构是

在房地产开发投资中，属于财务费用的是()。

图示电路在t＝0时开关闭合，t≥0时uC(t)为：

水箱的有效容积包括()。

ReadthemagazinearticlebelowaboutAndySeymour,theChiefExecutiveofachainofbookstorescalledBookroom,andthequest

Intheirworldofdarkness,itwouldseemlikelythatsomeoftheanimalsmighthavebecomeblind,ashashappenedtosomecave

Formanyofus,petshavecometooccupycriticalrolesinourlives.Thelonelinessandisolationinsomelifestylescanbesof

(1)Theseniorpartner,OliverLambert,studiedtheresumeforthehundredthtimeandagainfoundnothinghedislikedaboutMitch

______atinthisway,thepresenteconomicsituationdoesn’tseemsogloomy.

已知顺序表A，在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下，设计算法，将所有奇数号元素移到所有偶数号元素前。 给出算法的基本设计思想。

计算机408

学硕统考专业

下面对官渡之战的表述正确的是()。

下列关于清朝设置台湾府的叙述，不正确的是()。

广西壮族自治区的设立时间是()。

概述20世纪初欧洲在世界优势地位的主要表现，并分析第一次世界大战对这种优势地位的影响。

简述公元前8世纪至公元前6世纪希腊海外殖民的背景、范围及影响。

我国最早的人工大运河邗沟是由()修建的。

19世纪中期，德意志资产阶级迫切要求实现国家的统一，其首要的目的是()。

某计算机的Cache共有16块，采用2路组相联映射方式(即每组2块)。每个主存块大小为32字节，按字节编址。主存129号单元所在主存块应装入到的Cache组号是()。

42．设有带头结点的循环双链表表示的线性表L=(a1，a2，……，an-1，an)。设计在时间和空间上都尽可能高效的算法，将L改造成L=(a1，a2，……，an，……a4，a2)。要求：(1)给出算法的基本设计思想。(2)根据设计思想，

“乘法减少”和“加法增大”各用在什么情况下?

法律文书在形式上十分明显的特点是

高压电缆最内层的结构是

在房地产开发投资中，属于财务费用的是()。

图示电路在t＝0时开关闭合，t≥0时uC(t)为：

水箱的有效容积包括()。

ReadthemagazinearticlebelowaboutAndySeymour,theChiefExecutiveofachainofbookstorescalledBookroom,andthequest

Intheirworldofdarkness,itwouldseemlikelythatsomeoftheanimalsmighthavebecomeblind,ashashappenedtosomecave

Formanyofus,petshavecometooccupycriticalrolesinourlives.Thelonelinessandisolationinsomelifestylescanbesof

(1)Theseniorpartner,OliverLambert,studiedtheresumeforthehundredthtimeandagainfoundnothinghedislikedaboutMitch

______atinthisway,thepresenteconomicsituationdoesn’tseemsogloomy.

已知顺序表A，在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下，设计算法，将所有奇数号元素移到所有偶数号元素前。给出算法的基本设计思想。