搜索
2014年北大《数据结构与算法B》期末复习提要以本文最后的内容为复习重点，尤其是★标出部分为重中之重。考试时如果涉及到本大纲没有列出的内容，那么试卷中会给出足够的定义和性质，也可以举手问监考老师。第1章概论一.重要概念1.数据三要素（逻辑结构、存储结构、算法）2.抽象数据结构（逻辑+运算）3.存储是逻辑结构到物理地址的映射，主要方法有顺序、链接、散列、索引等★4.算法分析(时间代价、空间代价)二.方法1.二元组逻辑结构，即有向图Vi,Vj、无向图（Vi,Vj）结点对，注意边的方向★2.算法的代价估算，特别是核心算法段的运算次数★3.算法渐进分析方法，主要掌握大O表示法（不要求掌握大Ω、大Θ表示法）★4.数据结构的选择和评价（针对具体的应用实例，能运用本学期所学的数据结构，特别是图模型构造和评价合适的数据结构，并能实现核心的算法）第2章线性表一.概念1.线性表2.单链表3.双链表4.循环表二.方法1.顺序表上实现的运算★2.链表上实现的运算(指针操作的正确性)3.顺序表和链表的比较，各自的优缺点以及适应的应用场景第3章栈与队列一.概念1.栈2.队列3.循环队列二.方法★1.栈的性质，用栈来生成序列，栈的实现2.队列的性质，用队列生成序列★3.循环队列的实现4.栈的灵活应用，例如表达式求值(中缀表达式转后缀表达式的算法、后缀表达式求值算法)第4章字符串一.概念1.串（由0个或多个字符/符号的顺序排列所组成的复合数据结构，线性表的特殊形式）2.模式匹配（在目标T中寻找一个给定的模式P的过程）二.方法1.串的存储2.串的重要运算（返回指定位置字串substr、求子串find、拼接“+”操作等）3.理解模式匹配基本含义，不要求掌握KMP算法第5章二叉树一.概念1.二叉树2.二叉树的递归深度优先遍历、宽度优先遍历3.二叉搜索树4.堆5.Huffman树、Huffman编码二.方法1．二叉树的链式存储（1）二叉链表（2）带父指针的三重链表2.二叉树的顺序存储、完全二叉树的顺序存储★3.二叉树的深度优先遍历，要求能用递归解决二叉树应用问题4.二叉树的广度优先遍历及其应用★5.二叉检索树（也称二叉搜索树、二叉排序树、BST）的插入与删除（都是先查找到合适位置，再进行相应操作）★6.构造Huffman树，利用Huffman树进行编码、解码★7.堆的建立与维护过程三、算法1.上述“二、方法”中的基本算法2.不考察非递归的二叉树深度优先遍历第6章树一.概念1.树、森林2.树的先根遍历、后根遍历、层次遍历二.方法★1.森林与二叉树相互转换(森林表示为等价二叉链结构，左孩子是第一个子结点，右孩子是在森林中的下一个兄弟)2．森林的链式存储★(1)转换为相应的二叉树，用二叉链表示（左子-右兄）(3)子结点表表示法★3.森林的深度优先遍历（递归），可能结合应用4.森林的层次遍历(用队列)，可能结合应用★5.森林的顺序存储（不必死记各种顺序存储方法，要了解原理。其本质是按照遍历的性质，把顺序存储的森林信息反构造成森林。在内存中往往用等价的二叉链来表示）三、算法1.上述“二、方法”中的基本算法2.不考察父指针方法，不考Union-Find并查集，不考K叉树第7章图一.概念1.图的深度遍历2.图的宽度遍历3.图的生成树、生成树林、最小生成树★二.图的方法★1.图的存储方法（1）相邻矩阵（2）邻接表(结点表--边表)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.散列表、同义词、碰撞、堆积二.方法1.二分法检索的判定树、查找某个结点的比较次数2.散列表:1)散列函数的选择(除余法、折叠法)2)冲突处理方法(分离同义词子表、线性探测、双散列函数)★三.不考察具体的散列算法设计和实现