数据结构复习要点总结

关于机考猜测Stack,Queue,List:迷宫，日历，链表深度优先搜索，广度优先搜索拓扑排序贪心排序与查找树的前序，中序，后序遍历最小生成树基础复习要点Stack，Queue:基本性质及其基本操作；实现方式（链式和顺序）List：指针的基本操作（插入，删除）String:串的定义与概念，及其基本操作Sorting：Insertionsort;Selectionsort;Quicksort;（次要点：Mergesort;Shellsort;Heapsort）Searching：二分法查找Tree:基本概念：children,parent,siblings,ancestors（祖先）,descendants（后继）,branch,leaf,height,depth（level）ofavertex前序，中序，后序遍历（递归以及非递归实现）；AVLTree；HuffmanTree:又称最优树，是一类带权路劲最短的树；（英文课本159）Hash：给你一个Hash函数，你是否能建立起Hashtable?是否会用openaddressing或chaining来解决冲突？（复习课本与课件中的例题）Graph：存储方式（邻接表，邻接矩阵）遍历（DFS/BFS）拓扑排序贪心算法最小生成树关于二叉树：二叉树（binarytrees）的概念，特殊二叉树，边数，结点数和度数等；二叉树的链式存储结构，连续存储结构；二叉树的遍历（递归和非递归算法）及其实现；二叉排序树（二叉查找树，binarysearchtrees）的概念；二叉排序树的搜索、插入、删除；树排序（treesort）及其性能；平衡二叉排序树（AVLtrees）的概念和构造方法；Huffman树的概念、Huffman树的构造和Huffman的编码算法及其实现;树、森林和二叉树之间的转换。关于查找:查找问题的一般叙述，如何度量基于比较的查找算法的工作量；顺序查找如何实现，其特点是什么，复杂度是什么。二分查找的实现，二分查找的时间复杂度是什么；理解比较树的概念，对比较树的分析能得到哪些信息，如高度表示什么，内、外路径长度各表示什么；为什么说二分查找是基于比较的查找算法中最优的；关于递归:掌握递归方法：递归有哪些要素，使用递归应该注意什么问题;递归在计算机中是如何实现的；递归树的概念；递归算法的时间效率和空间效率的估算；递归的消除；理解回溯法，分治法和贪心法。理解尾部递归的特点以及使用的场景表的查找:如何使用表格进行信息检索；索引函数(indexfunctions)和访问数组(accessarrays);矩阵的存储：行优先序列和列优先序列；设计散列函数的一般原则和方法；什么是碰撞(collisions),解决碰撞的常见方法；什么是拉链法(chaining);什么是开地址法(openaddressing);线性探查法(linearprobing)及其特点；平方探查法(quadraticprobing)及其特点；关于排序:掌握下列排序方法，包括排序算法，稳定性，时间性能和其他特点：简单插入排序，简单选择，归并排序，快速排序和堆排序；理解排序性能分析方法。能够对每种排序的过程很熟悉，并且联系到实际的问题情境。对给定的数据，选择最优的排序算法。排序方法最坏时间复杂度平均时间复杂度辅助空间稳定性直接插入排序O(n2)O(n2)O(1)稳定Shell排序O(ni・25)O(ni-25)O(1)不稳定直接选择排序O(n2)O(n2)O(1)不稳定快速排序O(n2)O(nlogn)O(logn)不稳定归并排序O(nlogn)O(nlogn)O(logn)稳定堆排序O(nlogn)O(nlogn)O(1)不稳