大观

• 线性结构
  • 线性表 $\sim$ 链表 头插尾插
  • 队列
  • 栈
  • 数组
    • 特殊数组
  • 字符串
    • KMP
    • next 数组 := 失配后开始位置
      • next[0] = -1
      • next[i] = pi[i - 1]
• 非线性结构
  • 树
    • 高度分析
    • 线索二叉树
    • 森林
  • 哈希表
  • 图论大观
    • 图概念
    • 图遍历
    • 图应用
      • 最小生成树
      • 拓扑排序
      • 最短路
      • 关键路径
• 查找
  • 线性查找
    • 顺序查找
    • 二分查找
    • 分块查找
  • 非线性查找
    • 树形查找 = 二叉排序树 + 平衡二叉树
    • 哈希查找/ 散列查找
• 内部排序
  • 交换排序
  • 插入排序
  • 选择排序
  • 内部排序性质

考前必背

1. 线性表
   1. 特殊数组
2. 树
   1. 二叉树度 $n_{0}=n_{2}+1$
   2. 树高分析 $\log_{m}((m-1)n+1)\leq h\leq n - m + 1$
   3. 先序遍历/树种类 = 卡特兰数 $\frac{1}{n+1}C_{2n}^{n}$
   4. 哈夫曼树
   5. 线索二叉树 := 孩子优先，空孩子补前驱后继
   6. 森林转二叉树 := 左儿子右兄弟
3. 图论大观
   1. 图论时间复杂度 !图论时间复杂度
4. 查找
   1. 查找效率
5. 内部排序
   1. 内部排序性质 !内部排序性质