《北航数据结构课件复习》由会员分享，可在线阅读，更多相关《北航数据结构课件复习（18页珍藏版）》请在金锄头文库上搜索。
1、,第一章 绪论,第二章 线性表,第三章 数组,第四章 堆栈和队列,第五章 广义表,第六章 串,第七章 树与二叉树,第八章 图,第九章 文件和查找,第十章 内排序,1. 概念题,2. 算法题,3. 综合题(问题求解题),(1).是非判断题,(2).简答题,(3).填空题,(4).单项选择题,(1).算法设计题,(2).算法填空题,1. 第一章 绪论,（1）关于结构, 结构的种类, 结构之间的关系,（2）关于算法, 算法的定义, 算法的描述, SPARKS语言, 算法分析的基本概念,2. 第二章 线性表,（1）关于线性表, 什么是线性关系？, 什么是线性表？, 线性表的基本操作有哪些？,（2）线性
2、表的顺序存储结构, 线性表的顺序存储结构的构造原理, 插入、删除操作对应的算法的设计, 线性表的顺序存储结构的特点,（3）线性表的链式存储结构, 线性表的链式存储结构的构造原理, 线性链表的插入、删除算法, 循环链表的插入、删除算法, 双向链表的插入、删除算法,3. 第三章 数组,（1）数组的基本概念,（2）数组的存储结构, 一维数组, 二维数组,（3）特殊矩阵的压缩存储, 对称矩阵, 对角矩阵(三对角矩阵), 稀疏矩阵的三元组方法、十字链表方法,（4）数组的应用,4. 第四章 堆栈和队列,（1）堆栈和队列的基本概念, 定义, 基本操作, 特殊性,（2）堆栈和队列的存储结构, 顺序存储结构,
3、链式存储结构,插入、删除操作对应的算法设计,插入、删除操作对应的算法设计,（3）堆栈和队列在解决实际问题中的应用,5. 第五章 广义表,（1）广义表的基本概念,（2）广义表的存储结构,（3）多元多项式的广义表存储方法,6. 第六章 串,（1）串的基本概念, 串的定义, 几个名词术语、概念,（2）串的基本操作,（3）串的存储结构, 顺序存储结构 - 紧缩格式、非紧缩格式, 链式存储结构,（4）几个基本算法,7. 第七章 树与二叉树,（1）树的基本概念, 树的定义, 树的逻辑特点, 名词术语, 树的逻辑表示方法,（2）树的存储方法, 多重链表、三重链表,（3）二叉树, 二叉树的基本概念(定义),
4、两种特殊形态的二叉树（满二叉树、完全二叉树）,（4）二叉树的基本性质（五个）,（5）二叉树的存储结构, 顺序存储结构, 链式存储结构 - 二叉链表,（6）二叉树的遍历, 遍历的基本概念,几种常见的遍历方法 前序遍历、中序遍历、后序遍历、按层次遍历, 遍历的非递归算法的设计, 由遍历序列恢复二叉树,（7）二叉排序树, 二叉排序树的定义, 建立二叉排序树的逐点插入方法, 二叉排序树的删除（原则）, 二叉排序树的查找,8. 第八章 图,（1）图的基本概念, 图的定义, 图的分类,名词术语 - 顶点的度、路径、子图、图的连通、生成树,（2）图的存储方法, 邻接矩阵存储方法, 邻接表存储方法,（3）图的
5、遍历, 图的遍历的基本概念, 深度优先遍历方法, 广度优先遍历方法,（4）最小生成树, 最小生成树的概念, 求解最小生成树的方法,（5）最短路径, 路径长度的定义, 最短路径的概念, 求解最短路径的方法,（6）AOV网与拓扑排序,（7）AOE网与关键路径, AOE网与关键路径的定义, 求解关键路径的方法,9. 第九章 文件及其查找,（1）文件的基本概念, 名词术语, 文件的逻辑结构和物理结构, 文件的基本操作,查找、插入、删除、修改、排序,（2）顺序文件, 顺序文件的分类, 连续顺序文件的顺序查找方法, 排序连续顺序文件的折半查找方法, 连接顺序文件的查找方法,（3）索引文件, 索引文件的概念 - 组成、索引表的特点, 稠密索引文件与非稠密索引分块文件的查找,（4）B树与B+树, B 树和 B+ 树的定义, B 树和 B+ 树的查找,（5）杂凑文件（Hash文件), 杂凑文件的基本概念,杂凑函数、杂凑文件、哈希冲突, 杂凑函数的构造方法, 哈希冲突的处理方法,开放地址法、再哈希法、链地址法,10. 第十章 内排序,（1）排序的基本概念, 排序的定义, 排序的功能, 排序的分类 - 内排序、外排序,（2）插入排序法,（3）选择排序法,（4）泡排序法,（5）谢尔(Shell)排序法,（6）快速 排序法,（7）堆积排序法,（8）二路归并排序法,
