线性表

1. 顺序表

2. 链表（物理上离散，逻辑上连续）

   
   

链表的类别

• 单链表
• 循环链表

• 双链表

  
  

链表的操作

顺序表与链表的比较

栈

• FILO
• 栈顶、栈底

队列

• FIFO
• 队尾、对头（非循环）

• 循环队列（head、tail指针）（rear=(rear+1）mod m)

  
  
• 答案：C

树和二叉树

树概念

• 结点的度、树的度
• 叶子、分支、内部、父、子、兄弟结点
• 树除了叶子结点全部为分支结点，包括根结点
• 除了根结点和叶子结点，都为内部结点
• 层次
  *结点数=结点度总和+1（n=k+1）

树的遍历

• 前序遍历
• 后序遍历
• 层次遍历

二叉树概念

• 二叉树不是特殊的树
• 满二叉树、完全二叉树、非完全二叉树
• 完全二叉树：n-1层是满树，按左到右连续排列
• 第i层最多2^（i-1）个结点
• 深度为k的最多有(2^k)-1个结点

• 叶子结点数为n0，度为2结点数为n2，则n0=n2+1

  
  
• 答案：B

二叉树遍历

• 前序
• 中序
• 后序

• 层次

  
  

树与二叉树的转换

• 正向：孩子结点作左子树结点，兄弟结点作右子树
• 二叉树中序遍历和转换的树的后序遍历对应
• 二叉树前序遍历和转换的树的前序遍历一样

图

图的概念

• 线性表和树是图的特殊形式
• 有限非空顶点集合+顶点对表示的边集合
• G=(V,E)，树可以空树，图不能没有顶点
• 无向图与有向图（A,B）<A,B>≠<B,A>
• 顶点的度，有向图顶点的度=入度+出度
• 子图
• 完全图（每对顶点都有 一条/两条 边/有向边 相连）
• 路径和回路、简单回路
• 连通图和连通分量
• 网络（图+权值）
• 图的存储：邻接矩阵（1有边、0无边）

图的遍历

• 深度优先（类似树的先根遍历）
• 广度优先（类似树的层次遍历）

最小生成树

• 普里姆算法
• 克鲁斯卡尔算法

拓扑排序

• AOV网络
• 拓朴排序

关键路径

• AOE网络（AOV+权表示时间）（关键路径是最长路径）

排序算法

• 插入排序（直接插入、希尔）
• 选择排序（简单选择、堆）
• 交换排序（冒泡、快速）
• 归并排序
• 基数排序

哈希表

• 概念
• 函数构造方法
• 处理冲突方法
• 哈希表的查找

查找算法

• 顺序查找
• 二分查找
• 分块查找