[优质文档]2015年《数据结构与算法》温习提纲.docVIP

《数据结构与算法》复习提纲 一、程序设计原理 理解 二、栈 (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