北大数据结构与算法课件13期末考试复习课

期末考试复习课目标：4.0！优异成绩＝良好心态×(扎实的基础知识+良好的学习复习方法+考场上的正常发挥)知识点（图）一.概念★二.方法及算法★1.图的存储方法：（1）相邻矩阵（2）邻接表(结点表--边表)2.图的周游：（1）深度优先（2）宽度优先3.图的生成树与最小生成树（1）从某一点出发，按深度优先或宽度优先周游的生成树（2）最小生成树①Prim算法②Kruskal算法(避圈法)4.拓扑排序:对于给定图，找出若干个或所有拓扑序列任何无环的有向图，都可以拓扑排序。5.最短路径Dijkstra算法、Floyd算法(属于动态规划法)★两个算法的关键都在求Min的部分知识点（内排序）二.方法及算法1.重点排序算法：直接插入法、★Shell排序、★快速排序、★基数排序、归并排序2.算法分析（1）基于比较次数和移位次数分析最好、最坏的时间、空间直接插入法、二分法插入排序、起泡排序、直接选择、快速排序、基数排序、归并排序（2）记住各种排序方法的平均时间3.各种排序方法的局部修改和混合应用知识点（文件管理和外排序、检索）方法及算法1.★置换选择排序2.★多路归并(败者树，最佳归并树，多路归并的读盘和写盘次数)（不考第8章8.2.2节关于读盘时间的计算）一.概念1.平均检索长度2.二分检索★3.散列表、同义词、碰撞、堆积二.方法1.二分法检索的判定树、查找某个结点的比较次数2.散列表:1)散列函数的选择(除余法、平方取中法、折叠法)2)冲突处理方法(分离同义词子表、线性探测、双散列函数)★三.散列算法（查找、插入、删除，对墓碑的处理）不考9.2集合知识点（索引技术）一.概念1.顺序文件2.散列文件3.倒排文件4.静态索引结构5.动态索引结构(B树)二.方法（不考算法）★1.B树、B+树的插入与删除(注意保持性质，特别是等高；以及子结点和关键码个数的上下限制)2.B树/B+树的读盘和写盘次数分析3.B树/B+树的效率分析B树中关键码没有重复，父结点中的关键码是其子结点的分界；B+中最底层是关键码的一个全集，往根的方向一层层复写。不考10.2.1多分树，不考10.2.2ISAM和10.4.3VSAM。复习根据考试提纲制定计划教材？讲义？作业以前的试题？理解与记忆（关系到考试时解题的时间）我的方法：把自己觉得看过但不好记的知识点记到一张纸上，每次复习前都过一遍，考试前多看几次动笔去写代码跟同学讨论考试心态：我能！从以往的考试特别是期中考试得到了什么？考试时间分配解题顺序及答题版面组织个人习惯别漏答重点与细节阅卷者的角度：所有分数都对应到有限的考查重点