《算法与数据结构》复习要点

第一章绪论数据结构的定义：数据的逻辑结构：线性结构（线性表、栈、队列、串）和非线性结构（数据的物理结构：顺序存储、链式存储、索引存储、散列存储；常用的数据结构的运算：插入、删除、查找、修改、排序；时间复杂度的计算；第二章线性表1、顺序存储和链式存储的定义，优缺点，及其适用场景；2、单链表和双向链表的基本操作如何实现，诸如插入、删除等；3带头结点和无头结点的单链表L4、邻接表是一种结合了顺序存储与链式存储的存储格式，在那些结构中被使用第三章栈和队列栈：1、栈的相关操作：入栈和出栈；2、给定入栈序列，写出所有可能的出栈序列；3、共享栈的基本概念和操作；队列：1、顺序队列的“假溢出”是怎样产生的？2、循环队列：长度的计算；队满的表达式；队空的表达式；1、串的存储方式

第四章串2、朴素匹配算法和KMP算法的核心思想：两种算法比较次数的计算第五章多维数组和广义表多维数组：1、二维数组存储地址的计算（行优先存储和列优先存储）第一个元素的下标；第一个元素的存储地址；每个元素占几个单元；2、特殊矩阵的压缩存储（对称矩阵、三角矩阵、对角矩阵）如何进行压缩存储；压缩存储后，a （二维数组）和sa[k]（顺序表）之间ij的对应关系；也就是说如何通过i和j算出k。稀疏矩阵的两种存储方式：三元组表、十字链表；在转置矩阵中的下标广义表：1、广义表的定义2、广义表的取表头和取表尾运算L(a,b)head(L)atail(L)(b)第六章树5条性质：1（所有二叉树2（所有二叉树3（所有二叉树4（完全二叉树5（完全二叉树二叉树的遍历：1、先序遍历、中序遍历、后序遍历；2二叉树的还原：二叉树中结点和深度的计算（递归实现：1、叶子结点的计算；2、总结点的计算；3线索二叉树：1、结点的结构体定义；2结构体的五个成员变量（尤其是线索标志域、箭头的起始和终止位置；3（程序找错题二叉树和树的转换、二叉树和森林的转换：弟节点。哈夫曼树1、哈夫曼树的定义2、依据数据序列构造哈夫曼树、各个数据的对应码值、带权路径长度。第七章图图的相关定义：1、有向图和无向图；2、N个节点的有向图和无向图最多有多少条边、最少有多少条边；3、极大连通分量和极小连通分量；图的存储：1、邻接表：结构体定义；2、邻接矩阵：结构体定义；3图的遍历：1、广度优先遍历（队列）2（栈最小生成树：1、普里姆算法2、克鲁斯卡尔算法AOE网关键路径的计算（顶点表示事件、边表示活动）1、事件的最早发生时间（有多条入边时怎样计算、最迟发生时间（条出边时怎样计算；2（该条边的始点事件的最早发生时间（条边的终点时间的最迟发生时间—边的权重；3、活动的时间余量（余量为0的活动即为关键活动）最短路径的计算（迪杰斯特拉算法）第八章排序各种排序算法的具体实现过程，如何统计比较次数：插入排序：直接插入排序（传统的插入排序交换排序：冒泡排序、快速排序；选择排序：直接选择排序、堆排序（初始堆如何建立、应从下标为/2处开始的性质；归并排序：建议：对比学习：比如直接插入和直接选择、希尔排序和归并排序，相同点在哪里，不同点在哪里？第九章查找顺序查找：折半查找（二分查找分块查找：树表的查找二叉排序树的查找：平衡二叉排序树L树散列表的查找常见的哈希函数冲突处理方法：开放地址法（线性探测法、二次探测法、随机探