《数据结构复习要点总结》由会员分享，可在线阅读，更多相关《数据结构复习要点总结（4页珍藏版）》请在装配图网上搜索。
1、关于机考猜测Stack, Queue, List:迷宫，日历，链表深度优先搜索，广度优先搜索拓扑排序贪心排序与查找树的前序，中序，后序遍历最小生成树基础复习要点Stack, Queue:基本性质及其基本操作；实现方式（链式和顺序）List：指针的基本操作（插入，删除）String :串的定义与概念，及其基本操作Sorting： Insertion sort; Selection sort; Quick sort;（次要点：Merge sort;Shell sort; Heap sort）Searching：二分法查找Tree： 基本概念： children, parent, siblings,
2、 ancestors （祖先）,descendants （后继） ,branch, leaf,height, depth（ level） of a vertex前序，中序，后序遍历（递归以及非递归实现）；AVL Tree；Huffman Tree:又称最优树，是一类带权路劲最短的树；（英文课本159）Hash：给你一个Hash函数，你是否能建立起Hash table ?是否会用open addressing 或 chaining 来解决冲突？（复习课本与课件中的例题）Graph：存储方式（邻接表，邻接矩阵）遍历（ DFS/BFS）拓扑排序贪心算法最小生成树关于二叉树：二叉树（binary tr
3、ees）的概念，特殊二叉树，边数，结点数和度数等； 二叉树的链式存储结构，连续存储结构； 二叉树的遍历（递归和非递归算法）及其实现;二叉排序树（二叉查找树， binary search trees） 的概念； 二叉排序树的搜索、插入、删除；树排序（treesort）及其性能； 平衡二叉排序树（AVL trees）的概念和构造方法；Huffman 树的概念、 Huffman 树的构造和 Huffman 的编码算法及其实现 树、森林和二叉树之间的转换。关于查找：查找问题的一般叙述，如何度量基于比较的查找算法的工作量； 顺序查找如何实现，其特点是什么，复杂度是什么。 二分查找的实现，二分查找的时间复
4、杂度是什么； 理解比较树的概念，对比较树的分析能得到哪些信息，如高度表示什么，内、外路径长度各 表示什么；为什么说二分查找是基于比较的查找算法中最优的；掌握递归方法：递归有哪些要素，使用递归应该注意什么问题 递归在计算机中是如何实现的；递归树的概念； 递归算法的时间效率和空间效率的估算； 递归的消除；理解回溯法，分治法和贪心法。 理解尾部递归的特点以及使用的场景表的查找：如何使用表格进行信息检索;索引函数(index functions)和访问数组(access arrays);矩阵的存储：行优先序列和列优先序列； 设计散列函数的一般原则和方法;什么是碰撞(collisions),解决碰撞的常
5、见方法； 什么是拉链法(chaining);什么是开地址法(open addressing);线性探查法(linear probing)及其特点；平方探查法(quadratic probing)及其特点；关于排序：掌握下列排序方法，包括排序算法，稳定性，时间性能和其他特点：简单插入排序，简单选 择，归并排序，快速排序和堆排序；理解排序性能分析方法。 能够对每种排序的过程很熟悉，并且联系到实际的问题情境。 对给定的数据，选择最优的排序算法。排序方法最坏时间 复杂度平均时间 复杂度辅助空间稳定性直接插入排序0(n2)0(n2)O(1)稳定Shell排序0(ni5)O(ni-25)O(1)不稳定直接选择排序0(n2)0(n2)O(1)不稳定快速排序0(n2)O(nlog n)O(logn)不稳定归并排序O(nlogn)O(nlogn)O(logn)稳定堆排序O(nlog n)O(nlog n)O(1)不稳定关于图：图的概念 图的两种表示法: 邻接矩阵与邻接表 图的遍历算法及其实现BFS 和 DFS 的快速实现 拓扑排序及其实现 求最短路径的算法及其实现 求最小生成树的算法及其实现
数据结构复习要点总结
