数据结构

树

• 存储结构、遍历算法
• 树、森林、二叉树转换相关
• 二叉树
  • 遍历
  • 线索化
• 应用
  • 哈夫曼树
    • 计算WPL 【注意 WPL 需要路径长度*权重，不乘是错的！】

图

• 应用
  • 最小生成树
    • 第一性：无环、总权最小、包含所有节点
    • 实现
      • 克鲁斯卡尔：加边
      • prim：加点
  • 最短路径
    • 迪杰斯特拉，思想是贪心，找新加入节点到已知节点的最短路径【求 dist 数组】
  • 拓扑排序
    • 实现
    • 时间复杂度 O(V+E)
  • 关键路径
    • 问题：活动余量、关键路径、最早开始、最晚结束时间，以及关键路径概念
      • 增加、减少关键活动对工期的影响
    • 求解
      • 从左往写最早开始时间
      • 从右往左写每每个节点的最晚开始时间
      • 活动的余量 = 该活动的结束节点的最晚开始时间 - 开始节点的最早开始时间 - 该活动的持续时长
      • 余量为 0 的活动为关键路径【或者直接找图里最长的路径】
  • 用 DAG 表示表达式，求节点个数 #2018
• 定义相关
  • 数据结构
    • 邻接表、邻接矩阵、邻接多重表、十字链表
  • 算法
    • DFS
    • BFS

查找

• 数组查找
• 树形查找
  • B-树和B+树
  • 平衡二叉树
• 散列表查找
  • 计算查找成功/失败的平均查找长度 成功时除以表内元素个数，失败时除以 mod n 的 n 大小 #2018 #1022

排序

• 内部排序
  • 堆排序、建堆过程 多次考到 #2020
  • 几种排序的比较
    • 不稳定的排序：选择、快速、希尔、堆排序
  • 各种排序算法的细节
    • 桶排序
    • LSD 基数排序
    • 选择 vs 插入， 直接插入 vs 简单选择 #2022 #2020
    • 归并排序过程 #2024 #2022 #2019

顺序表

• 数组压缩，求元素下标