408 | 【2016年】计算机统考真题 自用回顾知识点整理

数据结构

T7：拓扑排序 —— 基于有向无环图（DAG图）

• 有向无环图（DAG图）
• AOV网：DAG图表示一个工程，顶点表示活动，有向边表示前必须先于后（仅表示顶点的先后关系），则称为顶点表示活动的网络
• 拓扑排序：对有向无环图的顶点的排序，若存在一条A到B的路径，则B出现在A后
• 拓扑排序算法：
  • ①选择一个没有前驱的结点并输出
  • ②删除以它为起点的有向边
  • ③重复12直到当前的AOV网为空或不存在无前驱的结点为止（存在环）
    • 
• 邻接表 时间复杂度O(|V|+|E|) 邻接矩阵O(|V|^2)
• DFS也可实现拓扑排序

T10：B树及其基本操作、B+树的基本概念（RBT）

• B树（多路平衡排序树）
  • B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。
  • 一棵m阶B树或