首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知顺序表A,在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下,设计算法,将所有奇数号元素移到所有偶数号元素前。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。 (3)说明你所设计算法的时
已知顺序表A,在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下,设计算法,将所有奇数号元素移到所有偶数号元素前。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。 (3)说明你所设计算法的时
admin
2023-02-06
40
问题
已知顺序表A,在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下,设计算法,将所有奇数号元素移到所有偶数号元素前。
(1)给出算法的基本设计思想。
(2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。
选项
答案
(1)基本的设计思想:先将偶数号元素复制到一个辅助空间,然后整理数组剩下的奇数号元素,最后将辅助空间中的元素复制到数组的后半部分,但这种思路的空间复杂度为O(n)。另一种思路: ①在数组尾部从后往前找到第一个奇数号元素,将此元素与其前面的偶数号元素交换。这样,就形成了两个前后相连且相对顺序不变的奇数号元素“块”。 ②暂存①中“块”前面的偶数号元素,将“块”内奇数号结点依次前移,然后将暂存的偶数号结点复制到空出来的数组单元中。就形成了三个连续的奇数号元素“块”。 ③暂存②中“块”前面的偶数号元素,将“块”内奇数号结点依次前移,然后将暂存的偶数号结点复制到空出来的数组单元中。就形成了四个连续的奇数号元素“块”。④如此继续,直到前一步的“块”前没有元素为止。 (2)算法的设计如下: [*] (3)一共进行了n/2次交换,每次交换的元素个数从1-n/2,因此时间复杂度为O(n
2
)。虽然时间复杂度为O(n
2
),但因n
2
前的系数很小,实际达到的效率是很高的。算法的空间复杂度为O(1)。
解析
转载请注明原文地址:https://kaotiyun.com/show/QEwD777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
反馈在操作技能的学习过程中的作用十分关键,其中()的作用尤为明显。
学生在教师指导下运用知识反复完成一定的操作或解决某类作业与习题,以加深理解,形成技能、技巧。这种教学方法是()。
学生发展核心素养主要指学生应具备的,能够适应终身发展和社会发展需要的品质和关键能力。中国学生发展核心素养总框架不包括()。
根据教师法的有关规定,下列不属于学校可以解聘教师的情形的是()。
在成就测验的类型中,()是在教学过程中实施的,虽然也要让学生做题,对他们的作业评分,但其目的不是为学生划分等级,而是为了获取学生学习进步情况的有关信息,以便据此改进教学并促进学生学习。
布鲁纳认为,学习知识的最佳方式是发现学习。()
根据以下资料,回答问题。下列关于2018年评价指标指数大小排序正确的是:
从所给的四个选项中,选择最合适的一个填入问号处,使下图中的立体图形①、②、③和④可组成一个完整的长方体。
研究人员介绍,来源于化脓链球菌的Cas9核酸酶现已广泛应用于水稻基因组编辑,有效促进了水稻功能基因组学研究和分子育种进程。Cas9在进行基因组编辑的过程中需要识别、结合一段位于编辑位点靶DNA序列末端的保守NGG序列(该保守序列被称为PAM识别序列,N为碱
时间精确标准的建立从古代起就很自然选择了天(日)为时间间隔标准。最初以太阳升到最高点(日影最短)为中午,连续两次中午之间的时间间隔为1日,叫太阳日。后发现太阳日的长度在变化,就用某恒星连续两次经过子午圈的时间作为1日,称为恒星日。它比太阳日均匀多了,再按一
随机试题
____________thething,Johnwouldhavetoldyouaboutit.
全营养混合液不包括()
对吡喹酮叙述不正确的是
收涩药的功效不包括
恶心呕吐,呃逆嗳气等症频作,其病机是
法的第二层次的本质表明()。
《房屋登记办法》规定,具有独立利用价值的特定空间以及码头、油库等其他建筑物、构筑物,可参照房屋登记的规定和程序,由房屋登记机构依法登记。()
下列关于施工总承包模式的说法中,正确的是()。
逆查法是沿着“试算-过账-制证-结账”的逆账务处理程序,从尾到头进行的普遍检查。()
Whendiditbegintorain?
最新回复
(
0
)