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

第一章绪论数据结构的定义：数据的逻辑结构：线性结构（线性表、栈、队列、串）和非线性结构（树、图）；数据的物理结构：顺序存储、链式存储、索引存储、散列存储；常用的数据结构的运算：插入、删除、查找、修改、排序；时间复杂度的计算；第二章线性表1、顺序存储和链式存储的定义，优缺点，及其适用场景；2、单链表和双向链表的基本操作如何实现，诸如插入、删除等；3、带头结点和无头结点的单链表L的判空条件4、邻接表是一种结合了顺序存储与链式存储的存储格式，在那些结构中被使用第三章栈和队列栈：1、栈的相关操作：入栈和出栈；2、给定入栈序列，写出所有可能的出栈序列；3、共享栈的基本概念和操作；队列：1、顺序队列的“假溢出”是怎样产生的？2、循环队列：长度的计算；队满的表达式；队空的表达式；第四章串1、串的存储方式2、朴素匹配算法和KMP算法的核心思想：两种算法比较次数的计算第五章多维数组和广义表多维数组：1、二维数组存储地址的计算（行优先存储和列优先存储）第一个元素的下标；第一个元素的存储地址；每个元素占几个单元；2、特殊矩阵的压缩存储（对称矩阵、三角矩阵、对角矩阵）如何进行压缩存储；压缩存储后，ija（二维数组）和][ksa（顺序表）之间的对应关系；也就是说如何通过i和j算出k。稀疏矩阵的两种存储方式：三元组表、十字链表；矩阵的快速转置：临时表的构建，每一列的非零元的个数；每一列的非零元在转置矩阵中的下标广义表：1、广义表的定义2、广义表的取表头和取表尾运算),(baLaLhead)()()(bLtail第六章树二叉树的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/n处开始建立；排序时，输出元素如何选择，输出后如何调整，使得剩余元素依旧满足堆的性质）；归并排序：建议：对比学习：比如直接插入和直接选择、希尔排序和归并排序，相同点在哪里，不同点在哪里？第九章查找线性表的查找顺序查找：折半查找（二分查找）；分块查找：树表的查找二叉排序树的查找：平衡二叉排序树（AVL树）：散列表的查找常见的哈希函数冲突处理方法：开放地址法（线性探测法、二次探测法、随机探测法）、拉链法各种查找方法的平均路径长度niiicp1ASL=niicn11（等概率模型，ic为找到第i个数据元素所需要进行的比较次数）