队列

    • (r-f+n)%n

哈希

  • 聚集现象
    • 线性探测容易产生“聚集现象”。 当表中的第i、i+1、i+2的位置上已经存储某些关键字，则下一次哈希地址为i、i+1、i+2、i+3的关键字都将企图填入到i+3的位置上，这种多个哈希地址不同的关键字争夺同一个后继哈希地址的现象称为“聚集”
    • 拉链法不会产生聚集现象

树

  • 森林和二叉树的转化

    • 左孩子右兄弟

  • 线索二叉树

    • 答案为B

  • 再check一下AVL树的转法

图

  • 图DFS算法复杂度
    • 邻接矩阵：$O(\vert V\vert ^2)$
    • 邻接表：$O(\vert V\vert+\vert E\vert)$
  • 图BFS算法复杂度
    • 邻接矩阵：$O(\vert V\vert^2)$
    • 邻接表：$O(\vert V\vert+\vert E\vert)$
  • DAG图
    • 有向无环图
  • 拓扑排序
    • 方法是重复寻找一个入度为0的顶点，将该顶点从图中删除，即放进一个队列里存着，这个队列的顺序就是最后的拓扑排序
  • 找有向图中的环
    • 对结点进行拓扑排序，最后图中入度为1的结点构成至少一个有向环

排序

  • 插入排序

    • 遇到比自己大的就往前排，直到前面的比自己小为止

  • 折半插入排序：查找时使用二分查找

    • 无论前面序列情况如何，插入第i个记录时都要二分查找$log_2 \lfloor i \rfloor + 1$次
    • 当记录的初始排列为正序或接近正序时，直接插入排序比折半插入排序执行的关键字比较次数要少

  • 选择排序

    • 每次从未排序序列中选最值，放到未排序序列首

  • 快速排序

    • 最好情况：每次选的pivot都能刚好把序列划分成均匀的两部分
    • 最坏情况：初始序列有序（或逆序）

  • 堆排序

    • 初始化堆：check每个非端点结点