设数组A[1…m1…n］的每个元素占用1个存储单元，对于数组..

2015年下半年上午试卷综合知识

第 33 题


知识点	数组的特征列存储数组
关键词	存储单元偏移量数组
章/节	常用数据结构

设数组A[1…m,1…n］的每个元素占用1个存储单元，对于数组元素A[ij]（1≤i≤m，1≤j≤n），在按行存储方式下，其相对于数组空间首地址的偏移量为( 33）；在按列存储方式下，其相对于数组空间首地址的偏移量为（34）。

A. i*(n-1）-j

B. (i-1)*n+j－1

C. i*(m-1)+j

D. (i-1)*m+j-1

相关试题常用数据结构

第43题

2016年上半年

对于n个元素的关键码序列{k₁，k₂，…，k_n}，当且仅当满足下列关系时称其为堆。

以下关键码序列中，（）不是..

第43题

2012年上半年

以下关于图的存储结构的叙述中，正确的是（43)

第31题

2023年上半年

可利用一个栈来检查表达式中的括号是否匹配，其方法是:初始时设置栈为空，然后从左到右扫描表达式，遇到左括号“(”就将其入栈，遇到右括号“)&r..

知识点讲解

· 数组的特征

· 列存储

· 数组

数组的特征

数组是一组具有相同类型的变量，其中各个元素共用一个数组名，但是用不同的下标来访问（引用）。如int a[6]；说明了一个一维整型数组a，其中各个整型元素组成了一个向量：a[0], a[1], a[2], a[3], a[4], a[5]。

数组还可以是多维数组，但二维以上的多维数组不是线性结构。

n维数组是一维数组（向量）的推广。二维数组（也叫矩阵）可看作其元素是一维数组的一维数组（线性表、向量），n维数组可看作其元素是n-1维数组的一维数组（线性表、向量）。n维数组的每个元素处于n个向量中，有n个前驱，也有n个后继。

对二维数组来说，给定维数和下标，如何得到数组元素存储位置？设每个数组占用L个内存单元，则二维数组A_mn按行优先顺序（下标从0开始），a_ij的地址为：

LOC（i, j）=LOC（0, 0）+（i*n+j）*L

二维数组A_mn按列优先顺序（下标从0开始），a_ij的地址为：

LOC（i,j）=LOC（0, 0）+（j*m+i）*L

对n维数组而言，一旦规定了数组的维数和各维的上下界限，便可为它分配存储空间；反之，只要给出一组下标便可求得相应数组元素的存储位置。以行序为例，设每个数据元素占L个存储单元，则n维数组任意元素的存储位置为：

其中，

C_n=L,C_i_-1=b_i×c_i, 1<i≤n

在C语言中，二维数组是按行优先存储的，数组float a[4][5]；的存储顺序为a[0][0], a[0][1], …, a[0][4], …, a[3][0], …, a[3][4], a[2][3]的地址为S+（2×5+3）×4=42，其中S为起始地址。

列存储

传统的关系型数据库都是以行为单位来进行数据的存储的，擅长进行以行为单位的数据处理，比如特定条件数据的获取。因此，关系型数据库也被称为面向行的数据库。相反，面向列的数据库是以列作为单位来进行数据的存储的，擅长进行以列为单位的数据处理。下表所示为面向行和面向列的数据库的比较。

面向行和面向列的数据库比较

面向列的数据库具有高扩展性，即使数据增加也不会降低相应的处理速度，所有它主要应用于需要处理大量数据的情况。另外，利用面向列的数据库的优势，把它作为批处理程序的存储器来对大量数据进行更新也是非常有用的。

列存储数据库，主要产品有Google的Bigtable、由Bigtable衍生的Hypertable和HBase、Cassandra这几个数据库。

数组

数组的定义及基本运算

一维数组是长度固定的线性表，数组中的每个数据元素类型相同。n维数组是定长线性表在维数上的扩张，即线性表中的元素又是一个线性表。

设有n维数组A［b₁，b₂，…，b_n］，其每一维的下界都为1，b_i是第i维的上界。从数据结构的逻辑关系角度来看，A中的每个元素A［j₁，j₂，…，j_n］（1≤j_i≤b_i）都被n个关系所约束。在每个关系中，除第一个和最后一个元素外，其余元素都只有一个直接后继和一个直接前驱。因此就单个关系而言，这n个关系仍是线性的。

以下面的二维数组A［m］［n］为例，可以把它看成是一个定长的线性表，它的每个元素也是一个定长线性表。

可将A看作一个行向量形式的线性表：

A_m_*_n=［［a₁₁a₁₂…a₁_n］［a₂₁a₂₂…a_2n］…［a_m₁a_m₂…a_mn］］

也可将A看作列向量形式的线性表：

A_m_*_n=［［a₁₁a₂₁…a_m₁］［a₁₂a₂₂…a_m₂］…［a₁_na₂_n…a_mn］］

数组结构的特点如下：

（1）数据元素数目固定。一旦定义了一个数组结构，就不再有元素的增减变化。

（2）数据元素具有相同的类型。

（3）数据元素的下标关系具有上下界的约束且下标有序。

在数组中通常做下面两种操作：

（1）取值操作。给定一组下标，读其对应的数据元素。

（2）赋值操作。给定一组下标，存储或修改与其相对应的数据元素。

几乎所有的程序设计语言都提供了数组类型。实际上，在语言中把数组看成是具有共同名字的同一类型多个变量的集合。需要注意的是，不能对数组进行整体的运算，只能对单个数组元素进行运算。

数组的顺序存储

由于数组一般不作插入和删除运算，也就是说，一旦定义了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动，因此数组适合于采用顺序存储结构。

对于数组，一旦确定了它的维数和各维的长度，便可为它分配存储空间。反之，只要给出一组下标便可求得相应数组元素的存储位置，也就是说，在数据的顺序存储结构中，数据元素的位置是其下标的线性函数。

二维数组的存储结构可分为以行为主序（按行存储）和以列为主序（按列存储）两种方法，如下图所示。

二维数组的两种存储方式

设每个数据元素占用L个单元，m、n为数组的行数和列数，那么以行为主序优先存储的地址计算公式为：

Loc（a_ij）=Loc（a₁₁）+（（i-1）×n+（j-1））×L

同理，以列为主序优先存储的地址计算公式为：

Loc（a_ij）=Loc（a₁₁）+（（j-l）×m+（i-1））×L

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

京B2-20210865 | 京ICP备2020040059号-5