408计算机综合中的数据结构，占试卷分值为45分。因此，备考2020考研408计算机综合考研者，需要认真对待数据结构中的重难点知识。接下来，北京文都考研网小编分享出“408数据结构考点知识:查找”，供考生参考。
2020考研408数据结构考点知识:查找
点睛点:折半查找法及性能分析、分块查找、字符串模式匹配、B 树的定义及其基本操作、散列表的查找及性能分析。
答题要点:顺序查找法比较简单,折半查找比较重要,需掌握折半查找的适用条件、折半查找算法和查找过程、判定树的构造、查找长度分析等。B 树和 B+树是本章难点,一般不要求掌握算法,对于 B 树要求能够执行插入、删除和查找操作,对于 B+树,仅需了解基本概念和性质即可。散列查找也比较重要,掌握常用的算法函数和冲突解决方法，容易出综合题。
【例】顺序存储的某线性表共有 123 个元素，按分块查找的要求等分为 3 块。若对索引表采用顺序查找方法来确定子块，且在确定的子块中也采用顺序查找方法，则在等概率的情况下，分块查找成功的平均查找长度为( )
A.21 B.23 C.41 D.62
参考答案:B
【例】从 19 个元素中查找其中任意一个元素,如果最多进行 4 次元素之间的比较,则采用的查找方法只能是( )
A.分块查找 B.折半查找 C.散列查找 D.二叉排序树
参考答案:C
【例】假定在一个散列表中每个元素占用 s 个存储单元(不包括链指针),但需要使用指针的时候,每一个指针要占用 1 个存储单元.如果在表中已经有 n 个元素,散列表总共有 m 个散列位置,包括空元素所占据的位置.
(1)如果采用开地址法解决冲突，散列表需要多少存储单元，原因是什么?
(2)如果采用链地址法解决冲突，所有记录存放在若干分离的结点中，每个结点和指针成员需要 s+1 个存储单元。那么 n 个结点总共需要多少个存储单元。
(3)如果采用链地址法解决冲突，散列表本身需要多少个存储单元?这里假定指向溢出链的指针只需要一个存储单元。
参考答案：
(1)m*s 个存储单元
(2)n 个结点需要 n*(s+1)个存储单元
(3)m*1=m 个存储字
以上是北京文都考研网给出的“2020考研408数据结构考点知识:查找”，希望对参加408计算机考研考生，在复习该部分上面有很大的帮助!祝考研路上顺利!
推荐阅读：
![京网文[2014]2116-316号](https://bj.wendu.com/imgs/jingicp.jpg){kind=link}
