首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
现要对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
28
问题
现要对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。
阅读以下说明,回答问题,将解答填入对应的解答栏内。[说明]某旅馆的电话服务如下:可以拨分机号和外线号码。分机号是从7201至7299。外线号码先拨9,然后是市话号码或长话号码。长话号码是以区号和市话号码组成。区号是从100到300中任意的数字串。市话
阅读以下说明,回答问题1~4,将解答填入对应的解答栏内。[说明]现有如下关系模式:R(A#,B#,C,DE),其中,A#,B#为组合键,R上存在的函数依赖有(A#,B#)→E,B#→C,C→D
请使用[说明]中给出的词汇,将该房屋租赁服务系统顶层数据流图(见图5-10)中(1)~(4)空缺处的数据流补充完整。请将以下与租赁者信息相关的数据字典条目补充完整。登录信息=租赁者ID+密码注册信息=(9)租赁者信息=(10
请将以上[Java代码1]与[Java代码2]程序段中,(1)~(7)空缺处的语句填写完整。请用150字以内的文字简要说明[Java代码1]、[Java代码2]这两种对传输门进行状态模拟的设计思路的区别之处。
阅读以下说明和C函数,将(1)~(5)空缺处的字句填写完整。[说明]计算机在处理算术表达式时,首先将其转换为后缀表达式。例如,表达式“46+5*120-37)”的后缀表达式形式为“46512037-*+”。计算后缀表达式时,
根据【说明】,将图6—1中的E1一E3填充完整。 图6—1中缺少三条数据流,根据【说明】,分别指出这三条数据流的起点和终点。(注:数据流的起点和终点均采用图中的符号和描述)
不考虑数据确认处理(加工2),请指出图3-17~图3-19数据流图中可能存在的错误。请使用[说明]中数据字典条目定义形式,将以下(1)和(2)空缺处的内容填写完整。初录数据=(1)复录数据=(2)
阅读下列说明C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系,对某些作业,在A上处理时间长,而对某些作业在B上处理时间长。一
随机试题
威尔达夫斯基指出,早在马克斯·韦伯为我们提供了关于官僚的经典定义时,他已经着重强调了两大特点,即
下列哪种案件应中止诉讼()
关于具体行政行为的成立和效力,下列哪些选项是错误的?(卷二真题试卷第80)
建设工程监理工作文件一般由( )构成。
《商业银行个人理财业务管理暂行办法》规定,商业银行开展个人理财业务有下列情形,并造成客户经济损失的,应按照有关法律规定或者合同的约定承担责任,但不包括()。
假定不考虑补价的情况下,在具有商业实质且换入或换出资产的公允价值能够可靠计量的非货币性资产交换中,确定换入资产入账价值时应考虑的因素有()。
SendingE—mailstoProfessorsOnestudentskippedclassandthensenttheprofessorane-mail______(1)forcopiesofherteaching
根据制度经济学理论,()是分析经济制度的基本范畴。
WiFi依赖看不见的无线电波传输,设备功率越来越大,局部电磁辐射势必增强;无线信号穿墙而过,网络信息不安全。这些安全隐患,在LiFi中“一扫而光”。光谱比无线电频谱大10000倍,意味着更大的带宽和更高的速度,网络设置又几乎不需要任何新的基础设施。LiFi
Wheredidtheconversationtakeplace?
最新回复
(
0
)