某大型整数矩阵用二维整数组 G[1：2M ，1：2N]表示，其中M和N是较大的整数，而且每行从..

2017年上半年上午试卷综合知识

第 63 题


知识点	矩阵排序数组
关键词	排序数组
章/节	数学应用

某大型整数矩阵用二维整数组 G[1：2M ，1：2N]表示，其中M和N是较大的整数，而且每行从左到右都已是递增排序，每到从上到下也都已是递增排序。元素G[M，N]将该矩阵划分为四个子矩阵A[1：M，1：N]，B[1:M，(N+1):2N]，C[(M+1）:2M，1:N ]，D[(M+1）:2M，(N+1):2N]。如果某个整数E大于A[M，N]，则E（）。

A. 只可能在子矩阵A中

B. 只可能在子矩阵B或C中

C. 只可能在子矩阵B、C或D中

D. 只可能在子矩阵D中

相关试题数学应用

第65题

2019年上半年

数控编程常需要用参数来描述需要加工的零件的图形。在平面坐标系内，确定一个点需要2个独立的参数，确定一个正方形需要（）个独立的参数。

第65题

2016年下半年

菲波那契(Fibonacci)数列定义为f(1)=1，f(2)=1，n>2时，f(n)=f(n-1)+f(n-2)。据此可以导出，n>1时，有向量的递推关系式：
(f(n+1),f(n))=(f(n),f(n-1))A。其中A是2*2矩阵（64）。从而..

第61题

2017年上半年

某项目计划20天完成，花费4万元。在项目开始后的前10天内遇到了偶发事件，到第10天末进行中期检查时，发现已花费2万元，但只完成了40%的工作量。如果此后不发生偶发事件，则该项目将（）。

知识点讲解

· 矩阵

· 排序

· 数组

矩阵

矩阵是很多科学与工程计算问题中研究的数学对象。在数据结构中主要讨论如何在尽可能节省存储空间的情况下，使矩阵的各种运算能高效地进行。

在一些矩阵中，存在很多值相同的元素或者是零元素。为了节省存储空间，可以对这类矩阵进行压缩存储。压缩存储的含义是为多个值相同的元素只分配一个存储单元，对零元不分配存储单元。

特殊矩阵

常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵等。对于特殊矩阵，由于其非零元的分布都有一定的规律，所以可将其压缩存储在一维数组中，并建立起每个非零元在矩阵中的位置与其在一维数组中的位置之间的对应关系。

若矩阵A_n_×_n中的元素有a_ij=a_ji（1≤i，j≤n）的特点，则称之为对称矩阵。

若为对称矩阵中的每一对元素分配一个存储单元，那么就可将n²个元素压缩存储到能存放n（n+1）/2个元素的存储空间中。不失一般性，以行为主序存储下三角（包括对角线）中的元素。假设以一维数组B［n（n+1）/2］作为n阶对称矩阵A中元素的存储空间，则B［k］（0≤k<n（n+1）/2）与矩阵元素a_ij（a_ji）之间存在着一一对应的关系。

对角矩阵是指矩阵中的非零元素都集中在以主对角线为中心的带状区域中，即除了主对角线上和直接在对角线上、下方若干条对角线上的元素外，其余的矩阵元素都为零。一个n阶的三对角矩阵如下图所示。

三对角矩阵示意图

若以行为主序将n阶三对角矩阵A_n_×_n的非零元素存储在一维数组B［k］（0≤k<3n-2）中，则元素位置之间的对应关系为：

k=3×（i-1）-1+j-i+1=2i+j-3（1≤i，j≤n）

其他特殊矩阵可作类似的推导和计算，这里不再一一说明。

稀疏矩阵

在一个矩阵中，若非零元素的个数远远少于零元素的个数，且非零元素的分布没有规律，则称之为稀疏矩阵。

对于稀疏矩阵，存储非零元素时必须同时存储其位置（即行号和列号），所以三元组（i，j，a_ij）可唯一确定矩阵中的一个元素。由此，一个稀疏矩阵可由表示非零元素的三元组及其行、列数唯一确定。

一个6行7列的稀疏矩阵如下图所示，其三元组表为（1，2，12），（1，3，9），（3，1，-3），（3，6，14），（4，3，24），（5，2，18），（6，1，15），（6，4，-7））。

稀疏矩阵示意图

稀疏矩阵的三元组表构成一个线性表，其顺序存储结构称为三元组顺序表，其链式存储结构称为十字链表。

排序

假设含n个记录的文件内容为｛R₁，R₂，…，R_n｝，其相应的关键字为｛k₁，k₂，…，k_n｝。经过排序确定一种排列｛R_j₁，R_j₂，…，R_jn｝，使得它们的关键字满足如下递增（或递减）关系：k_j₁≤k_j₂≤…≤k_jn（或k_j₁≥k_j₂≥…≥k_jn）。

数组

数组的定义及基本运算

一维数组是长度固定的线性表，数组中的每个数据元素类型相同。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