线性表
- 顺序表
-
链表（物理上离散，逻辑上连续）
链表的类别
- 单链表
- 循环链表
-
双链表
链表的操作
顺序表与链表的比较
栈
- 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+权表示时间）（关键路径是最长路径）
排序算法
- 插入排序（直接插入、希尔）
- 选择排序（简单选择、堆）
- 交换排序（冒泡、快速）
- 归并排序
- 基数排序
哈希表
- 概念
- 函数构造方法
- 处理冲突方法
- 哈希表的查找
查找算法
- 顺序查找
- 二分查找
- 分块查找
