免费智能真题库 > 历年试卷 > 程序员 > 2017年上半年 程序员 下午试卷 案例
  第1题      
  知识点：   查找   矩阵   数组

 
【说明】
设有二维整数数组（矩阵）A[1:m,1:n]，其每行元素从左到右是递增的，每列元素从上到下是递增的。以下流程图旨在该矩阵中寻找与给定整数X相等的数。如果找不到则输出“false”;只要找到一个（可能有多个）就输出“True”以及该元素的下标i和j（注意数组元素的下标从1开始）。
例如，在如下矩阵中查找整数8，则输出为：True,4,1
2 4 6 9
4 5 9 10
6 7 10 12
8 9 11 13
流程图中采用的算法如下：从矩阵的右上角元素开始，按照一定的路线逐个取元素与给定整数X进行比较（必要时向左走一步或向下走一步取下一个元素），直到找到相等的数或超出矩阵范围（找不到）。
【流程图】

该算法的时间复杂数是（5）。
供选择答案：A.O（1） B.O（m+n） C.O（m*n） D.O（m2+n2）
 
问题：1.1   （共15分）
阅读以下说明和流程图和问题，填补流程图和问题中的空缺，将解答填入答题纸的对应栏内。
 
 
 

   知识点讲解    
   · 查找    · 矩阵    · 数组
 
       查找
        1）顺序查找
        顺序查找又称线性查找，顺序查找的过程是从线性表的一端开始，依次逐个与表中元素的关键字值进行比较，如果找到其关键字与给定值相等的元素，则查找成功；若表中所有元素的关键字与给定值比较都不成功，则查找失败。
        2）折半查找
        折半查找的过程是先将给定值与有序线性表中间位置上元素的关键字进行比较，若两者相等，则查找成功；若给定值小于该元素的关键字，那么选取中间位置元素关键字值小的那部分元素作为新的查找范围，然后继续进行折半查找；如果给定值大于该元素的关键字，那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围，然后继续进行折半查找，直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。
        3）分块查找
        在分块查找过程中，首先将表分成若干块，每一块中关键字不一定有序，但块之间是有序的。此外，还建立了一个索引表，索引表按关键字有序。分块查找过程需分两步进行：先确定待查记录所在的块；然后在块中顺序查找。
        4）哈希表及其查找
        根据设定的哈希函数H（key）和处理冲突的方法，将一组关键字映射到一个有限的连续地址集上，并以关键字在地址集中的像作为记录在表中的存储位置，这种表称为哈希表，也称散列表。这一过程所得到的存储位置称为散列地址，由此形成的查找方法称为散列查找。
 
       矩阵
        矩阵是很多科学与工程计算问题中研究的数学对象。在数据结构中主要讨论如何在尽可能节省存储空间的情况下，使矩阵的各种运算能高效地进行。
        在一些矩阵中，存在很多值相同的元素或者是零元素。为了节省存储空间，可以对这类矩阵进行压缩存储。压缩存储的含义是为多个值相同的元素只分配一个存储单元，对零元不分配存储单元。
               特殊矩阵
               常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵等。对于特殊矩阵，由于其非零元的分布都有一定的规律，所以可将其压缩存储在一维数组中，并建立起每个非零元在矩阵中的位置与其在一维数组中的位置之间的对应关系。
               若矩阵An×n中的元素有aij=aji（1≤i，j≤n）的特点，则称之为对称矩阵。
               若为对称矩阵中的每一对元素分配一个存储单元，那么就可将n2个元素压缩存储到能存放n（n+1）/2个元素的存储空间中。不失一般性，以行为主序存储下三角（包括对角线）中的元素。假设以一维数组B［n（n+1）/2］作为n阶对称矩阵A中元素的存储空间，则B［k］（0≤k<n（n+1）/2）与矩阵元素aij（aji）之间存在着一一对应的关系。
               
               对角矩阵是指矩阵中的非零元素都集中在以主对角线为中心的带状区域中，即除了主对角线上和直接在对角线上、下方若干条对角线上的元素外，其余的矩阵元素都为零。一个n阶的三对角矩阵如下图所示。
               
               三对角矩阵示意图
               若以行为主序将n阶三对角矩阵An×n的非零元素存储在一维数组B［k］（0≤k<3n-2）中，则元素位置之间的对应关系为：
               k=3×（i-1）-1+j-i+1=2i+j-3（1≤i，j≤n）
               其他特殊矩阵可作类似的推导和计算，这里不再一一说明。
               稀疏矩阵
               在一个矩阵中，若非零元素的个数远远少于零元素的个数，且非零元素的分布没有规律，则称之为稀疏矩阵。
               对于稀疏矩阵，存储非零元素时必须同时存储其位置（即行号和列号），所以三元组（i，j，aij）可唯一确定矩阵中的一个元素。由此，一个稀疏矩阵可由表示非零元素的三元组及其行、列数唯一确定。
               一个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维数组是定长线性表在维数上的扩张，即线性表中的元素又是一个线性表。
               设有n维数组A［b1，b2，…，bn］，其每一维的下界都为1，bi是第i维的上界。从数据结构的逻辑关系角度来看，A中的每个元素A［j1，j2，…，jn］（1≤ji≤bi）都被n个关系所约束。在每个关系中，除第一个和最后一个元素外，其余元素都只有一个直接后继和一个直接前驱。因此就单个关系而言，这n个关系仍是线性的。
               以下面的二维数组A［m］［n］为例，可以把它看成是一个定长的线性表，它的每个元素也是一个定长线性表。
               
               可将A看作一个行向量形式的线性表：
               Am*n=［［a11a12…a1n］［a21a22…a2n］…［am1am2…amn］］
               也可将A看作列向量形式的线性表：
               Am*n=［［a11a21…am1］［a12a22…am2］…［a1na2n…amn］］
               数组结构的特点如下：
               （1）数据元素数目固定。一旦定义了一个数组结构，就不再有元素的增减变化。
               （2）数据元素具有相同的类型。
               （3）数据元素的下标关系具有上下界的约束且下标有序。
               在数组中通常做下面两种操作：
               （1）取值操作。给定一组下标，读其对应的数据元素。
               （2）赋值操作。给定一组下标，存储或修改与其相对应的数据元素。
               几乎所有的程序设计语言都提供了数组类型。实际上，在语言中把数组看成是具有共同名字的同一类型多个变量的集合。需要注意的是，不能对数组进行整体的运算，只能对单个数组元素进行运算。
               数组的顺序存储
               由于数组一般不作插入和删除运算，也就是说，一旦定义了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动，因此数组适合于采用顺序存储结构。
               对于数组，一旦确定了它的维数和各维的长度，便可为它分配存储空间。反之，只要给出一组下标便可求得相应数组元素的存储位置，也就是说，在数据的顺序存储结构中，数据元素的位置是其下标的线性函数。
               二维数组的存储结构可分为以行为主序（按行存储）和以列为主序（按列存储）两种方法，如下图所示。
               
               二维数组的两种存储方式
               设每个数据元素占用L个单元，m、n为数组的行数和列数，那么以行为主序优先存储的地址计算公式为：
               Loc（aij）=Loc（a11）+（（i-1）×n+（j-1））×L
               同理，以列为主序优先存储的地址计算公式为：
               Loc（aij）=Loc（a11）+（（j-l）×m+（i-1））×L
   题号导航      2017年上半年 程序员 下午试卷 案例   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
 
第1题    在手机中做本题