计算机考研中的数据结构占统考综合试卷分值为45分。因此,参加2020计算机考研学子一定要重点复习该部分。接下来,北京文都考研网为助力计算机考生一臂之力,特意整理了计算机数据结构知识:查找,供考生参考。
2020考研计算机数据结构知识:查找
知识点:折半查找法及性能分析、分块查找、字符串模式匹配、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考研计算机数据结构知识:查找”,希望对正在复习计算机数据机构的考生有所帮助!祝2020考研考出好成绩,加油!
推荐阅读: