免费智能真题库 > 历年试卷 > 软件评测师 > 2017年下半年 软件评测师 上午试卷 综合知识
  第43题      
  知识点:   查找   查找算法   折半查找
  关键词:   算法        章/节:   程序设计语言知识       

 
采用折半查找算法有序表{7,15,18,21,27,36,42,48 ,51,54,60,72}中寻找值为15和38,分别需要进行( )次元素之间的比较。
 
 
  A.  3和1
 
  B.  3和2
 
  C.  4和1
 
  D.  4和3
 
 
 

 
  第16题    2017年下半年  
   27%
下图所示的非确定有限自动机(s0为初态, S3为终态)可识别字符串( )。
  第40题    2016年下半年  
   60%
某个应用中,需要对输入数据进行排序,输入数据序列基本有序(如输入为1,2,5,3,4,6,8,7)。在这种情况下,采用(40)排序算法最好,..
  第16题    2016年下半年  
   53%
若某线性表长度为n且采用顺序存储方式,则运算速度最快的操作是(16)。
   知识点讲解    
   · 查找    · 查找算法    · 折半查找
 
       查找
        1)顺序查找
        顺序查找又称线性查找,顺序查找的过程是从线性表的一端开始,依次逐个与表中元素的关键字值进行比较,如果找到其关键字与给定值相等的元素,则查找成功;若表中所有元素的关键字与给定值比较都不成功,则查找失败。
        2)折半查找
        折半查找的过程是先将给定值与有序线性表中间位置上元素的关键字进行比较,若两者相等,则查找成功;若给定值小于该元素的关键字,那么选取中间位置元素关键字值小的那部分元素作为新的查找范围,然后继续进行折半查找;如果给定值大于该元素的关键字,那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围,然后继续进行折半查找,直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。
        3)分块查找
        在分块查找过程中,首先将表分成若干块,每一块中关键字不一定有序,但块之间是有序的。此外,还建立了一个索引表,索引表按关键字有序。分块查找过程需分两步进行:先确定待查记录所在的块;然后在块中顺序查找。
        4)哈希表及其查找
        根据设定的哈希函数H(key)和处理冲突的方法,将一组关键字映射到一个有限的连续地址集上,并以关键字在地址集中的像作为记录在表中的存储位置,这种表称为哈希表,也称散列表。这一过程所得到的存储位置称为散列地址,由此形成的查找方法称为散列查找。
 
       查找算法
               静态查找表
               对查找表经常要进行两种操作:查询某个特定的数据元素是否在查找表中;检索某个特定的数据元素的各种属性。通常只进行这两种操作的查找表称为静态查找表。静态查找表主要有顺序查找、折半查找和分块查找。
               1)顺序查找
               顺序查找,又称线性查找,顺序查找的过程是从线性表的一端开始,依次逐个与表中元素的关键字值进行比较,如果找到其关键字与给定值相等的元素,则查找成功;若表中所有元素的关键字与给定值比较都不成功,则查找失败。
               在等概率的情况下,顺序查找成功的平均查找长度为:
               
               2)折半查找
               折半查找是一种采用顺序存储结构的线性表进行查找的方法,也称二分查找。在进行折半查找之前,线性表中的数据元素必须按照关键字的值升序或降序排列。
               折半查找的过程是先将给定值与有序线性表中间位置上的元素的关键字进行比较,若两者相等,则查找成功;若给定值小于该元素的关键字,那么选取中间位置元素关键字值小的那部分元素作为新的查找范围,然后继续进行折半查找;如果给定值大于该元素的关键字,那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围,然后继续进行折半查找,直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。平均查找长度为:
               
               3)分块查找
               分块查找又称索引顺序查找,是顺序查找的一种改进方法。在分块查找过程中,首先将表分成若干块,每一块中关键字不一定有序,但块之间是有序的。此外,还建立了一个索引表,索引表按关键字有序。分块查找过程需分两步进行:先确定待查记录所在的块,然后在块中顺序查找。
               假设长度为n的分块表分成b块,每块中元素个数为s,又设每个元素的查找概率都相等,块间块内均采用线性查找方法,则平均查找长度为:
               
               动态查找表
               若在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已存在的某个数据元素,则称此类查找表为动态查找表。动态查找表的特点是表结构是动态生成的。
               1)二叉排序树的定义
               二叉排序树又称二叉查找树,它或者是一棵空树,或者是具有以下性质的二叉树。
               .若它的左子树非空,则左子树上所有节点的值均小于根节点的值。
               .若它的右子树非空,则右子树上所有节点的值均大于或等于根节点的值。
               .左、右子树本身就是两棵二叉排序树。
               2)二叉排序树的查找过程
               若二叉树为非空,将给定值与根节点的关键字值进行比较,若相等,则查找成功;若不等,则当根节点的关键字值大于给定值时,到根的左子树中进行查找;否则到根的右子树进行查找。
               3)二叉排序树中插入节点的操作
               二叉排序树是通过依次输入数据元素并把它们插到二叉树的适当位置上构造起来的,具体过程如下:读入一个元素,建立一个新节点。若二叉排序树非空,则将新节点的值与根节点的值进行比较,如果小于根节点的值,则插入左子树中,否则插入右子树中;若二叉树为空,则新节点作为二叉排序树的根节点。
               4)二叉排序树中删除节点的操作
               在二叉排序树中删除一个节点,不能把以该节点为根的子树都删除,只能删除这个节点并仍旧保持二叉排序树的特性。
               哈希表
               1)哈希表的定义
               根据设定的哈希函数H(key)和处理冲突的方法,将一组关键字映射到一个有限的连续地址集上,并以关键字在地址集中的像作为记录在表中的存储位置,这种表称为哈希表,也称散列表。这一过程所得到的存储位置称为散列地址,由此形成的查找方法称为散列查找。当选择了某个散列函数后,不同的关键字可能与同一个散列地址相对应,这种现象称为冲突。
               对于哈希表,主要考虑两个问题:一是如何构造哈希函数,二是如何解决冲突。
               2)哈希函数的构造方法
               常用的哈希函数的构造方法有直接定址法、数字分析法、平方取中法、折叠法、随机数法和除留余数法等。
               3)处理冲突的方法
               解决冲突就是为出现冲突的关键字找到另一个"空"的哈希地址。常见的冲突处理方法有:开放地址法、链地址法、再哈希法等。
 
       折半查找
        折半查找也称为二分查找,其基本思想是:先令查找表中间位置记录的关键字和给定值比较,若相等,则查找成功;若不等,则缩小范围,直至新的查找区间中间位置记录的关键字等于给定值或者查找区间没有元素时(表明查找不成功)为止。
        设查找表的元素存储在一维数组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 /
 
第43题    在手机中做本题