工程硕士专业课复习提纲

工程硕士专业课复习提纲工程硕士专业课复习提纲 第一章第一章 绪论绪论 抽象数据类型定义 数据结构研究内容 数据结构定义 数据定义抽象数据类型定义 数据结构研究内容 数据结构定义 数据定义 第二章第二章 算法及时间复杂性算法及时间复杂性 时间复杂性定义 常用时间复杂性比较 简单程序的时间复杂性判时间复杂性定义 常用时间复杂性比较 简单程序的时间复杂性判 断断 算法 算法 Algorithm 是对特定问题求解步骤的一种描述 它是指令 是对特定问题求解步骤的一种描述 它是指令 规则 的有限序列 其中每一条指令表示一个或多个操作 规则 的有限序列 其中每一条指令表示一个或多个操作 算法的特征 算法的特征 有穷性 有穷性 确定性 确定性 能行性 能行性 输入 输入 输出输出 算法描述 算法描述 自然语言 自然语言 程序设计语言 程序设计语言 类语言 类语言 常见的时间复杂性及其比较常见的时间复杂性及其比较 1 n n n n n n2 n3 y 1 y 1 y y 1 时间复杂性为时间复杂性为 O n s 0 f n 1 T2 n O f n O 1 常量阶常量阶 for i 1 i n i x s x f n 3n 1 T1 n O f n O n 线性阶线性阶 for i 1 i n i for j 1 j n j x s x f n 3n2 2n 1 T3 n O f n O n2 平方阶平方阶 for i 1 i n i for j 1 j n j c i j 0 for k 1 k n k c i j a i k b k j f n 2n3 3n2 2n 1 T4 n O f n O n3 立方阶立方阶 第三章第三章 线性表线性表 基本概念基本概念 线性表 栈 队列 循形链表 双向链表 单链表 广义表线性表 栈 队列 循形链表 双向链表 单链表 广义表 存贮结构及在计算机内的表示 存贮结构及在计算机内的表示 顺序存贮 数组 顺序存贮 数组 链式存贮 链式存贮 基本操作 基本操作 插入 删除 查找 栈的压入 弹出操作 队列的循环数组表示 插入 删除 查找 栈的压入 弹出操作 队列的循环数组表示 队列的假溢出队列的假溢出 栈 队列的特殊性及出栈序列栈 队列的特殊性及出栈序列 单链表的表头作用 空链表的表示单链表的表头作用 空链表的表示 数组的地址计算 二维 三角矩阵 数组的地址计算 二维 三角矩阵 稀疏矩阵的存贮方法 稀疏矩阵的存贮方法 串的定义崆串的定义崆 串与空白串的区别串与空白串的区别 广义表的长度 深度广义表的长度 深度 第四章第四章 树树 基本概念 基本概念 树 二元树 森林树 二元树 森林 完全二元树 满二元树 哈夫曼完全二元树 满二元树 哈夫曼 树树 存贮结构 二元树的四种结构 顺序 左右链 游标 线索存贮结构 二元树的四种结构 顺序 左右链 游标 线索 树的三种 父链法 数组 树的三种 父链法 数组 左右链 邻接表 左右链 邻接表 遍历算法 递归与非递归 前序 中序 后序 按层 线索二元遍历算法 递归与非递归 前序 中序 后序 按层 线索二元 树求前导与后继树求前导与后继 二元树的性质 二元树的性质 5 个 个 森林与二元树之间的转换 森林与二元树之间的转换 哈夫曼树的构造方法及哈夫曼编码 哈夫曼树的构造方法及哈夫曼编码 弟五章弟五章 图及有关算法图及有关算法 基本概念 基本概念 图 最小生成树 关键路径 拓扑分类 连通分量图 最小生成树 关键路径 拓扑分类 连通分量 存贮结构 存贮结构 邻接矩阵 邻接表邻接矩阵 邻接表 搜索算法 先深 先广 最小生成树 拓扑分类 关键路径 单源搜索算法 先深 先广 最小生成树 拓扑分类 关键路径 单源 最短路径最短路径 出度 入度 先深序列 先广序列出度 入度 先深序列 先广序列 第六章第六章 查找查找 掌握线性查找 折半查找 分块查找 二元查找树 散列法的定义 掌握线性查找 折半查找 分块查找 二元查找树 散列法的定义 算法思想及时间复杂性算法思想及时间复杂性 散列冲突的处理 散列函数 散列冲突的处理 散列函数 第七章第七章 分类分类 掌握简单分类 快速分类 归并分类 堆分类的定义 算法思想 掌握简单分类 快速分类 归并分类 堆分类的定义 算法思想 内存空间及时间复杂性 内存空间及时间复杂性 第八章第八章 外部分类及文件外部分类及文件 掌握外部分类的定义 磁盘文件的归并分类技术