免费智能真题库 > 历年试卷 > 程序员 > 2017年下半年 程序员 下午试卷 案例
  第4题      
  知识点:   查找   排列   数组   折半查找

 
【说明】
数组中的元素已经排列有序时,可以采用折半查找(二分查找)法查找一个元素。下面的函数biSearch(int r[],int low,int high,int key)用非递归方式在数组r中进行二分查找,函数biSearch_rec(int r[],int low,int high,int key)采用递归方式在数组r中进行二分查找,函数的返回值都为所找到元素的下标;若找不到,则返回-1。
【C函数1】
int biSearch(int r[],int low,int high,int key)
//r[low..high] 中的元素按非递减顺序排列
//用二分查找法在数组r中查找与key相同的元素
//若找到则返回该元素在数组r的下标,否则返回-1
{
   int mid;
   while((1)) {
        mid = (low+high)/2 ;
        if (key ==r[mid])
              return mid;
        else if (key<r[mid])
                 (2);
        else
                 (3);
    }/*while*/
    return -1;
}/*biSearch*/

【C 函数2】
int biSearch_rec(int r[],int low,int high,int key)
//r[low..high]中的元素按非递减顺序排列
//用二分查找法在数组r中查找与key相同的元素
//若找到则返回该元素在数组r的下标,否则返回-1
{
   int mid;
   if((4)) {
        mid = (low+high)/2 ;
        if (key ==r[mid])
              return mid;
        else if (key<r[mid])
              return biSearch_rec((5),key);
        else
              return biSearch_rec((6),key);
   }/*if*/
   return -1;
}/*biSearch_rec*/
 
问题:4.1   (12分)
请填充C函数1和C函数2中的空缺,将解答填入答题纸的对应栏内。
 
