1 题型总结

1.1 线性表（6年）

2010（另设数组移动/逆置数组）
2011（排序/归并合并数组/数组指针后移/两个数组的折半查找）
2013（双重枚举/排序/空间换时间/技巧——两两抵消）
2016（排序/类快排思想排序）
2018（暴力枚举/排序后扫描数组/空间换时间——hash）
2020（三重for循环/二重循环+指针后移/一重循环+两折半查找/技巧——贪心+三指针后移）

1.1.1 常用思想

• 暴力解：
  • 枚举所有情况；
  • 无序数组快速排序
• 优化：
  • 折半查找（一个、有序、数组）
  • 数组指针后移（多个、线性表、有序）
  • 空间换时间（hash）
  • 贪心（每次选择最有利的）

1.2 链表（4年）

2009（双层循环枚举/递归遍历查询/数组保存遍历/找规律/双指针法）
2012（双重循环枚举/链表转数组，数组保存结点地址双指针法）
2015（枚举/空间换时间——hash）
2019（一半尾插法/多次逆置)）

1.2.1 常用思想

• 暴力解：
  • 枚举；
  • 链表保存为数组
• 优化：
  • 前后指针（两个指针距离相同）
  • 快慢指针（判断环，快指针一定会追上慢指针）
  • 头插法（逆置）
  • 空间换时间

1.3 树（3年）

2014（WPL计算——前序遍历）
2017（中缀表达式转换——中序遍历）
2022（中序遍历搜查搜索数/二叉搜索树的定义）

1.3.1 常用思想

• 二叉树
  • 前序、中序、后续
• 树和森林
  • 先根、后根、层序
• 数转二叉树
• 二叉排序树
  • 判断是否是平衡二叉树、红黑树

1.4 图（2年）

2021（统计每个顶点的度（出度和入度和））
2023（统计各顶点的入度）

1.4.1 常用思想

• 遍历图统计顶点的度

2 具体内容（含题目和解法）