全部科目 > 软件设计师 >
2021年上半年 上午试卷 综合知识
第 40 题
知识点 数组  
关键词 时间复杂度   数组   算法   子段  
章/节 计算机软件知识  
 
 
最大尺寸和问题描述为，在n个整数(包含负数)的数组A中，求之和最大的非空连续子数组,如数组A=(-2,11,-4,13,-5,-2) ，其中子数组B=(11,-4,13)具有最大子段和20(11-4+13=20) 。求解该问题时,可以将数组分为两个n/2个整数的子数组最大子段或或者在前半段,或者在后半段,或者跨越中间元素,通过该方法继续划分问题,直至最后求出最大子段和,该算法的时间复杂度为( )。
 
  A.  O(nlgn)
 
  B.  O(n2)
 
  C.  O(n2lgn)
 
  D.  O(n3)




 
 
相关试题     计算机软件知识 

  第47题    2021年下半年  
在Python语言中，（）是一种可变的、有序的序列结构，其中元素可以重复。

  第49题    2019年下半年  
计算机执行程序时，内存分为静态数据区、代码区、栈区和堆区。其中（48)一般在进行函数调用和返回时由系统进行控制和管理，(49)由用户在程序中根据需要申请和释放..

  第58题    2018年上半年  
对下面的二叉树进行顺序存储(用数组MEM表示)，已知结点A、B、C在MEM中对应元素的下标分别为1、2、3，那么结点D、E、F对应的数组元素下标为(  )。

 
知识点讲解
· 数组
 
        数组
               数组的定义及基本运算
               n维数组是一种"同构"的数据结构，其每个元素类型相同、结构一致。数组是定长线性表在维数上的扩张，即线性表中的元素又是一个线性表。
               数组结构的特点是：数据元素数目固定；数据元素具有相同的类型；数据元素的下标关系具有上下界的约束且下标有序。
               对数组进行的基本运算有以下两种。
               （1）给定一组下标，存取相应的数据元素。
               （2）给定一组下标，修改相应的数据元素中某个数据项的值。
               数组的顺序存储
               一旦定义了数组，结构中的数据元素个数和元素之间的关系就不再发生变动，因此数组适合于采用顺序存储结构。
               由于计算机的内存结构是一维线性的，因此存储多维数组时必须按照某种方式进行降维处理，即将数组元素排成一个线性序列，这就产生了次序约定问题。对二维数组有两种存储方式：一种是以列为主序的存储方式；另一种是以行为主序的存储方式。
               设每个数据元素占用L个单元，m、n为数组的行数和列数，那么以行为主序优先存储的地址计算公式为
               Loc(aij)=Loc(a11)+((i-1)n+(j-1))L
               同样的，以列为主序优先存储的地址计算公式为
               Loc(aij)=Loc(a11)+((j-1)m+(i-1))L



更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5
京公网安备 11010502032051号 | 营业执照
 Copyright ©2000-2025 All Rights Reserved
软考在线版权所有