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

admin2023-02-06 55

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

学硕统考专业

学生在教师指导下运用知识反复完成一定的操作或解决某类作业与习题，以加深理解，形成技能、技巧。这种教学方法是()。

教师职业道德评价是教师个人按照教师道德的要求所进行的自我锻炼、自我教育的过程。()

问题解决的第一步是()。

在上课之前，老师告诉学生提前学习，目的是减少学生的休息时间。()

当前教师队伍中存在着“以教谋私”“有偿家教”等现象，这主要违背了()。

从所给四个选项中，选出能与给定的①、②、③、④零件共同构成如下图所示的9×2方块组合的一项：

如图所示，为测量珠穆朗玛峰上某点C的海拔高度，测量队选择了两个海拔高度相差100米的珠峰测量点A和B，测得∠ABC为90°，从A观测B、C的仰角分别为30°和45°，从B观测C的仰角也为30°，则C点的海拔高度比A点高：

下列变化过程中包含化学反应的有：①鬼火②光合作用③水垢形成④高粱酿酒⑤舞台云雾的生成

试找出分别满足下面条件的所有二叉树：(1)前序序列和中序序列相同。(2)中序序列和后序序列相同。(3)前序序列和后序序列相同。(4)前序、中序、后序序列均相同。

在古希腊教育史上，首次将算术、几何、天文、音乐四门课程(即“四艺”)列入教学科目的教育家是()。

最高人民法院复核死刑案件，高级人民法院复核死刑缓期执行的案件，应当由()组成合议庭进行。

A．二氢吡啶类钙通道阻滞剂B．β受体阻滞剂C．α受体阻滞剂D．血管紧张素转换酶抑制剂E．中枢交感神经抑制剂合并糖尿病、尿蛋白阳性的高血压患者降压宜首选

被吊销执业证书的，几年内不得申请护士执业注册

调整产业结构、转变增长方式的中心环节是()。

为满足投机性需要而置存过多的现金，使用这种方式较多的是()。

正是由于中国等亚洲国家对日本当时(麦克阿瑟统治期)比现在问题更严重的历史教科书___，错失了_影响的最佳时机，新一代日本人长成了，问题才更_____了。填入画横线部分最恰当的一项是()。

进程对主存的访问具有局部性特征，即时间局部性和【】局部性。

计算机408

学硕统考专业

学生在教师指导下运用知识反复完成一定的操作或解决某类作业与习题，以加深理解，形成技能、技巧。这种教学方法是()。

教师职业道德评价是教师个人按照教师道德的要求所进行的自我锻炼、自我教育的过程。()

问题解决的第一步是()。

在上课之前，老师告诉学生提前学习，目的是减少学生的休息时间。()

当前教师队伍中存在着“以教谋私”“有偿家教”等现象，这主要违背了()。

从所给四个选项中，选出能与给定的①、②、③、④零件共同构成如下图所示的9×2方块组合的一项：

如图所示，为测量珠穆朗玛峰上某点C的海拔高度，测量队选择了两个海拔高度相差100米的珠峰测量点A和B，测得∠ABC为90°，从A观测B、C的仰角分别为30°和45°，从B观测C的仰角也为30°，则C点的海拔高度比A点高：

下列变化过程中包含化学反应的有：①鬼火②光合作用③水垢形成④高粱酿酒⑤舞台云雾的生成

试找出分别满足下面条件的所有二叉树：(1)前序序列和中序序列相同。(2)中序序列和后序序列相同。(3)前序序列和后序序列相同。(4)前序、中序、后序序列均相同。

在古希腊教育史上，首次将算术、几何、天文、音乐四门课程(即“四艺”)列入教学科目的教育家是()。

最高人民法院复核死刑案件，高级人民法院复核死刑缓期执行的案件，应当由()组成合议庭进行。

A．二氢吡啶类钙通道阻滞剂B．β受体阻滞剂C．α受体阻滞剂D．血管紧张素转换酶抑制剂E．中枢交感神经抑制剂合并糖尿病、尿蛋白阳性的高血压患者降压宜首选

被吊销执业证书的，几年内不得申请护士执业注册

调整产业结构、转变增长方式的中心环节是()。

为满足投机性需要而置存过多的现金，使用这种方式较多的是()。

正是由于中国等亚洲国家对日本当时(麦克阿瑟统治期)比现在问题更严重的历史教科书_______，错失了_______影响的最佳时机，新一代日本人长成了，问题才更_______了。填入画横线部分最恰当的一项是()。

进程对主存的访问具有局部性特征，即时间局部性和【】局部性。

正是由于中国等亚洲国家对日本当时(麦克阿瑟统治期)比现在问题更严重的历史教科书___，错失了_影响的最佳时机，新一代日本人长成了，问题才更_____了。填入画横线部分最恰当的一项是()。