【必看】数据结构保研复习知识点总结｜2021计算机软工保研｜夏令营预推免面试经验_保研推免 数据结构考点

文章目录

• 数据结构复习
• • 重点
  • 绪论
  • • • 基本概念
      • 数据类型：
      • 数据结构三要素：逻辑结构、存储结构和数据的运算
      • • 逻辑结构
        • 存储/物理结构：数据结构在计算机内的表示（映像）
        • 数据的运算
    • 算法和算法评价
    • • 算法五个特征（必须有的）
      • • 好算法的目标：正确、可用、可读、效率、健壮性
      • 算法复杂度
  • 线性表
  • • • 定义和基本操作
      • 线性表顺序表示
      • 线性表的链表表示
  • 栈和队列
  • • 栈
    • • 栈的定义
      • 顺序栈
      • 顺序栈的基本运算
      • • 双端队列
        • 数组和特殊矩阵的压缩存储
        • 两个栈共享一个内存区域
      • 链栈
      • • 链栈的栈顶和栈底
    • 队列
    • • 队列的顺序存储
      • • 循环队列
      • 链式队列
    • 栈和队列的应用
    • • 括号匹配
      • 表达式求值
      • 递归
      • 栈和队列的相互转换
      • 队列在计算机中的应用
    • 特殊矩阵的压缩存储
    • • 数组的定义和存储
      • 矩阵的压缩存储
      • • 1.对称矩阵
        • 2.三角矩阵
        • 3.三对角矩阵
      • 稀疏矩阵
  • 串
  • • • 串的模式匹配
      • • 1.Brute-Force算法 暴力模式匹配 O(mn)
        • 2.模式匹配的KMP算法 O(n+m) 主要优点是主串不回溯
        • 3.正则表达式与模式匹配有关
  • 树和二叉树
  • • • 二叉树-代码题见机试葵花宝典
      • 深度优先遍历
      • 广度优先遍历
      • • 图上遍历的时间空间复杂度（DFS BFS都惊人地一样）
      • 二叉排序树/二叉查找树 BST
      • 平衡二叉树
      • 哈夫曼树与哈夫曼编码
      • 堆的应用与堆的实现
  • 图
  • • • 图的有关概念
      • 图的表示
      • 图的遍历
      • 最小生成树：
      • 最短路径：
      • 拓扑排序
      • 关键路径
      • • AOV网和AOE网
      • 并查集
    • 查找
    • • 顺序查找和折半查找
      • 散列表
    • • 二叉排序树（偏向概念）
      • 平衡二叉树（偏向概念）
      • B树和B+树
      • 排序
      • • 排序的一些概念：
        • 两种交换排序：
        • 插入排序 稳定的
        • 选择排序(两种选择排序：简单选择和堆排序都是不稳定的)
        • 基数排序 稳定的 O(d*(n+r)) r表示队列数量 n表示元素数量 d是d趟分配和收集
        • 归并排序 基于分治
      • 内部排序算法的比较
      • 外部排序