北大数据结构与算法期末复习提要

1、2014年北大数据结构与算法B期末复习提要以本文最后的内容为复习重点，尤其是标出部分为重中之重。考试时如果涉及到本大纲没有列出的内容，那么试卷中会给出足够的定义和性质，也可以举手问监考老师。第1章 概论 一. 重要概念1. 数据三要素（逻辑结构、存储结构、算法） 2. 抽象数据结构（逻辑+运算） 3. 存储是逻辑结构到物理地址的映射，主要方法有顺序、链接、散列、索引等 4. 算法分析(时间代价、空间代价) 二. 方法1. 二元组逻辑结构，即有向图、无向图（Vi, Vj）结点对，注意边的方向 2. 算法的代价估算，特别是核心算法段的运算次数 3. 算法渐进分析方法，主要掌握大O表示法（不要求掌握

2、大、大表示法） 4. 数据结构的选择和评价（针对具体的应用实例，能运用本学期所学的数据结构，特别是图模型构造和评价合适的数据结构，并能实现核心的算法） 第2章 线性表一. 概念1. 线性表 2. 单链表 3. 双链表 4. 循环表二. 方法1. 顺序表上实现的运算 2.链表上实现的运算(指针操作的正确性) 3. 顺序表和链表的比较，各自的优缺点以及适应的应用场景第3章 栈与队列一. 概念1. 栈 2. 队列 3. 循环队列二. 方法 1. 栈的性质，用栈来生成序列，栈的实现 2. 队列的性质，用队列生成序列 3. 循环队列的实现4. 栈的灵活应用，例如表达式求值 (中缀表达式转后缀表达式的算法

3、、后缀表达式求值算法)第4章 字符串一. 概念1. 串（由0个或多个字符/符号的顺序排列所组成的复合数据结构，线性表的特殊形式） 2. 模式匹配（在目标 T 中寻找一个给定的模式P的过程）二. 方法1. 串的存储2. 串的重要运算（返回指定位置字串substr、求子串find、拼接“+”操作等）3.理解模式匹配基本含义，不要求掌握KMP算法第5章 二叉树一. 概念1. 二叉树 2.二叉树的递归深度优先遍历、宽度优先遍历 3. 二叉搜索树 4. 堆 5. Huffman树、Huffman编码 二. 方法1二叉树的链式存储（1）二叉链表（2）带父指针的三重链表2. 二叉树的顺序存储、完全二叉树的顺

4、序存储 3. 二叉树的深度优先遍历，要求能用递归解决二叉树应用问题4. 二叉树的广度优先遍历及其应用 5. 二叉检索树（也称二叉搜索树、二叉排序树、BST）的插入与删除（都是先查找到合适位置，再进行相应操作） 6. 构造Huffman树，利用Huffman树进行编码、解码 7. 堆的建立与维护过程三、算法1. 上述“二、方法”中的基本算法2. 不考察非递归的二叉树深度优先遍历第6章 树一. 概念1. 树、森林 2. 树的先根遍历、后根遍历、层次遍历 二. 方法 1. 森林与二叉树相互转换 (森林表示为等价二叉链结构，左孩子是第一个子结点，右孩子是在森林中的下一个兄弟)2森林的链式存储 (1)

5、转换为相应的二叉树，用二叉链表示（左子-右兄）(3) 子结点表表示法 3. 森林的深度优先遍历（递归），可能结合应用4. 森林的层次遍历(用队列)，可能结合应用 5. 森林的顺序存储（不必死记各种顺序存储方法，要了解原理。其本质是按照遍历的性质，把顺序存储的森林信息反构造成森林。在内存中往往用等价的二叉链来表示）三、算法1. 上述“二、方法”中的基本算法2. 不考察父指针方法，不考Union-Find并查集，不考K叉树第7章 图一. 概念 1. 图的深度遍历 2. 图的宽度遍历 3. 图的生成树、生成树林、最小生成树 二. 图的方法 1. 图的存储方法 （1） 相邻矩阵 （2） 邻接表(结点表

6、 - 边表) 2. 图的遍历（1） 深度优先DFS （2） 宽度优先BFS（2） 注意用mark数组避免遇回路造成死循环，也能提供对非连同分量的继续访问；给每个顶点先标记为未访问，遍历过程中遇到未访问点才能深入访问该结点，而且立即把该结点则标记为已经访问。 3. 图的生成树与最小生成树 （1） 从某一点出发，按深度优先或宽度优先遍历的生成树 （2） 最小生成树 Prim算法 Kruskal算法(避圈法) 4. 最短路径 Dijkstra算法 算法的关键都在求Min的部分三. 算法 1. 要求掌握深搜DFS、宽搜BFS、最短路 Dijkstra、最小生成树Prim、拓扑排序等图的相关算法 2.不考Kruskal算法的实现，不考拓扑排序，不考关键路径，不Floyd算法第8章 内排序二. 方法及算法 1. 重点排序算法：直接插入法、Shell排序、快速排序、堆排序、基数排序、归并排序 2. 算法分析 （1）基于比较次数和移位次数分析最好、最坏情况分析，包括时间和空间 直接插入法、二分法插入排序、冒泡排序、直接选择、快速排序、基数排序、归并排序 （2） 记住各种排序方法的平均时间 3. 各种排序方法的局部修改和混合应用第10章 检索一. 概念 1. 平均检索长度 2. 二分法检索 3. 散列表、同义词、碰撞、