复习考试王位春.ppt

复习考试王位春,目标：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章节关于读盘时间的计算）一.概念 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+中最底层是关键码的一个全集，往根的方向一层层复写。不考多分树，不考和。,复习,根据考试提纲制定计划教材？讲义？作业以前的试题？理解与记忆（关系到考试时解题的时间）我的方法：把自己觉得看过但不好记的知识点记到一张纸上，每次复习前都过一遍，考试前多看几次动笔去写代码跟同学讨论,考试,心态：我能！从以往的考试特别是期中考试得到了什么？考试时间分配解题顺序及答题版面组织个人习惯别漏答重点与细节阅卷者的角度：所有分数都对应到有限的考查重点,THANKS!,