免费智能真题库
>
历年试卷
>
软件设计师
>
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(n
2
)
C. O(n
2
lgn)
D. O(n
3
)
本题目为专供试卷题目。
【如需要，请开通】
您暂时无法使用本功能。
【如需要，请开通】
为保障您的权益，请登录
相关试题：数组
更多>
第58题
2015年下半年
41%
设某n阶三对角矩阵A
n×n
的示意图如下图所示。若将该三对角矩阵的非零元素按行存储在一维数组B[k]（1≤k≤3*..
第63题
2011年下半年
36%
在有n个无序无重复元素值的数组中查找第i小的数的算法描述如下：任意取一个元素r,用划分操作确定其在数组中的位置，假设元素r为第..
第64题
2017年下半年
49%
现需要对一个基本有序的数组进行排序。此时最适宜采用的算法为（64）排算法，时间复杂度为（65）。
知识点讲解
·
数组
数组
数组的定义及基本运算
n
维数组是一种"同构"的数据结构，其每个元素类型相同、结构一致。数组是定长线性表在维数上的扩张，即线性表中的元素又是一个线性表。
数组结构的特点是：数据元素数目固定；数据元素具有相同的类型；数据元素的下标关系具有上下界的约束且下标有序。
对数组进行的基本运算有以下两种。
（1）给定一组下标，存取相应的数据元素。
（2）给定一组下标，修改相应的数据元素中某个数据项的值。
数组的顺序存储
一旦定义了数组，结构中的数据元素个数和元素之间的关系就不再发生变动，因此数组适合于采用顺序存储结构。
由于计算机的内存结构是一维线性的，因此存储多维数组时必须按照某种方式进行降维处理，即将数组元素排成一个线性序列，这就产生了次序约定问题。对二维数组有两种存储方式：一种是以列为主序的存储方式；另一种是以行为主序的存储方式。
设每个数据元素占用
L
个单元，
m
、
n
为数组的行数和列数，那么以行为主序优先存储的地址计算公式为
Loc(
a
ij
)=Loc(
a
11
)+((
i
-1)
n
+(
j
-1))
L
同样的，以列为主序优先存储的地址计算公式为
Loc(
a
ij
)=Loc(
a
11
)+((
j
-1)
m
+(
i
-1))
L
题号导航
2021年上半年 软件设计师 上午试卷 综合知识
本试卷我的完整做题情况
1
/
2
/
3
/
4
/
5
/
6
/
7
/
8
/
9
/
10
/
11
/
12
/
13
/
14
/
15
/
16
/
17
/
18
/
19
/
20
/
21
/
22
/
23
/
24
/
25
/
26
/
27
/
28
/
29
/
30
/
31
/
32
/
33
/
34
/
35
/
36
/
37
/
38
/
39
/
40
/
41
/
42
/
43
/
44
/
45
/
46
/
47
/
48
/
49
/
50
/
51
/
52
/
53
/
54
/
55
/
56
/
57
/
58
/
59
/
60
/
61
/
62
/
63
/
64
/
65
/
66
/
67
/
68
/
69
/
70
/
71
/
72
/
73
/
74
/
75
/
第40题 在手机中做本题
