数据结构考核知识点.doc

BuildDate：2011-12-01第1章概论 逻辑结构和存储结构。 时间复杂度（大O表示法）、空间复杂度。第2章线性表 线性表的存储结构：顺序表、单链表、循环链表、双向链表。各自的优缺点；如何选择相应的表结构 掌握顺序表上的操作：插入、删除、查找、初始化。算法实现、性能分析。 掌握单链表上实现的建表、查找、插入和删除（逆转、合并）等基本算法，时间复杂度分析。 掌握双链表的定义，及其插入、删除、查找等算法实现。 应用顺序表、链表解决实际问题。 程序实现：链表的基本操作（查找、插入、删除）、其他操作（逆转、合并等等）。双链表的插入、删除。第3章 栈和队列 栈和队列的概念、特点、存储结构。 掌握顺序栈和链栈上实现的进栈、退栈、栈空等算法实现。 掌握顺序循环队列和链队列上实现的入队、出队等算法实现。利用 头指针front和尾指针rear计算对列中元素个数，队列空的判断，队列初始化、进队列、出队列算法实现（三种情况的循环队列：设头尾指针、只设头指针和计数器、只设尾指针和计数器） 应用栈、队列解决实际问题 程序实现：栈、队列的程序实现。第4章 串和数组 串的定义、概念、存储结构。 掌握顺序串的基本运算：赋值运算、复制、求串长度、判断串相等、串连接、求子串、查找子串位置。 简单串匹配（串匹配的概念、模式串、子串的概念） KMP算法的Next数组（程序不要求） 掌握多维数组的顺序存储结构及地址计算方式。 掌握对称、三角等特殊矩阵的压缩存储、地址计算。 理解稀疏矩阵的三元组表表示方法及有关算法（加、转置）。 程序实现：串定位的BF算法、第5章 递归和广义表 理解递归的定义。 掌握递归模型的设计，转换成递归函数。 理解广义表的概念、表示方式、存储方式。 了解广义表的常见运算，掌握求长度、深度、表头和表尾。（程序不做要求） 程序实现：简单的递归程序的实现第6章 树和二叉树 掌握二叉树的定义、性质，了解相应的证明方法。（判断一棵树是否为二叉树、计算某一层的最大（小）结点数、计算某棵二叉树的总的结点数、根据高度计算某完全二叉树的最多节点总数等。） 掌握二叉树的两种存储方法、特点及适用范围。n 顺序存储（根据树形给出顺序存储结构、或者给出顺序存储结构画出该二叉树）n 二叉链存储结构（创建二叉树、求二叉树高度、求二叉树结点个数、求二叉树叶子结点个数等算法实现） 掌握二叉树的基本运算、三种遍历算法。 掌握给定二叉树的三种遍历表示、给定两种遍历构造出二叉树。 掌握树和森林与二叉树之间的转换。 二叉树的线索化和线索二叉树的遍历算法实现。（给出一棵二叉树，要求给出中序线索化二叉树；线索化二叉树的遍历） 哈夫曼树的创建、哈夫曼编码以及WPL计算。 掌握算法实现程序：三种遍历（前序、中序、后序）和中序线索二叉树的遍历算法第7章 图 了解图的常用术语及含义。 掌握邻接矩阵和邻接表这两种存储结构的特点及适用范围。 给出一个图，能够给出邻接矩阵、邻接表；能给出DFS、BFS序列。 能够利用图的两种遍历设计算法解决简单的应用问题。 掌握求最小生成树 Prim和Kruskal算法的基本思想和过程。 掌握单源最短路径的Dijkstra算法的基本思想和过程。 掌握AOV网、拓扑排序的基本思想和过程。 掌握AOE网、有向图关键路径查找过程。 掌握算法实现程序：DFS深度优先搜索和BFS广度优先搜索第8章 查找 ASL平均查找长度计算、时间复杂度、空间复杂度。 掌握顺序查找、二分查找的过程和查找效率分析。 理解二分查找对存储结构及关键字的要求。 理解分块查找的过程。 掌握二叉排序树的插入、删除、建树和查找过程及时间性能。 理解AVL树、平衡因子的概念。 AVL 树调整方法，建立、查找的过程。 掌握散列表、散列函数、散列地址和装填因子等有关概念。了解几种常用的散列函数构造方法。 掌握采用线性探测法和拉链法解决冲突时，散列表的建表方法、查找过程以及ASL的计算。（成功、不成功两种情况） 掌握算法实现程序：顺序查找、二分查找第9章 排序 掌握排序方法分类、算法时间复杂度（平均/最好/最坏）、辅助空间、“稳定”与否。 掌握直接插入排序、希尔排序的过程。 掌握直接选择排序、堆排序算法