《数据结构与算法》复习提纲一、程序设计原理理解二、栈(1)栈说明：栈的定义和基本操作(2)栈的实现：顺序栈的实现(3)应用-桌面计算器(4)应用-括号的匹配(5)抽象数据类型及其实现三、队列(1)定义：队列的定义和基本操作(2)队列的实现：顺序队列的实现(3)C++队列的循环实现：顺序队列的实现(4)演示和测试(5)队列的应用-模拟四、链式栈和链式队列(1)指针和链式结构(2)链栈：链式栈的实现(3)带保护的链栈(4)链式队列：链式队列的实现(5)应用-多项式运算(6)抽象数据类型及其实现：栈和队列的抽象数据类型定义五、递归(1)递归导言：递归算法的两个组成部分、非形式化描述转化为递归定义（如求阶乘等）(2)递归的原理(3)回溯法-延缓工作(4)树结构的程序-在游戏中预测：不做要求六、表和字符串(1)表的定义：表的定义和基本操作(2)表的实现：顺序实现、简单链式实现、双链表(3)字符串：不做要求(4)应用-文本编辑器：不做要求(5)数组链表：不做要求(6)应用-生成排列：不做要求七、查找(1)查找-引言和符号(2)顺序查找：算法流程、算法实现、算法分析（比较次数计算）(3)二分查找：两个版本的算法流程、算法实现、算法分析（比较次数计算）(4)比较树：画出顺序查找和二分查找（两个版本）的比较树(5)下限：不做要求(6)渐近：不做要求八、排序(1)插入排序：算法流程、算法实现(2)选择排序：算法流程、算法实现(3)希尔排序：算法流程(4)链表的归并排序：算法流程、算法实现(5)顺序表的快速排序：算法内容、算法实现(6)堆和堆排序：算法流程、算法实现(7)冒泡排序：算法流程、算法实现九、表和信息检索不做要求十、二叉树(1)二叉树：定义、二叉树遍历、链式实现、通过前序序列和中序序列构造(2)二叉查找树：定义(3)建立二叉查找树：构建方法(4)高度平衡-AVL树：构建AVL树(5)伸展树-自我调节的数据结构：不做要求十一、多路树(1)果园、树和二叉树：定义、果园与二叉树的对应关系及转换(2)词典查找树-trie：不做要求(3)外部查找：B-树：B-树的生长、删除过程(4)红-黑树：不做要求十二、图(1)数学背景：定义(2)计算机表示：几种表示方式(3)图的遍历：深度优先遍历和广度优先遍历的算法流程、算法应用(4)拓扑排序：算法流程(5)最短路径：算法流程、算法应用(6)最小生成树：算法流程、算法应用(7)图作为数据结构：不做要求十三、案例研究不做要求题型：选择题（20）、判断题（10）、简答题（50）、算法填空题（10）、算法设计题（10）分值分布：线性表（栈、队列、表）约25%、查找+排序约30%、树+图约45