首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知数组A[1……n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想; (2)根据设计思想,采用C或C++
已知数组A[1……n]的元素类型为整型int,设计一个时间和空间上尽可能高效的算法,将其调整为左右两部分,左边所有元素为负整数,右边所有元素为正整数。不要求对这些元素排序。 (1)给出算法的基本设计思想; (2)根据设计思想,采用C或C++
admin
2013-07-12
47
问题
已知数组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
学硕统考专业
相关试题推荐
“二战”后世界经济发展变化迅速,这种变化主要表现在()。①国际金融体系和贸易体系的形成②国家垄断资本主义的空前发展③形成以美、苏“冷战”为特征的两极格局④科学技术推动生产力发展更为迅速
评述欧洲一体化的历史进程。(华东师范大学1998年世界当代史真题)
评价凡尔赛—华盛顿体系。
抗日战争期间,日本将沦陷区的许多矿产业、钢铁业等交给日本公司管理,而名义是()
简述清代秘密立储制的操作并作出评价。
【伊壁鸠鲁】中国人民大学2015年世界通史真题
什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后,得到IP地址都不一样,可能吗?为什么?
某计算机字长16位,采用16位定长指令字结构,部分数据通路结构如下图所示。图中所有控制信号为1时表示有效、为0时表示无效。例如控制信号MDRinE为1表示允许数据从DB打入MDR,MDRin为1表示允许数据从内总线打入MDR。假设MAR的输出一直处于使能状
若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点,则下面最节省运算时间的存储方式是()。
随机试题
甲状腺功能亢进
患者,男,72岁。左侧腹股沟可复性包块14年,不能回纳8小时,以左腹股沟斜疝嵌顿急诊手术,术中见嵌顿小肠肠管色暗,无蠕动,行部分肠切除。此时不能行疝修补术的原因是()
患者女,26岁。因面黄、乏力、皮肤紫癜1年来诊。查体:巩膜轻度黄染。检测WBC4.6×109/L,RBC1.8×1012/L,Hb60g/L,PLT36×109/L;骨髓示有核细胞增生明显活跃,粒系比例、分布正常,红系占0.32,分布大致正常,成熟红细胞畸
临证应用清瘟败毒饮,当根据具体病情及脉象决定使用大、中、小剂,使用小剂的脉象依据是
以下( )不是企业定额的作用。
会计报告的编制要求包括( )等。
“儿童中心主义”教育理论,违背了()。
下列关于担保物权的表述,正确的有()。
Fearsof"madcow"diseasespread【C1】______theglobelastweek【C2】______SouthMrica,NewZealandandSingaporejoiningmostof
A、Itcanbetrainedonlybyspeakingwithnativespeakers.B、Itisaskillandshouldbetrained.C、Itisaskillthatdevelops
最新回复
(
0
)