首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
现要对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
61
问题
现要对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
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列函数说明和Java代码,将应填入(n)处的字句写在对应栏内。【说明】通常情况下,用户可以对应用系统进行配置,并将配置信息保存在配置文件中,应用系统在启动时首先将配置文件加载到内存中,这些内存配置信息应该有且仅有一份。下面的
阅读以下算法说明和C程序,根据要求回答问题1至问题2。[说明][算法4-1]的功能是:用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号没有对应的左括号或者右括号,则给出相应的提示信息,如图4-18所示。在[算法4-1
阅读下列说明和Java代码,将应填入(n)处的字句写在答题纸的对应栏内。【说明】某公司的组织结构图如图6-1所示,现采用组合(Composition)设计模式来设计,得到如图6-2所示的类图。其中Company为抽象类,定义
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】堆数据结构定义如下:对于n个元素的关键字序列{a1,a2,…,an},当且仅当满足下列关系时称其为堆。在一个堆中,若堆顶元素为最大元素,则称为大顶堆;若堆顶元素
对文法G进行改写,然后对每个非终结符写出不带回溯的递归子程序。经改写后的文法是否是LL(1)的?指出它的预测分析表中(1)~(3)处的内容。
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。【说明】用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系,对某些作业,在A上处理时间长,而对某些作业在B上处理时间
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】堆数据结构定义如下:对于n个元素的关键字序列{a1,a2,…,an},当且仅当满足下列关系时称其为堆。在一个堆中,若堆顶元素为最大元素,则称为大顶堆;若堆顶元素为最小元素
(2012年上半年下午试题二)阅读下列说明,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某医院拟开发一套住院病人信息管理系统,以方便对住院病人、医生、护士和手术等信息进行管理。【需求分析】(1)系统登记每
(2013年上半年下午试题二)阅读下列说明,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某电视台拟开发一套信息管理系统,以方便对全台的员工、栏目、广告和演播厅等进行管理。【需求分析】(1)系统需要维护全台
随机试题
下列各项中,不应列入利润表“营业收入”项目的是()。
识记
急性肝炎时,LD同工酶谱中以何种增高为主
不发生相互作用的免疫细胞膜分子是
A.乳果糖B.生长抑素C.柳氮磺胺吡啶D.左旋多巴E.利福平主要用于治疗溃疡性结肠炎的药物是
“蓝牙”技术是()。
大理石具有( )等优点。
教育情境
增强现实技术是一种实时地计算摄影机影像的位置及角度并加上相应图像的技术,这种技术的目标是在屏幕上把虚拟世界套在现实世界并进行互动。根据上述定义。下列属于增强现实技术的是:
印记学习是指发生在动物生活的早期阶段、由直接印象形成的学习行为,印记学习行为虽发生在早期,但对晚期行为也具有一定影响。根据上述定义,下列不属于印记学习行为的是()。
最新回复
(
0
)