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

admin2016-03-29 63

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

下面条约没有涉及德国的赔款问题的是()。

基督教产生的时间是()。

中世纪战争史上有过两次君士坦丁堡陷落，分别简述其发生的时间、征战的双方、导致的历史变动。(华东师范大学2003年世界通史真题)

十六国时期的历史，可以划分为前后两个时期，其分界线是()。

下列哪一个不是罗马王政时代的管理机构?()

假定有一条通带为100kHz的信道，每路信号的带宽为3．2kHz，各路信号间的防护带宽为0．8kHz。若采用频分多路复用，那么最多可以同时传输()路信号。

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

循环队列用数组A[0．．m～1]存放其元素值，已知其头尾指针分别为front和rear，则当前元素个数为()。

A．冠心病B．原发性梗阻性肥厚型心肌病C．扩张型心肌病D．风湿性心脏瓣膜病E．高血压心脏病

IgA肾病的临床表现不包括

诊断糖尿病的主要依据为

A、寒湿阻络B、血脉瘀阻C、湿热毒盛D、热毒伤阴E、气阴两虚脱疽表现为患肢黯红而肿，患肢如煮熟之红枣，渐变为紫黑色，呈浸淫蔓延，溃破腐烂，疼痛异常，彻夜不得安眠。其证候是

关于工程总承包，下列说法正确的有()。

受理申请宣告公民失踪或死亡的机关是：

已知A是3阶矩阵，αi(i=1，2，3)是3维非零列向量，若Aαi=iαi(i=1，2，3)，令α=α1+α2+α3.(I)证明：α，Aα，A2α线性无关；(II)设P=(α，Aα，A2α)，求P-1AP．

Atwork,asinlife,attractivewomengetalotofgoodlucks.Studieshaveshownthattheyaremorelikelytobe【B1】______than

Howcanwegetridofgarbage(垃圾)?Dowehaveenoughenergysourcestomeetourfutureenergyneeds?Thesearetwoimportant

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

计算机408

学硕统考专业

下面条约没有涉及德国的赔款问题的是()。

基督教产生的时间是()。

中世纪战争史上有过两次君士坦丁堡陷落，分别简述其发生的时间、征战的双方、导致的历史变动。(华东师范大学2003年世界通史真题)

十六国时期的历史，可以划分为前后两个时期，其分界线是()。

下列哪一个不是罗马王政时代的管理机构?()

假定有一条通带为100kHz的信道，每路信号的带宽为3．2kHz，各路信号间的防护带宽为0．8kHz。若采用频分多路复用，那么最多可以同时传输()路信号。

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

循环队列用数组A[0．．m～1]存放其元素值，已知其头尾指针分别为front和rear，则当前元素个数为()。

A．冠心病B．原发性梗阻性肥厚型心肌病C．扩张型心肌病D．风湿性心脏瓣膜病E．高血压心脏病

IgA肾病的临床表现不包括

诊断糖尿病的主要依据为

A、寒湿阻络B、血脉瘀阻C、湿热毒盛D、热毒伤阴E、气阴两虚脱疽表现为患肢黯红而肿，患肢如煮熟之红枣，渐变为紫黑色，呈浸淫蔓延，溃破腐烂，疼痛异常，彻夜不得安眠。其证候是

关于工程总承包，下列说法正确的有()。

受理申请宣告公民失踪或死亡的机关是：

已知A是3阶矩阵，αi(i=1，2，3)是3维非零列向量，若Aαi=iαi(i=1，2，3)，令α=α1+α2+α3.(I)证明：α，Aα，A2α线性无关；(II)设P=(α，Aα，A2α)，求P-1AP．

Atwork,asinlife,attractivewomengetalotofgoodlucks.Studieshaveshownthattheyaremorelikelytobe【B1】______than

Howcanwegetridofgarbage(垃圾)?Dowehaveenoughenergysourcestomeetourfutureenergyneeds?Thesearetwoimportant

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