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

admin2019-08-15 42

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

论述世界反法西斯联盟形成的意义。

下列描述中，属于冯.诺依曼体系结构的特点是()。①采用流水线技术；②指令和数据均以二进制表示；③存储程序并且存储时不区别数据和指令。

下列选择中，()不是操作系统关心的主要问题。

下列各种情况中，应采用异步通信方式的是()。

试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的：ProcessPO：do{flag[0]=true；While(flag[1])；

ICMP在TCP／IP协议集中属于()。

操作系统采用页式存储管理方法，要求()。

下图所示的CPU逻辑框图中，有两条独立的总线和两个独立的存储器。已知指令存储器IM最大容量为16384字(字长18位)，数据存储器DM最大容量是65536字(字长16位)。各寄存器均有“打入”(Rin)“送出”(Rout/)控制命令，但图中未标出。

以下关于查找方法的说法正确的是()。I顺序查找法只能在顺序存储结构上进行Ⅱ折半查找法可以在有序的双向链表上进行Ⅲ分块查找的效率与线性表被分为多少块有关

中断响应过程中，保护程序计数器PC的作用是()。

A．腹痛突然发生或加重，呈持续性剧痛B．起病缓慢，腹痛由轻至重，呈持续性C．腹痛轻，呈持续性D．起病急，呈持续性阵发性加重E．发病急，呈阵发性腹部绞痛绞窄性急腹症腹痛的特点是

β-CD可以应用于

依据《关于预防煤矿生产安全事故的别规定》，煤矿若存在下列情形，有关执法部门应当提请政府对其予以关闭的有()。

希克斯和尼汉斯认为金融创新的支配因素是()。

失独家庭可领养子女，民政局要统计各区县人数。想要做一个调查。让你组织，你怎么做?

[*]

Bilingualeducationinschoolshaslongbeenapoliticalhotpotato—itwasbannedinCaliforniabya1998ballotmeasure,which

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

计算机408

学硕统考专业

论述世界反法西斯联盟形成的意义。

下列描述中，属于冯.诺依曼体系结构的特点是()。①采用流水线技术；②指令和数据均以二进制表示；③存储程序并且存储时不区别数据和指令。

下列选择中，()不是操作系统关心的主要问题。

下列各种情况中，应采用异步通信方式的是()。

试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的：ProcessPO：do{flag[0]=true；While(flag[1])；

ICMP在TCP／IP协议集中属于()。

操作系统采用页式存储管理方法，要求()。

下图所示的CPU逻辑框图中，有两条独立的总线和两个独立的存储器。已知指令存储器IM最大容量为16384字(字长18位)，数据存储器DM最大容量是65536字(字长16位)。各寄存器均有“打入”(Rin)“送出”(Rout/)控制命令，但图中未标出。

以下关于查找方法的说法正确的是()。I顺序查找法只能在顺序存储结构上进行Ⅱ折半查找法可以在有序的双向链表上进行Ⅲ分块查找的效率与线性表被分为多少块有关

中断响应过程中，保护程序计数器PC的作用是()。

A．腹痛突然发生或加重，呈持续性剧痛B．起病缓慢，腹痛由轻至重，呈持续性C．腹痛轻，呈持续性D．起病急，呈持续性阵发性加重E．发病急，呈阵发性腹部绞痛绞窄性急腹症腹痛的特点是

β-CD可以应用于

依据《关于预防煤矿生产安全事故的别规定》，煤矿若存在下列情形，有关执法部门应当提请政府对其予以关闭的有()。

希克斯和尼汉斯认为金融创新的支配因素是()。

失独家庭可领养子女，民政局要统计各区县人数。想要做一个调查。让你组织，你怎么做?

[*]

Bilingualeducationinschoolshaslongbeenapoliticalhotpotato—itwasbannedinCaliforniabya1998ballotmeasure,which

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