2019考研计算机数据结构复习重点：查找

考研网

《数据结构(C语言版)》复习重点在二、三、六、七、九、十章，考试内容两大类：概念，算法，自从计算机专业课统考以后，专业课考试题型分为2类，一类选择题，一类综合应用题。接下来是新东方在线整理的2019考研计算机数据结构复习重点查找。
    　　1. 查找表：是由同一类型的数据元素(或记录)构成的集合。
    　　2. 关键字：是数据元素(或记录)中某个数据项的值，用它可以标识(识别)一个数据元素(或记录)。
    　　3. 静态查找表：查询某个特定的数据元素是否在查找表中，检索某个特定的数据元素的各种属性。
    1)
顺序查找法：从表中最后一个记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录;反之若直至第一个记录，其关键字和给定值比较都不相等，则表明表中没有所查记录，查找不成功。
    其存储结构要求：以顺序表或线性链表表示的静态查找表。
    其平均查找长度：假设每个记录的查找概率相等，即Pi=1/n，则在等概率情况下顺序查找的平均查找长度为，ASL=(n+1)/2。
    2) 折半查找法(二分查找法)：先确定待查记录所在的范围(区间)，然后逐步缩小范围直到找到或找不到该记录为止。
    其存储结构要求：以有序表表示的静态查找表。
    其平均查找长度：假设表中每个记录的查找概率相等(Pi=1/n)，则查找成功时折半查找的平均查找长度为，ASL=(n+1)/n*log2(n+1)-1。
    3) 索引顺序表查找法(分块查找法)：先确定待查记录所在的块(子表)，然后在块中顺序查找。
    其存储结构要求：以索引顺序表表示的静态查找表。
    其平均查找长度：将长度为n的表均匀地分成b块，每块含有s个记录，即b=[n/s];又假设表中每个记录的查找概率相等，则每块查找概率为1/b，块中每个记录的查找概率为1/s，若用顺序查找确定所在块，则分块查找的平均查找长度为，ASL=(n/s+s)/2+1;若用折半查找确定所在块，则分块查找的平均查找长度为，ASL≈log2(n/s+1)+s/2。