首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
现要对n个实数(仅包含正实数和负实数)组成的数组A进行重新排列,使得其中所有的负实数都位于正实数之前。求解该问题的算法的伪代码如下,则该算法的时间和空间复杂度为_____________。 i=0;j=n-1 while i<j do while A[
现要对n个实数(仅包含正实数和负实数)组成的数组A进行重新排列,使得其中所有的负实数都位于正实数之前。求解该问题的算法的伪代码如下,则该算法的时间和空间复杂度为_____________。 i=0;j=n-1 while i<j do while A[
admin
2021-01-13
24
问题
现要对n个实数(仅包含正实数和负实数)组成的数组A进行重新排列,使得其中所有的负实数都位于正实数之前。求解该问题的算法的伪代码如下,则该算法的时间和空间复杂度为_____________。
i=0;j=n-1
while i<j do
while A
<0 d。
i=i+1:
while A[j]>0 do
j=j-1;
if i<j do
交换A
和A[j]
选项
A、
B、
C、
D、
答案
C
解析
算法中用到了两个辅助变量i和j,算法的空间复杂度为
(1)。在重新排列过程中,从数组的两端进行比较,从i=0开始判断A
是否为负数,i为负数的时候,i=i+1,直到A
为正数;从j=n-1开始判断A
是否为正数,如果为正数,j=j-1,直到A[j]为负数。当i<j的时候交换A
和A[j]的值。然后继续判断A
和A[j]的值。数组A中的元素个数为n,A
<0和A[j]>0的比较次数共为72+2,i=i+1和j=j-1执行的次数最多为n+2次,if语句中的i<j的比较和交换A
和A[j]的操作分别最多执行n-1次,Wbile循序的条件判断至多执行n次。可见,算法的时间复杂度为
(n)。
转载请注明原文地址:https://kaotiyun.com/show/xXCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明,回答问题。【说明】现有事务T1,T2、L3它们对数值型数据A执行的操作分别如下:T1;将A加1。T2:将A加倍。T3:输出A的值,并将A置为1。
阅读下列说明,根据要求回答问题1~问题3。[说明]某地区举行篮球比赛,需要开发一个比赛信息管理系统来记录比赛的相关信息。[需求分析结果]1.登记参赛球队的信息。记录球队的名称、代表地区、成立时间等信息。系统记录球队的每个队员
阅读下列函数说明和Java代码,将应填入(n)处的字句写在对应栏内。【说明】通常情况下,用户可以对应用系统进行配置,并将配置信息保存在配置文件中,应用系统在启动时首先将配置文件加载到内存中,这些内存配置信息应该有且仅有一份。下面的
请根据标准书号校验码的技术说明,将图5-13和图5-14程序流程图中(1)~(4)空缺处的内容填补完整。假设《应试捷径——典型考题解析与考点贯通_系统分析师考试》书籍标准书号前9个数字为7-121-04715,请写出其对应的校验码。
阅读以下标准书号校验码的技术说明和程序流程图,根据要求回答问题1至问题3。[说明]为实现图书的国际统一编码,便于实现计算机化的图书管理,每本正式出版的图书都印有国际标准书号。标准书号由“ISBN”、10个数字(0~9)组成,其格式如下。
请将以上[Java代码1]与[Java代码2]程序段中,(1)~(7)空缺处的语句填写完整。请用150字以内的文字简要说明[Java代码1]、[Java代码2]这两种对传输门进行状态模拟的设计思路的区别之处。
阅读下列说明和E-R图,回答问题1至问题3,将解答填入对应栏内。[说明]设有下列关于学生成绩管理系统的E-R图(见图2-1)。图中矩形表示实体,圆表示属性,双圆表示关键字属性,菱形表示实体间的联系。假定已通过下列SQL语言建立了基本表:
试解释这个对象联系图。试用ORDB的定义语言,定义这个数据库。
对文法G进行改写,然后对每个非终结符写出不带回溯的递归子程序。经改写后的文法是否是LL(1)的?指出它的预测分析表中(1)~(3)处的内容。
阅读下列说明和Java代码,将应填入(n)处的字句写在答题纸的对应栏内。【说明】某公司的组织结构图如图17—9所示,现采用组合(Composition)设计模式来设计,得到如图17—10所示的类图。其中Company为抽象类,定义了在组织结构图上添
随机试题
A.有利、自主、公正、互助B.有利、自主、公平、帮助C.舆论、习俗、信念D.舆论、方法、信念、习俗E.以上都是医德评价的主要标准
人民法院受理了绿野公司债权人提出的对绿野公司破产清算的申请,下列问题应给予否定回答的有:()
背景某新建办公楼工程,主楼建筑面积29600m2,地上16层,地下1层,基础埋深4m,现浇混凝土框架一剪力墙结构。附楼建筑面积5000m2混合结构,地上3层。地下防水采用防水混凝土附卷材防水,屋面采用卷材防水,室内采用涂料防水。土方开挖采用放坡形式。预制
我国参照过去伦敦协会条款制定的海洋运输条款,仍采用()险别
企业上年年末的资产负债表(简表)如下(单位:万元):根据历史资料可知,经营资产、经营负债项目与营业收入成正比,金融资产为可动用的金融资产,企业上年度营业收入800万元,实现净利100万元,支付股利60万元。要求:如果预计本年度不含通货膨胀的营业收
请认真阅读下列材料,并按要求作答。根据上述材料完成下列任务:什么是数据分析观念?如何培养学生的数据分析观念?(10分)
下列叙述正确的是()。
送蔡元振序曾巩古之州从事①,皆自辟士,士择所从,故宾主相得也。如不得其志,去之可也。今之州从事,皆命于朝,非惟守不得择士,士亦不得择所从,宾主岂尽相得哉!如不得其志,耒可以
以下哪项,如果为真,能支持题干中专家的结论?
TheCounsellingServicemaycontacttutorsif
最新回复
(
0
)