免费智能真题库 > 历年试卷 > 程序员 > 2017年下半年 程序员 上午试卷 综合知识
  第38题      
  知识点:   静态查找表   查找   折半查找
  关键词:   二分查找   关键码        章/节:   常用算法       

 
对关键码序列(9,12,15,20,24,29,56,69,87)进行二分查找(折半查找),若要查找关键码15;则需依次与( )进行比较。
 
 
  A.  87、29、15
 
  B.  9、12、15
 
  C.  24、12、15
 
  D.  24、20、15
 
 
 

 
  第42题    2012年上半年  
   46%
以下关于顺序查找和二分查找的叙述中,正确的是(42)。
  第41题    2015年下半年  
   44%
(41) 不符合二叉排序树的定义。
  第38题    2020年下半年  
   43%
下图所示为一个二叉排序树(二叉査找树),其先序遍历序列为( )。
   知识点讲解    
   · 静态查找表    · 查找    · 折半查找
 
       静态查找表
        对查找表经常要进行两种操作:查询某个特定的数据元素是否在查找表中;检索某个特定的数据元素的各种属性。通常只进行这两种操作的查找表称为静态查找表。静态查找表主要有顺序查找、折半查找和分块查找。
        1)顺序查找
        顺序查找,又称线性查找,顺序查找的过程是从线性表的一端开始,依次逐个与表中元素的关键字值进行比较,如果找到其关键字与给定值相等的元素,则查找成功;若表中所有元素的关键字与给定值比较都不成功,则查找失败。
        在等概率的情况下,顺序查找成功的平均查找长度为:
        
        2)折半查找
        折半查找是一种采用顺序存储结构的线性表进行查找的方法,也称二分查找。在进行折半查找之前,线性表中的数据元素必须按照关键字的值升序或降序排列。
        折半查找的过程是先将给定值与有序线性表中间位置上的元素的关键字进行比较,若两者相等,则查找成功;若给定值小于该元素的关键字,那么选取中间位置元素关键字值小的那部分元素作为新的查找范围,然后继续进行折半查找;如果给定值大于该元素的关键字,那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围,然后继续进行折半查找,直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。平均查找长度为:
        
        3)分块查找
        分块查找又称索引顺序查找,是顺序查找的一种改进方法。在分块查找过程中,首先将表分成若干块,每一块中关键字不一定有序,但块之间是有序的。此外,还建立了一个索引表,索引表按关键字有序。分块查找过程需分两步进行:先确定待查记录所在的块,然后在块中顺序查找。
        假设长度为n的分块表分成b块,每块中元素个数为s,又设每个元素的查找概率都相等,块间块内均采用线性查找方法,则平均查找长度为:
        
 
       查找
        1)顺序查找
        顺序查找又称线性查找,顺序查找的过程是从线性表的一端开始,依次逐个与表中元素的关键字值进行比较,如果找到其关键字与给定值相等的元素,则查找成功;若表中所有元素的关键字与给定值比较都不成功,则查找失败。
        2)折半查找
        折半查找的过程是先将给定值与有序线性表中间位置上元素的关键字进行比较,若两者相等,则查找成功;若给定值小于该元素的关键字,那么选取中间位置元素关键字值小的那部分元素作为新的查找范围,然后继续进行折半查找;如果给定值大于该元素的关键字,那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围,然后继续进行折半查找,直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。
        3)分块查找
        在分块查找过程中,首先将表分成若干块,每一块中关键字不一定有序,但块之间是有序的。此外,还建立了一个索引表,索引表按关键字有序。分块查找过程需分两步进行:先确定待查记录所在的块;然后在块中顺序查找。
        4)哈希表及其查找
        根据设定的哈希函数H(key)和处理冲突的方法,将一组关键字映射到一个有限的连续地址集上,并以关键字在地址集中的像作为记录在表中的存储位置,这种表称为哈希表,也称散列表。这一过程所得到的存储位置称为散列地址,由此形成的查找方法称为散列查找。
 
       折半查找
        折半查找也称为二分查找,其基本思想是:先令查找表中间位置记录的关键字和给定值比较,若相等,则查找成功;若不等,则缩小范围,直至新的查找区间中间位置记录的关键字等于给定值或者查找区间没有元素时(表明查找不成功)为止。
        设查找表的元素存储在一维数组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 /
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 /
 
第38题    在手机中做本题