首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知数组A[1……n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想; (2)根据设计思想,采用C或C++
已知数组A[1……n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想; (2)根据设计思想,采用C或C++
admin
2013-07-12
24
问题
已知数组A[1……n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。
(1)给出算法的基本设计思想;
(2)根据设计思想,采用C或C++或JAVA语言表述算法,关键之处给出注释;
(3)说明你所设计算法的时间复杂度和空间复杂度。
选项
答案
(1)算法的基本设计思想如分析所述。 (2)用C语言算法描述如下: void Adjust(int A[]){ //调整数组A,使得A的左边为负整数。右边为正整数 int i=1,j=n,temp; whi1e(i
0&&i
解析
本题主要考查线性表的顺序存储结构(这里为数组)的应用。算法的基本设计思想是先设置好上、下界和轴值,然后分别从数组前端查找正整数和从数组末端查找负整数,找到后进行交换,直到上、下界相遇。
具体做法是:设置两个指示器i和j,其中i=1,j=n;当A
为正整数,A[j]为负整数时,A
和A[j]交换;否则,A
为负整数时,则i++;A[j]为正整数时,则j--。这样,可使算法的时间复杂度为O(n)。
转载请注明原文地址:https://kaotiyun.com/show/crxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
周王室的两大官僚系统是()。
试析淝水之战前后南北政局的特点及其变化。(中国人民大学2005年中国通史真题)
《吕氏春秋》载:“公作则迟,有所匿其力也;分地则速,无所匿其力也。”这条材料反映的实质问题是()。
佛教在从印度向外传播的过程中分为两大流派,其中小乘佛教又称为()。
元代对边疆地区的统治方式不同于其他三地的一地是()。
中国历史上第一部资产阶级革命法典《临时约法》公布的时间是()。
最早测量子午线的长度,并主持修订了当时最先进历法《大衍历》的是僧人()。
光绪元年七月,清政府迫于()强烈要求派一位使臣到其国,()成为中国第一个驻外公使
“二战”后主要资本主义国家经济恢复和发展的杠杆是()。①政府采取宏观调控政策②发展国家垄断资本主义③充分利用科技成果④加强国际经济联系
(1)页面长度为1KB=210B,因此页内偏移地址占10位。主存大小为16KB=214B,所以物理地址占14位。0AC5H=0000101011000101B,除去后10位,得到页号为2,则查找页表可知物理块号为4,所以物理地址是0100101100
随机试题
“文化大革命”结束的标志是
金属桥用栅栏式的铸道其优点A.各个铸道的长度一致,有利于防止收缩变形B.各个铸道的长度一致,有利于铸件的切割C.各个铸道的长度一致,有利于包埋D.各个铸道的长度一致,有利于铸造E.各个铸道的长度一致,有利于操作
A.补气升提B.健脾利湿C.补肾固脱D.温肾纳气E.收涩固脱
建设项目所处的地区不同,决定了其建设费用的项目类别及其费率存在差异。()
《建设工程安全生产管理条例》规定,不属于监理单位安全生产管理责任和义务的是( )。
某甲在一胡同口抢劫一女青年钱包,抢到钱包后,突然发现该女青年是自己的邻居,于是将钱包当面送还给女青年,并声称刚才的行为是开玩笑的。某甲的行为是()。
企业收到投资者以外币投入的资本,无论是否存在合同约定汇率,均不采用合同约定汇率折算,应采用交易日即期汇率折算,外币投入资本与相应的货币性项目的记账本位币金额相等,不产生外币资本折算差额。()
行为目标描述的是()。
材料一:今年2月27日,全国“两会”前夕,国务院总理温家宝时隔一年之后二次与网友进行在线交流。在两个小时的访谈中,温家宝坦诚深入地回答了网友们内心的诸多问题。在谈到最近两次受到广泛关注的“问题奶粉”时,温总理重申“企业家的身上应该流淌着道德的血液。”今年4
(1)新民主主义理论(2)列宁主义(3)剩余价值理论(4)农村包围城市理论(5)科学发展观
最新回复
(
0
)