首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
现要对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
65
问题
现要对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
软件设计师上午基础知识考试
软考中级
相关试题推荐
请将图3-25中的(1)~(3)空缺处的内容填写完整。对于本试题的作业处理问题,用图3-25的贪心算法能否求得最高收益?(6)。(能或不能)用贪心算法求解任意给定问题时,是否一定能得到最优解?(7)。(能或不能)
请根据标准书号校验码的技术说明,将图5-13和图5-14程序流程图中(1)~(4)空缺处的内容填补完整。假设《应试捷径——典型考题解析与考点贯通_系统分析师考试》书籍标准书号前9个数字为7-121-04715,请写出其对应的校验码。
阅读下列说明和图,回答问题1到问题3。[说明]目前大多数操作系统都采用虚拟存储技术,这样可在较小的可用内存中执行较大的用户程序,可在内存中容纳更多程序并发执行。引入虚拟存储技术,其基本思想是利用大容量的外存来扩充内存,产生一个
阅读下列说明和C程序,将应填入(n)处的字句写在对应栏中。[说明]借助一个栈结构,可实现二叉树的非递归遍历算法。InOrderTraverse数实现中序非递归遍历,遍历过程如下:若不是空树,根节点入栈,进入左子树;若已
阅读下列说明和E-R图,回答问题1至问题3,将解答填入对应栏内。[说明]设有下列关于学生成绩管理系统的E-R图(见图2-1)。图中矩形表示实体,圆表示属性,双圆表示关键字属性,菱形表示实体间的联系。假定已通过下列SQL语言建立了基本表:
阅读下列说明和C代码,回答以下问题,将解答写在答题纸的对应栏内。【说明】用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系,对某些作业,在A上处理时间长,而对某些作业在B上处理时间
阅读下列说明C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系,对某些作业,在A上处理时间长,而对某些作业在B上处理时间长。一
(2012年上半年下午试题二)阅读下列说明,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某医院拟开发一套住院病人信息管理系统,以方便对住院病人、医生、护士和手术等信息进行管理。【需求分析】(1)系统登记每
(2013年上半年下午试题二)阅读下列说明,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某电视台拟开发一套信息管理系统,以方便对全台的员工、栏目、广告和演播厅等进行管理。【需求分析】(1)系统需要维护全台
随机试题
病毒垂直感染的正确概念是()
A.糖正常,氯化物升高,蛋白明显下降,细胞数升高,以中性粒细胞为主B.糖明显下降,氯化物正常,蛋白明显升高,细胞数升高,以中性粒细胞为主C.糖明显下降,氯化物下降,蛋白明显升高,细胞数升高,以淋巴增高为主D.糖正常,氯化物正常,蛋白升高,细胞数升高,
新民主主义的政治是()
急性血源性骨髓炎,在X线片上出现异常的最早期时间为起病后
小儿感冒易引起惊厥的年龄是
冠桩的长度一般为根长的可保留的牙齿其牙槽骨吸收不能超过根长的
A.阵发性室上性心动过速B.阵发性室性心动过速C.房颤D.早搏E.窦性心动过速
下列各项中,属于其他应收款的有()。
凭证是账务系统最基本最重要的资料来源,其中下列( )属于计算机账务系统处理的凭证来源。
下列函数不属于初中数学课程内容的是()。
最新回复
(
0
)