算法与数据结构各章学习要点

1、算法与数据结构各章学习要点第1章概论一、学习要点：1、 熟练掌握各基本概念：数据、数据元素、数据项、数据结构、逻辑结构、存储结构、顺序存储结构、链式存储结构的定义。2、 掌握逻辑结构、存储结构的基本分类。3、 掌握算法的基本特性4、 理解算法效率的评价指标（时间复杂度、空间复杂度），能够评价简单算法的时间复杂度。二、作业练习：1、P10：一、二、三。第2章线性表一、学习要点：1、 掌握线性结构的特点、线性表的定义，理解线性表的基本术语：表长、空表、直接前驱、直接后继。2、 掌握顺序表的定义和特点，掌握顺序表中第i 个元素的地址计算公式3、 能够用 C 语言描述顺序表的类型并熟练应用，熟练掌握顺

2、序表的基本运算及实现：初始化、插入、删除、按值查找。4、 掌握链表的定义，理解：头指针、头结点、首元结点(第一结点 )的区别。5、 能够用 C 语言描述单链表结点类型并熟练应用，熟练掌握单链表的基本运算及实现：建立（头部建立、尾部建立）、求表长、查找（按序号查找、按值查找）、插入、删除。6、 理解循环链表、双向链表的算法实现特点。7、 掌握顺序表和链表存储结构的比较。8、 能够运用顺序表和单链表、循环单链表进行算法设计。二、作业练习 ：P41：一、二、三（1， 3， 4）第3章 栈与队列一、学习要点：1、 掌握栈的定义和特点，掌握栈的基本术语：栈顶、栈底、空栈。2、 能够根据栈的特点，描述同一

3、输入下的不同输出顺序。3、 能够用 C 语言描述顺序栈结点类型并熟练应用，掌握顺序栈的基本运算及实现：置空栈、判栈空、入栈、出栈、取栈顶元素。4、 掌握队列的定义和特点，掌握队列的基本术语：队头、队尾，掌握循环队列的目的。5、 理解循环队列区分队满和队空的方法，能够根据解决的方法设计数据结构，并实现循环队列的基本运算：置空队、入队、出队、判队空、判队满、求队列的长度。6、 能够利用栈和队列结构设计算法。二、作业练习：P64 一、二、三（ 2， 3）第4章 串一、学习要点：1、 掌握串的定义和特点，掌握串的基本术语：串长、子串、主串、子串的位置、串相等、空串和空格串。2、 掌握串模式匹配的定义，

4、掌握KMP 模式匹配的思想及next 函数值的计算方法。二、作业练习：P77:一、二、三第 5 章 数组和广义表1、 掌握数组逻辑结构的特点以及通常做的操作。2、 掌握二维数组存储地址计算。3、 能够进行能够特殊矩阵压缩存储地址计算公式的推导。4、 掌握稀疏矩阵的三元组表示。5、 掌握广义表以及表头、表尾的定义。二、作业练习：P89:一、二、三（ 1,2）第 6 章 树和二叉树一、学习要点：1、 掌握二叉树的定义，熟悉二叉树的五种基本形态。2、 掌握树、二叉树的基本术语：结点的度、树的度、叶结点、分枝结点、孩子、兄弟、双亲、深度、层次、满二叉树、完全二叉树。3、 掌握二叉树的性质以及相应的证明

5、方法。4、 掌握二叉树的顺序存储、二叉链表存储，能够绘制示意图。5、 能够熟练运用二叉链表的存储结构，掌握二叉树递归遍历算法，能够给出遍历结果。6、 能够利用二叉树的先序遍历进行二叉树的各种算法设计。7、 掌握由前序序列（或后序序列）和中序序列可唯一确定该二叉树的方法。8、 掌握由前序序列构造二叉树的方法，能够进行算法实现。9、 掌握线索、线索二叉树的定义，并能将二叉树转换为线索二叉树（示意图）。10、掌握哈夫曼树的定义，能够根据给定的权值图示哈夫曼树构造过程并进行哈夫曼编码，并计算WPL 。11、掌握树的定义，能够图示树的双亲表示法、孩子链表法、双亲孩子表示法、孩子兄弟表示法。12、能够进行

6、树和二叉树的转换、森林和二叉树的转换。二、作业 练习：P121：一、二、三、四（17 ）第7章图一、学习要点：1、 掌握图的基本概念：有向图、无向图、网络、连通分量、生成树、度、出度、入度、完全图、子图。2、 能够图示图的存储结构：邻接矩阵、邻接表、逆邻接表。3、 掌握图的深度优先遍历和广度优先遍历的定义，能够根据图或邻接表写出遍历顺序。4、 掌握两种最小生成树生成最小生成树思想和过程示意图。5、 理解 Dijkstra 单源最短路径算法思想。6、 能够根据给定有向无环图进行拓扑排序、寻找关键路径。二、作业练习：P156：一、二、三、四（14）第8章查找一、学习要点：1. 掌握查找表的数据结构

7、的特点：逻辑结构、核心运算。2.掌握平均查找长度ASL 的定义，能够计算各种查找算法的ASL 值。3. 能够实现顺序查找算法，理解“监视哨”的作用。4. 掌握三种静态查找算法的比较。5.能够用递归和非递归方法实现折半查找，能够绘制折半查找的判定树，并根据判定树计算ASL 值。6. 理解分块查找的思想，掌握分块方法。7. 掌握二叉排序树的定义，能够根据给定的序列图示二叉排序树的创建过程。8. 掌握二叉排序树的查找、插入的递归和非递归算法。9. 掌握平衡二叉树、平衡因子的定义，能够判断失衡的原因。10. 掌握散列表的常用构造方法和冲突处理方法，能够根据给定哈希函数和冲突处理方法构造哈希表。二、作业练习：P196：一、二、三、四（1,2,4,5）、五（ 1）第9章排序一、学习要点：1、 掌握排序方法稳定和不稳定的定义，堆、大顶堆、小顶堆的定义。2、 掌握 5 种内部排序插入排序、交换排序、选择排序、2路归并、基数排序的基本思想。3、 掌握各种排序