问题:4.2   (3分)
若有序数组中有n个元素,采用二分查找法查找一个元素时,最多与( )个数组元素进行比较,即可确定查找结果。
(7)备选答案:
A.[log2(n+1)] B.[n/2] C.n-1 D.n
 
 
 

   知识点讲解    
   · 查找    · 排列    · 数组    · 折半查找
 
       查找
        1)顺序查找
        顺序查找又称线性查找,顺序查找的过程是从线性表的一端开始,依次逐个与表中元素的关键字值进行比较,如果找到其关键字与给定值相等的元素,则查找成功;若表中所有元素的关键字与给定值比较都不成功,则查找失败。
        2)折半查找
        折半查找的过程是先将给定值与有序线性表中间位置上元素的关键字进行比较,若两者相等,则查找成功;若给定值小于该元素的关键字,那么选取中间位置元素关键字值小的那部分元素作为新的查找范围,然后继续进行折半查找;如果给定值大于该元素的关键字,那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围,然后继续进行折半查找,直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。
        3)分块查找
        在分块查找过程中,首先将表分成若干块,每一块中关键字不一定有序,但块之间是有序的。此外,还建立了一个索引表,索引表按关键字有序。分块查找过程需分两步进行:先确定待查记录所在的块;然后在块中顺序查找。
        4)哈希表及其查找
        根据设定的哈希函数H(key)和处理冲突的方法,将一组关键字映射到一个有限的连续地址集上,并以关键字在地址集中的像作为记录在表中的存储位置,这种表称为哈希表,也称散列表。这一过程所得到的存储位置称为散列地址,由此形成的查找方法称为散列查找。
 
       排列
        设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的三位数有个。根据加法原理,符合条件的三位数个数是
 
       数组
               数组的定义及基本运算
               一维数组是长度固定的线性表,数组中的每个数据元素类型相同。n维数组是定长线性表在维数上的扩张,即线性表中的元素又是一个线性表。
               设有n维数组Ab1b2,…,bn],其每一维的下界都为1,bi是第i维的上界。从数据结构的逻辑关系角度来看,A中的每个元素Aj1j2,…,jn](1≤jibi)都被n个关系所约束。在每个关系中,除第一个和最后一个元素外,其余元素都只有一个直接后继和一个直接前驱。因此就单个关系而言,这n个关系仍是线性的。
               以下面的二维数组Am][n]为例,可以把它看成是一个定长的线性表,它的每个元素也是一个定长线性表。
               
               可将A看作一个行向量形式的线性表:
               Am*n=[[a11a12a1n][a21a22a2n]…[am1am2amn]]
               也可将A看作列向量形式的线性表:
               Am*n=[[a11a21am1][a12a22am2]…[a1na2namn]]
               数组结构的特点如下:
               (1)数据元素数目固定。一旦定义了一个数组结构,就不再有元素的增减变化。
               (2)数据元素具有相同的类型。
               (3)数据元素的下标关系具有上下界的约束且下标有序。
               在数组中通常做下面两种操作:
               (1)取值操作。给定一组下标,读其对应的数据元素。
               (2)赋值操作。给定一组下标,存储或修改与其相对应的数据元素。
               几乎所有的程序设计语言都提供了数组类型。实际上,在语言中把数组看成是具有共同名字的同一类型多个变量的集合。需要注意的是,不能对数组进行整体的运算,只能对单个数组元素进行运算。
               数组的顺序存储
               由于数组一般不作插入和删除运算,也就是说,一旦定义了数组,则结构中的数据元素个数和元素之间的关系就不再发生变动,因此数组适合于采用顺序存储结构。
               对于数组,一旦确定了它的维数和各维的长度,便可为它分配存储空间。反之,只要给出一组下标便可求得相应数组元素的存储位置,也就是说,在数据的顺序存储结构中,数据元素的位置是其下标的线性函数。
               二维数组的存储结构可分为以行为主序(按行存储)和以列为主序(按列存储)两种方法,如下图所示。
               
               二维数组的两种存储方式
               设每个数据元素占用L个单元,mn为数组的行数和列数,那么以行为主序优先存储的地址计算公式为:
               Loc(aij)=Loc(a11)+((i-1)×n+(j-1))×L
               同理,以列为主序优先存储的地址计算公式为:
               Loc(aij)=Loc(a11)+((j-l)×m+(i-1))×L
 
       折半查找
        折半查找也称为二分查找,其基本思想是:先令查找表中间位置记录的关键字和给定值比较,若相等,则查找成功;若不等,则缩小范围,直至新的查找区间中间位置记录的关键字等于给定值或者查找区间没有元素时(表明查找不成功)为止。
        设查找表的元素存储在一维数组r[1..n]中,那么在表中的元素已经按关键字递增(或递减)排序的情况下,进行折半查找的方法是:首先比较key值与表r中间位置(下标为mid)的记录的关键字,若相等,则查找成功。若key>r[mid].key,则说明待查记录只可能在后半个子表r[mid+1..n]中,下一步应在后半个子表中再进行折半查找;若keyr的前半个子表中进行折半查找。这样通过逐步缩小范围,直到查找成功或子表为空时失败为止。
        【函数】设有一个整型数组中的元素是按非递减的方式排列的,在其中进行折半查找的算法如下:
        
        折半查找的过程可以用一棵二叉树描述,方法是:以当前查找区间的中间位置上的记录作为根,左子表和右子表中的记录分别作为根的左子树和右子树上的结点,这样构造的二叉树称为折半查找判定树。例如,具有11个结点的折半查找判定树如下图所示,结点中的数字表示元素的序号。
        
        具有11个结点的折半查找判定树
        从折半查找判定树可以看出,查找成功时,折半查找的过程恰好走了一条从根结点到被查结点的路径,关键字进行比较的次数即为被查找结点在树中的层数。因此,折半查找在查找成功时进行比较的关键字数最多不超过树的高度,而具有n个结点的判定树的高度为,所以折半查找在查找成功时和给定值进行比较的关键字个数至多为
        给判定树中所有结点的空指针域加上一个指向一个方型结点的指针,称这些方型结点为判定树的外部结点(与之相对,称那些圆形结点为内部结点),如下图所示。那么折半查找不成功的过程就是走了一条从根结点到外部结点的路径。和给定值进行比较的关键字个数等于该路径上内部结点个数。因此,折半查找在查找不成功时和给定值进行比较的关键字个数最多也不会超过
        
        加上外部结点的判定树
        那么折半查找的平均查找长度是多少呢?为了方便起见,不妨设结点总数为n=2h-1,则判定树是深度为h=log2n+1)的满二叉树。在等概率情况下,折半查找的平均查找长度为:
        
        当n值较大时,ASLbs≈log2n+1)-1。
        折半查找比顺序查找的效率要高,但它要求查找表进行顺序存储并且按关键字有序排列。因此,折半查找适用于表不易变动,且又经常进行查找的情况。
   题号导航      2017年下半年 程序员 下午试卷 案例   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
 
第4题    在手机中做本题