首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
现要对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
30
问题
现要对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)处的字句写在对应栏内。【说明】某绘图系统存在point、line、square三种图元,它们具有Shape接口,图元的类图关系如图13-12所示。现要将circle图元加入此绘图系统以实现功能扩充。已知
阅读下列算法说明和流程图,根据要求回答问题1~问题3。[说明]某机器上需要处理n个作业job1,job2,…,jobn,其中:(1)每个作业jobi(1≤i≤n)的编号为i,jobi有一个收益值P[i]和最后期限值d[i];
阅读以下某房屋租赁服务系统的技术说明和数据流图,根据要求回答问题1~问题4。[说明]某房屋租赁公司欲建立一个房屋租赁服务系统,统一管理房主和租赁者的信息,从而快速地提供租赁服务。该系统具有以下功能。(1)登记房主信息:对于每名房主,
阅读下列说明和图,回答问题1到问题3。[说明]目前大多数操作系统都采用虚拟存储技术,这样可在较小的可用内存中执行较大的用户程序,可在内存中容纳更多程序并发执行。引入虚拟存储技术,其基本思想是利用大容量的外存来扩充内存,产生一个
阅读下列说明和C程序,将应填入(n)处的字句写在对应栏中。[说明]借助一个栈结构,可实现二叉树的非递归遍历算法。InOrderTraverse数实现中序非递归遍历,遍历过程如下:若不是空树,根节点入栈,进入左子树;若已
阅读下列说明和E-R图,回答问题1至问题3,将解答填入对应栏内。[说明]设有下列关于学生成绩管理系统的E-R图(见图2-1)。图中矩形表示实体,圆表示属性,双圆表示关键字属性,菱形表示实体间的联系。假定已通过下列SQL语言建立了基本表:
对文法G进行改写,然后对每个非终结符写出不带回溯的递归子程序。经改写后的文法是否是LL(1)的?指出它的预测分析表中(1)~(3)处的内容。
阅读下列说明C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】用两台处理机A和B处理n个作业。设A和B处理第i个作业的时间分别为ai和bi。由于各个作业的特点和机器性能的关系,对某些作业,在A上处理时间长,而对某些作业在B上处理时间长。一
阅读下列说明和Java代码,将应填入(n)处的字句写在答题纸的对应栏内。【说明】某公司的组织结构图如图17—9所示,现采用组合(Composition)设计模式来设计,得到如图17—10所示的类图。其中Company为抽象类,定义了在组织结构图上添
随机试题
Nearly54millioncarsandtrucksintheUnitedStatesareequippedwithdriversideairbagslocatedinthecenterofthesteer
患者,男性,28岁。施工时不慎从4米高处跌下,半小时后被送入急诊室。体检:血压4/2kPa(30/15mmHg),神清、气促、面色苍白、四肢发凉、脉细弱,左侧胸压痛明显,胸廓塌陷、有骨擦感及反常呼吸征,左胸有一2cm×2.5cm创口,可听到气体出入创口响声
对切除胰腺或重度糖尿病患者无效的降糖药为
按照《注册建造师管理规定》,下列情形中不予注册的情形是()。
甲公司和乙公司均为增值税一般纳税人,购买及销售商品适用的增值税税率均为17%。甲公司于2013年9月30日向乙公司销售一批产品,应收乙公司的货款为2340万元(含增值税)。乙公司同日开出一张期限为6个月,票面年利率为8%的商业承兑汇票。在票据到期日,乙公司
按贷款风险程度划分,我国银行贷款资产包括以下五类()。
信用形式中属于直接信用的有()。
某教师在课外诗歌导读课上准备给学生推荐几首优美的山水诗,帮助学生增加阅读量,陶冶情操,以下诗作不合适的是()。
1,4,11,27,61,133,()
以五声听狱讼,求民情,一日辞听,二日色听,三日气听,四日耳听,五日目听。郑玄疏:“观其出言,不直则烦;观其颜色,不直则赧然;观其气息,不直则喘;观其听聆,不直则惑;观其眸子,不直则眊然。——《周礼.秋官.小司寇》请运用中国法制史的知识和理论,分析
最新回复
(
0
)