免费智能真题库 > 历年试卷 > 信息系统管理工程师 > 2016年上半年 信息系统管理工程师 上午试卷 综合知识
  第11题      
  知识点:   数组   矩阵   排列
  关键词:   二维数组   数组        章/节:   数据结构与算法基本概念       

 
设有一个m行n列的矩阵存储在二维数组A[1…m,1…n]中,将数组元素按行排列,对于A[i,j](1≤i≤m,1≤j≤n),排列在其前面的元素个数为(11)。
 
 
  A.  i×(n-1)+j
 
  B.  (i-1)×n+j-1
 
  C.  i×(m-1)+j
 
  D.  (i-1)×m+j-1
 
 
 

 
  第7题    2019年上半年  
   21%
高级语言程序中的( )表示一组相同类型变量的有序集合。
  第10题    2014年上半年  
   30%
( )不属于线性的数据结构。
 
   知识点讲解    
   · 数组    · 矩阵    · 排列
 
       数组
        数组是大家都已经很熟悉的一种数据类型,几乎所有高级语言程序设计中都设定了数组类型。数组可以看成是线性表的推广,数组的每个元素由一个值和一组下标确定,在数组中,对于每组有定义的下标都存在一个与之相对应的值;而线性表是有限结点的有序集合,若将其每个结点的序号看成下标,线性表就是一维数组(向量);当数组为多维数组时,其对应线性表中的每个元素又是一个数据结构而已。数组使用时需要的内存空间远远大于普通变量的空间,所以按内存开辟空间的时机来划分数组,在程序编译时开辟内存区的数组称为静态数组,运行时根据需要开辟内存区的数组称做动态数组。简单来说,使用数值常量或符号常量定义下标的数组为静态数组,首先声明一个没有下标的数组名,然后在使用时再次声明数组的下标,称为动态数组。用C语言来描述数组如下:
        
        由于数组一般不做插入或删除操作,也就是说,一旦建立了数组,则结构中的数组元素个数和元素之间的关系就不再发生变动,即它们的逻辑结构就固定下来了,不再发生变化。因此,一般采用顺序存储结构表示数组。多维数组的顺序存储有两种形式:以列序为主序和以行序为主序。
               存放规则
               行优先顺序也称为低下标优先或左边下标优先于右边下标。具体实现时,按行号从小到大的顺序,先将第一行中元素全部存放好,再存放第二行元素,第三行元素,依次类推……
               在Basic语言、Pascal语言、C/C++语言等高级语言程序设计中,都是按行优先顺序存放的。例如,对刚才的Am×n二维数组,可用如下形式存放到内存:a00,a01,…a0 n-1, a10,all,…,a1 n-1, …,am-1 0, am-1 1,…,am-1 n-1。即二维数组按行优先存放到内存后,变成了一个线性序列(线性表)。
               因此,可以得出多维数组按行优先存放到内存的规律:最左边下标变化最慢,最右边下标变化最快,右边下标变化一遍,与之相邻的左边下标才变化一次。因此,在算法中,最左边下标可以看成是外循环,最右边下标可以看成是最内循环。
               地址计算
               由于多维数组在内存中排列成一个线性序列,因此,若知道第一个元素的内存地址,如何求得其他元素的内存地址?可以将它们的地址排列看成是一个等差数列,假设每个元素占1个字节,元素aij的存储地址应为第一个元素的地址加上排在aij前面的元素所占用的单元数,而aij的前面有i行(0~i-1)共i×n个元素,而本行前面又有j个元素,故aij的前面一共有i×n+j个元素,设a00的内存地址为LOC (a00),则aij的内存地址按等差数列计算为LOC (aij)=LOC(a00)+(i×n+j)×1。同理,三维数组Am×n×p按行优先存放的地址计算公式为:LOC (aijk)=LOC(a000)+(i×n×p+j×p+k)×1。
 
       矩阵
        矩阵是很多科学与工程计算问题中研究的数学对象。在数据结构中主要讨论如何在尽可能节省存储空间的情况下,使矩阵的各种运算能高效地进行。
        在一些矩阵中,存在很多值相同的元素或者是零元素。为了节省存储空间,可以对这类矩阵进行压缩存储。压缩存储的含义是为多个值相同的元素只分配一个存储单元,对零元不分配存储单元。
               特殊矩阵
               常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵等。对于特殊矩阵,由于其非零元的分布都有一定的规律,所以可将其压缩存储在一维数组中,并建立起每个非零元在矩阵中的位置与其在一维数组中的位置之间的对应关系。
               若矩阵An×n中的元素有aij=aji(1≤ijn)的特点,则称之为对称矩阵。
               若为对称矩阵中的每一对元素分配一个存储单元,那么就可将n2个元素压缩存储到能存放nn+1)/2个元素的存储空间中。不失一般性,以行为主序存储下三角(包括对角线)中的元素。假设以一维数组Bnn+1)/2]作为n阶对称矩阵A中元素的存储空间,则Bk](0≤k<nn+1)/2)与矩阵元素aijaji)之间存在着一一对应的关系。
               
               对角矩阵是指矩阵中的非零元素都集中在以主对角线为中心的带状区域中,即除了主对角线上和直接在对角线上、下方若干条对角线上的元素外,其余的矩阵元素都为零。一个n阶的三对角矩阵如下图所示。
               
               三对角矩阵示意图
               若以行为主序将n阶三对角矩阵An×n的非零元素存储在一维数组Bk](0≤k<3n-2)中,则元素位置之间的对应关系为:
               k=3×(i-1)-1+j-i+1=2i+j-3(1≤ijn
               其他特殊矩阵可作类似的推导和计算,这里不再一一说明。
               稀疏矩阵
               在一个矩阵中,若非零元素的个数远远少于零元素的个数,且非零元素的分布没有规律,则称之为稀疏矩阵。
               对于稀疏矩阵,存储非零元素时必须同时存储其位置(即行号和列号),所以三元组(ijaij)可唯一确定矩阵中的一个元素。由此,一个稀疏矩阵可由表示非零元素的三元组及其行、列数唯一确定。
               一个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))。
               
               稀疏矩阵示意图
               稀疏矩阵的三元组表构成一个线性表,其顺序存储结构称为三元组顺序表,其链式存储结构称为十字链表。
 
       排列
        设S为具有n个不同元素的n元集,从S中选取r个元素且考虑其顺序称为S的一个r排列,不同排列的总数记为,有时也用P(nr)表示。如果r=n,则称这个排列为S的全排列。从排列的定义可知,如果两个排列相同,不仅这两个排列的元素必须完全相同,而且排列的顺序也必须完全相同。
        
        例子1:用0~9这十个数字,可以组成多少个没有重复数字的三位数?
        解法1:由于百位数上的数字不能为0,因此可先考虑排百位上的数字,再排十位和个位上的数字。百位数上的数字只能从除0以外的1~9数字中任选一个,有种;十位和个位上的数字,可以从余下的9个数字中任选两个,有种。根据乘法原理,所求的三位数的个数是
        解法2:可先考虑从0~9这十个数字中任取三个数字的排列数(),再减去其中以0开头的排列数()。因此,所求的三位数的个数是
        解法3:符合条件的三位数可以分为三类:每一位数字都不是0的三位数有个;个位数是0的三位数有个;十位数是0的三位数有个。根据加法原理,符合条件的三位数个数是
   题号导航      2016年上半年 信息系统管理工程师 上午试卷 综合知识   本试卷我的完整做题情况  
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 /
 
第11题    在手机中做本题