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

《算法与数据结构各章学习要点》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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、掌握栈的定义和特点，掌握栈的基本术语：

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

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

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

6、编码，并计算WPL。11、掌握树的定义，能够图示树的双亲表示法、孩子链表法、双亲孩子表示法、孩子兄弟表示法。12、能够进行树和二叉树的转换、森林和二叉树的转换。二、作业练习：P121：一、二、三、四（1~7）第7章图一、学习要点：1、掌握图的基本概念：有向图、无向图、网络、连通分量、生成树、度、出度、入度、完全图、子图。2、能够图示图的存储结构：邻接矩阵、邻接表、逆邻接表。3、掌握图的深度优先遍历和广度优先遍历的定义，能够根据图或邻接表写出遍历顺序。4、掌握两种最小生成树生成最小生成树思想和过程示意图。5、理解Dijkstra单源最短路径算法思想

7、。31、能够根据给定有向无环图进行拓扑排序、寻找关键路径。二、作业练习：P156：一、二、三、四（1~4）第8章查找一、学习要点：1.掌握查找表的数据结构的特点：逻辑结构、核心运算。2.掌握平均查找长度ASL的定义，能够计算各种查找算法的ASL值。3.能够实现顺序查找算法，理解“监视哨”的作用。4.掌握三种静态查找算法的比较。5.能够用递归和非递归方法实现折半查找，能够绘制折半查找的判定树，并根据判定树计算ASL值。6.理解分块查找的思想，掌握分块方法。7.掌握二叉排序树的定义，能够根据给定的序列图示二叉排序树的创建过程。8.掌握二叉排序树的查找

8、、插入的递归和非递归算法。9.掌握平衡二叉树、平衡因子的定义，能够判断失衡的原因。10.掌握散列表的常用构造方法和冲突处理方法，能够根据