全国计算机等级考试四级含金量,2017年全国计算机等级考试四级复习纲要：检索

七、检索

1.顺序检索

检索又称为查找。顺序检索是将待查找的关键码值与线性表中个结点的关键码值逐一比较，直到找到所需的记录，检索成功;或者在表中找不到所需记录而检索失败。顺序检索不要求线性表事先排序。设线性表有n个元素，则最多检索次数为n，最少检索次数为1。

2.二分法检索

二分法检索要求线性表结点按关键排序且以顺序方式存储。在查找时，首先与表的中间位置上结点的关键值比较，若相等则检索成功;否则根据比较结果确定下一步在表的前半部或后半部中继续进行。二分法检索的效率较主动，设线性表有n个元素，则最多的检索次数为大于log 2 n的最小整数，最少的检索次数为1。

3.分块检索

分块检索把线性表分成若干块，块内结点不必有序，但块与块之间必须有序，即每一块中各结点的关键值必须大于（或小于，与此类推）前一块关键值。为加快查找，还要建立一个索引表，表中给出每一块的关键值和指向块内第一个结点位置的指针。分块检索分两步进行，先查索引表，确定要找的记录在哪一块;然后再在相应的块中检索。分块检索适合于线性表很大，数据又是动态变化的情况。在查索引表时，可采用顺序法或二分法;在块内查找所求记录时，采用顺序法。由于分块而缩小了查找范围，从而加快检索速。

4.散列表检索

根据关键值，就可以迅速找到该记录所对应的存储位置，这就是建立在散列函数基础上的散列检索。设记录的关键值为k，则该记录的存储位置可用散列函数H来计算H=H（k）。常用来产生的散列函数的方法是除余法，即取H（k）=k mod p设散列表长度为n，取p为小于n的素数。一般说来，关键码值的集合比散列表存储位的数目大得多，这正是体现散列表的优势所在，但同时带来了冲突问题，即不同的关键值经散列函数计算，可能得到相同的存储位置。一个好的散列函数应该使冲突的可能性尽量小。最常用的解决冲突的方法是线性探测法，就是在发生冲突时，从H（k）以后的位置逐一探测，直至找到一个空位置，将新记录插入;在检索时，如果H（k）中不是所需关键值的记录，也是从H（k）往下逐一搜索，直到找到所需关键值或查找失败为止。应注意查找次序是:H（k），H（k）+1，H（k）+2，…n-1，0，1，2，…，H（k）-1即在n-1以后，又从0开始，因为在位置上是循环的。双重散列技术是对线性探测法的改进。它使用两个散列函数H1和H2。对关键值k，计算H1（k），求得0到n-1之间的一个散列地址;若在这个地址上冲突，下一个被探测的地址为（H1（k）+H2（k））mod n，关于选择H2的方法在此不做讨论。

本文来源：https://www.wddqw.com/7toO.html