以下是我在备考期间的一些笔记，算是一些小总结吧，如果你408准备得还可以了，可以看看下面的总结，我认为可能会给你一些启发的。这篇是关于数据结构的一些知识点，但是由于数据结构的总体难度算是偏小的了，所以备考过程中的笔记算是比较少的了。幕布笔记：

数据结构

1.散列表计算ASL

一般线性表和顺序线性表在查找成功的情况下平均查找长度是一样的，失败是不一样的(具体思考)

注意散列表的ASL计算，成功时查找除去的是个数，失败是除去散列函数中的质数，而不是散列表的长度

考点一：散列表查找失败+线性探查

这里注意失败时，求平均长度除以的是7，而插入时，因为20和6会有冲突，此时20的计算是H=(H(key)+d)%m，这里的m取的是散列表的长度（一定要理解为什么要%m，不要不知道就跳过去了‼️，这里是选项探测法的要点）

考点二：查找失败时，分母注意是给定散列函数的质数

考点三：注意理解查找失败的情况，不将质数之外的数算进去，也就是计算0～6失败的情况。而查找成功是按照关键字个数来计算的，需要将题目中的七个都计算进去(基本上理解这个，ALS也就没有太大的问题了)

考点四：装填因子是由关键字长度/表长，有时候会给你装填因子和关键字长度，让你计算表长或者构造散列函数，注意散列函数的是取质数的

2.树和图的度的区别

1、一定要注意两者的度的定义是不一样的，树的度是指节点的个数，无向图的度是边数✖️2，如果将树转化为图的话，那么树的度就是有向图的出度。

2、这里也要注意最小生成树的度/边的问题，最小生成树虽然有“树”在里面，但是本质上是图（极小连通图），所以最小生成树度的算法应该是图的度的算法

3.平衡二叉树

1、平衡二叉树，深度为h，最少结点数为Nh=Nh-1+Nh-2+1，N0=0，N1=1，N2=2

4.时间复杂度

时间复杂度在408中考得频率挺高，去年考得一题难度很大。这种题目就是注意频率了，下图类型②就是去年考的知识点，时间复杂度为O(N)