文艺复兴
这波啊，这波是老题新做。
听说现在数据结构是王涛老师在讲，所以请各位对模拟卷以及复习资料要用辩证的眼光看待，事物是对立统一的，要在对立中发现相同点。
资源包含：
18扛把子卢总模拟卷详解，18CTF金牌打手弛崽提供的复习总结，18老混子V模拟卷详解(有些题做错了，标准答案以卢总为准)，上市公司*见愁老贺的考研真题精选。
部分参考如下：
计算机查找复习
本章节假设：元素的关键字是唯一的
1.查找的分类
(1)动态查找，静态查找
(2)内查找，外查找
平均查找长度ASL的计算
分为和
顺序查找
折半查找
前提：原序列是有序的，这样才能一分为2
用判定树或比较树来等价，查找某元素成功的比较次数等于该结点所在的层数i
索引储存结构和分块查找
将连续s个元素的最大值作为索引表的关键字，第一个元素作为“地址”
1.索引表是有序的（分块之间是有序的）
2.分块内部不一定是有序的ASL=ASL(索引表)+ASL(分块)
假设表长n，b块，每块s个元素，
（可替换为折半）
二叉排序树
左儿子小，右儿子大
插入结点：
1.找到位置后直接插入结点
删除结点：P
1.删除叶子结点：直接删除
2.删除只有左(右)结点的结点：将起左（右）结点替换原结点位置
3.删除有左右结点的结点：左子树中最右下的结点替换原结点，再将该结点删除
平衡二叉树
平衡因子：左子树-右子树
平衡状态：
平衡因子
=1
平衡二叉树是在加入结点的过程中，一旦出现不平衡情况，立刻做出调整，使其恢复平衡
调节方法：P
插入某以结点，沿着逆路径写出平衡因子，发现第一个不平衡的结点与它前两个路径上的结点构成一个“调整树”。只要将第一个不平衡的点调节后，其他点都会回到平衡状态
RR，LL方法类似
RL，LR方法类似
见P例题8.8
B树，B+树，红黑树没有涉及到题目...大家自己看看
哈希表的查找
基本概念
通过映射函数H(x)，将关键字映射到内存单元的地址
同义词：具有相同关键字，不同地址，“同义词冲突”
装填因子：a=n/m
哈希表构造法
1.直接定值法h(k)=k+c（线性函数适用于关键字基本连续，否则存在大量浪费）
2.除留余数法h(k)=kmodp,p=m（p取素数效果最好，取奇数比取偶数好）
3.数字分析法例如：身份证的18位的身份证中只有其中几个数字是比较随机的，不需要把所有的数字用来计算
哈希冲突解决办法
1.开放地址法
(1)线性探查
(2)平方探查
(3)缺点：
①装填因子不能过大
②不能直接删除，只能标记
2.拉链法
(1)此时哈希表中存放的是链头指针，而不是真正的数据
(2)优点：
①操作简单
②无堆积，平均查找长度较短
③空间是动态申请的
④装填因子可以大于等于1，对于大规模数据，指针域的大小可忽略
⑤可以直接删除元素
(3)缺点：
①当装填因子过大的时候不如开放地址法则
模拟卷
选择题(15)：
选择(79)：D
序列中:
填空(8)：
------------------------------------------------------------------
预览时标签不可点收录于话题#个上一篇下一篇