数据结构要点.doc

第1章 绪论概念：数据结构、数据、数据元素、数据对象、物理结构、数据类型、抽象数据类型、时间复杂度、空间复杂度（所谓概念，不是说考名词解释，而是必须要理解这些名词）数据结构的基本结构存储结构的分类算法的特性算法设计的要求时间复杂度和空间复杂度的计算（其实常见的课本上都有，不用计算，记住更好）练习题目：1、3、8、12、14、16、17第2章 线性表线性结构的特点顺序表：l 顺序表的特点l 顺序表中元素地址的计算l 顺序表的插入和删除操作的实现（代码）链表：l 链表的基本结构与元素l 头结点的作用l 链表的插入和删除的实现（代码）l 静态链表的概念l 循环链表的特点l 双向链表的特点l 双向链表中插入和删除操作的实现（代码）练习题目：1、2、3、4、5、6、7、8、9、11、19第3章 栈和队列概念：栈、栈顶、栈底、队头、队尾栈的特点顺序栈的入栈和出栈操作（代码）队列的特点循环队列的入队和出队操作（代码）循环队列队空和队满的判断练习题目：2、3、4、10、11、12、19、28第4章 串概念：串、串长、空串、子串、主串、串相等、串的定长顺序存储表示串的堆分配存储表示及操作（赋值，求长度，比较，连接，求子串）（代码）串的模式匹配算法（算法4.5）（代码）练习题目：1、3、4、5、6、8、17、25第5章 数组和广义表数组的存储主序行为主序和列为主序时存储地址的计算对称矩阵存储地址的计算稀疏矩阵的存储形式三元组顺序表的特点，num和cpot向量的作用三元组顺序表转置操作的实现（代码）广义表的概念：原子、子表、表头、表尾GetHead( )和GetTail( )操作练习题目：1、2、7、8、10、19、21第6章 树和二叉树概念：树、子树、结点、度、叶子、分支结点、孩子、双亲、子孙、祖先、兄弟、层次、深度、森林、二叉树、满二叉树、完全二叉树、带权路径长度、哈夫曼树、前缀编码树的表示方法p120二叉树的性质二叉树的存储结构：顺序存储、链式存储结构二叉树的遍历的实现（递归方式）（代码）给定二叉树，写出其先序、中序和后序遍历结果给定二叉树的前序+中序或中序+后序遍历结果，要求画出二叉树线索二叉树的概念，特点及结点结构树的存储结构：（1）双亲表示法；（2）孩子表示法；（3）孩子兄弟表示法 各自的结构及特点森林的两种遍历方法哈夫曼编码的计算（类似于例6-2）哈夫曼树构造（代码）练习题目：1、2、3、4、5、6、12、13、16、26、27、28、29第7章 图概念：顶点、弧、弧头、弧尾、有向图、无向图、完全图、稀疏图、稠密图、子图、出度、入度、度、路径、环、简单路径、连通、连通图、连通分量、生成树图的存储结构：数组表示法；邻接表（要求能给出图，画出存储结构。或者反之）图的遍历：DFS和BFS（原理，基本过程）最小生成树（两种方法，要求给出图，会计算）拓扑排序（要求给出图，会计算）最短路径（要求给出图，会计算）练习题目：1、4、5、7、11、22第8章（不考）第9章 查找概念：查找表、静态查找表、动态查找表、关键字、查找、平均查找长度、二叉判定树、二叉排序树、平衡二叉树、哈希表顺序查找的过程顺序查找的性能分析折半查找的过程（包括代码）索引顺序表的查找过程二叉排序树的构造过程（要求能给出序列，画出对应的二叉排序树）二叉排序树的插入（代码）哈希函数的构造方法（要求会对给定关键字及给定函数，能计算出地址）冲突处理方法（要求会计算，对给定序列，给定哈希函数和冲突处理方法，能画出存储结果，包括开放定址法和链地址法）练习题目：1、2、3、9、19、21、31第10章 排序概念：排序、稳定排序、内部排序、排序的分类排序的基本操作排序方法：l 直接插入排序（基本思想、代码、给定序列写出每趟的结果）l 折半插入排序（基本思想、代码、给定序列写出每趟的结果）l 希尔排序（基本思想、代码、给定序列写出每趟的结果）l 起泡排序（基本思想、代码、给定序列写出每趟的结果）l 快速排序（基本思想、代码、给定序列写出每趟的结果）l 简单选择排序（基本思想）l 堆排序（基本思想）l 归并排序（基本思想，给定序列写出