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

 
【说明】
下面流程图的功能是：在给定的一个整数序列中查找最长的连续递增子序列。设序列存放在数组A[1:n](n≥2)中，要求寻找最长递增子序列A[K : K+L-1](即A[K]<A[K+1] <…<A[K+L-1])。流程图中，用Kj和Lj分别表示动态子序列的起始下标和长度，最后输出最长递增子序列的起始下标K和长度L。
例如，对于序列A={1，2，4，4，5，6，8，9，4，5，8}，将输出 K=4，L=5。
【流程图】
 
注：循环开始框内应给出循环控制变量的初值和终值，默认递增值为1，格式为：循环控制变量=初值，终值
 
问题：1.1   （共15分）
阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内。
 
 
 

   知识点讲解    
   · 查找    · 数组
 
       查找
        1）顺序查找
        顺序查找又称线性查找，顺序查找的过程是从线性表的一端开始，依次逐个与表中元素的关键字值进行比较，如果找到其关键字与给定值相等的元素，则查找成功；若表中所有元素的关键字与给定值比较都不成功，则查找失败。
        2）折半查找
        折半查找的过程是先将给定值与有序线性表中间位置上元素的关键字进行比较，若两者相等，则查找成功；若给定值小于该元素的关键字，那么选取中间位置元素关键字值小的那部分元素作为新的查找范围，然后继续进行折半查找；如果给定值大于该元素的关键字，那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围，然后继续进行折半查找，直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。
        3）分块查找
        在分块查找过程中，首先将表分成若干块，每一块中关键字不一定有序，但块之间是有序的。此外，还建立了一个索引表，索引表按关键字有序。分块查找过程需分两步进行：先确定待查记录所在的块；然后在块中顺序查找。
        4）哈希表及其查找
        根据设定的哈希函数H（key）和处理冲突的方法，将一组关键字映射到一个有限的连续地址集上，并以关键字在地址集中的像作为记录在表中的存储位置，这种表称为哈希表，也称散列表。这一过程所得到的存储位置称为散列地址，由此形成的查找方法称为散列查找。
 
       数组
               数组的定义及基本运算
               一维数组是长度固定的线性表，数组中的每个数据元素类型相同。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
   题号导航      2015年下半年 程序员 下午试卷 案例   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
 
第1题    在手机中做本题