考试重点

  1. 时间复杂度
  2. 存储结构
  3. 逻辑结构
  4. 栈
  5. 循环队列
  6. 二维数组
  7. 稀疏矩阵的存储方法
  8. 特殊矩阵
  9. 字符串
  10. 树的遍历
  11. 穿线二叉树
  12. 哈希函数
  13. 排序方法
  14. 顺序表的增删改查
  15. 字符串的链式存储
  16. 二叉树的链式存储
  17. 图的邻接矩阵和邻接表的存储方法
  18. 图的深度和广度优先遍历
  19. 二叉排序树
  20. 二分检索
  21. 哈夫曼编码
  22. 最小生成树的Prim和Kruskal算法
  23. 直接选择排序、直接插入排序、冒泡排序、快速排序、堆排序等
  24. 通过二叉树的前中后序遍历画出二叉树
  25. 单链表的增删改查

基本概念

数据结构

  1. 数据的逻辑结构
  2. 数据的存储结构（顺序存储、链式存储、索引存储、散列存储）
  3. 数据的运算集合（定义在逻辑结构之上，具体运算依赖于数据的存储结构）

算法的五个特征

  1. 有穷性
  2. 确定性
  3. 输入
  4. 输出
  5. 可行性

程序可以不具备有穷性

算法的时空复杂度

顺序表

栈

  1. 括号匹配
  2. 表达式求值

后缀表达式转写

队列

循环队列

单链表

  1. 带头节点的单链表
  2. 双链表

链式串

  1. 创建
  2. 插入
  3. 删除
  4. 连接
  5. 求子串

特殊矩阵

  1. 对称矩阵的压缩存储（默认存对角线以下）
  2. 三角矩阵的压缩存储（上下三角 和对称矩阵一样）
  3. 带状矩阵的压缩存储

稀疏矩阵

  1. 三元组表示法（实现、转置）
  2. 十字链表法（查找）

树的遍历

  1. 前序
  2. 中序
  3. 后序
  4. 层序

括号 层号 表示

图

  1. 邻接矩阵
  2. 邻接表
  3. DFS
  4. BFS
  5. Prim
  6. Kruskal
  7. Dijkstra

检索

  1. 二分
  2. 堆
  3. Huffman树

排序

  1. 直接插入
  2. 直接选择
  3. 堆排
  4. 冒泡
  5. 快速
  6. 归并