首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知顺序表A,在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下,设计算法,将所有奇数号元素移到所有偶数号元素前。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。 (3)说明你所设计算法的时
已知顺序表A,在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下,设计算法,将所有奇数号元素移到所有偶数号元素前。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。 (3)说明你所设计算法的时
admin
2023-02-06
88
问题
已知顺序表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
学硕统考专业
相关试题推荐
教师对学生的态度会影响学生人格的形成。如果学生在人格方面表现出没有组织纪律性,缺乏团体目标的特点,从教师影响学生的方面来说,教师态度是()的。
在新课程下,教学的预设与生成的关系是()。
教师在编写教学目标时,要求学生“概括出《孔乙己》的故事情节”。这属于布卢姆认知目标中的()。
认为学生能够完全决定整个教育过程和教育结果,而教师的任务只是刺激学生去学习的学习发展观的代表人物有()。
布鲁纳认为不论教师教什么学科,务必使学生理解该学科的基本结构。依此而建立的课程理论是()。
已有研究指出,口头言语发展的关键期是()。
地球上的地震发生在由板块运动产生的断层上,火星没有板块构造,但它持续的冷却和收缩过程会产生压力,当这种压力积累到足够大,就会引发火星地震。探测到火星地震是科学研究工作的一个里程碑。研究人员说,安放在火星表面的“内部结构地震实验仪”就像“贴着耳朵放了一部电话
根据以下资料,回答问题。截至2019年12月31日,中国共产党党员总数为9191.6万名,同比增长1.46%。在党员的性别、民族和学历上,女党员2559.9万名,少数民族党员680.3万名,大专及以上学历党员4661.5万名。在党员的入党时间上,新中
2015年全年全国生产总值676708亿元,同比增长6.9%,增速比去年同期下降0.5个百分点。表中所列31个地区中,2015年地区生产总值占全国的比重同比上升的个数比下降的个数多:
某部门举行年会抽奖活动。抽奖箱里有80个抽奖券,共20个不同的数字,每个数字均出现4次,且分别对应一份礼品,不同的数字对应的礼品不同。每人当天限抽1次。那么最少多少人当天参加抽奖活动,才能保证至少有3人领取的礼品相同?
随机试题
某街道综合治理委员会共有6名委员:F、G、H、I、M和P。其中每一位委员,在综合治理委员会下属的3个分委会中,至少要担任其中一个分委会的委员。每个分委会由3位不同的委员组成。已知以下条件:①6名委员中有一位分别担任3个分委会的委员。②F
目前对白血病的MICM分型诊断中,C指的是哪一种分类方法
患者,女,30岁。急性腹痛发作10小时入院,下列哪项检查对诊断急性胰腺炎最有价值
银行业从业人员对客户提出的问题应当本着()的原则答复,不得为达成交易而隐瞒风险或进行虚假或误导性陈述。
西斯蒙第的税收原则在亚当.斯密四原则基础上增加了()。
制定利润分配政策时,应该考虑的投资者的因素是( )。
根据政府采购法律制度的规定,下列情形中,采购入可以竞争性谈判方式采购的有()。
根据支付结算法律制度的规定,远期信用汪的付款期限最长不得超过()。
耶基斯一多德森定律表明:动机水平______,最有利于激发______。
下列对贷款的概念的理解,错误的一项是()。
最新回复
(
0
)