第10-12章习题课概要.ppt

第5章 二叉树 一. 概念 1. 二叉树 2.二叉树的深度优先周游 3. 二叉排序树 4. 堆 5. Huffman树、Huffman编码 各种结构的节点个数与高度、层次、度等关系换算 二. 方法 1．二叉树的链式存储 （1）二叉链表 （2）带父指针的三重链表 * 2. 二叉树的顺序存储 完全二叉树的顺序存储 ★ 3. 二叉树的深度优先周游 ★ 4. BST树的插入与删除 ★ 5. 构造Huffman树和Huffman编码 ★ 6. 堆的建立与维护过程 * * * * 第6章 树 一. 概念 树、森林 、先根、后根、层次周游 ★ K叉树 二. 方法 ★ 1. 森林与二叉树相互转换 2．森林的链式存储 ★ (1) 转换为相应的二叉树，用二叉链表表示 (2) 父指针表示法、(3) 子结点表表示法 (4)等价类和并查算法的应用 * ★ 3. 森林的深度优先周游（递归），可能结合应用 ★ 4. 森林的顺序存储及其构造 5. 二叉树和森林的层次周游(用队列)，可能结合应用 * 第7章 图 一. 概念 1. 图的相关概念：连通性、连通分量、边与顶点关系等 2. 深度周游、宽度周游 3. 图的生成树、生成树林、最小生成树 ★二. 方法及算法 ★1. 图的存储方法:（1） 相邻矩阵 （2） 邻接表 2. 图的周游: 1） 深度优先 （2） 宽度优先 * 3. 图的生成树与最小生成树 从某一点出发，按深度优先或宽度优先周游的生成树 最小生成树 ① Prim算法 ② Kruskal算法(避圈法) 4. 拓扑排序 : 给定图，找出若干个或所有拓扑序列 5. 最短路径: Dijkstra算法、Floyd算法 6. Dijkstra算法、Prim算法、Kruskal算法都是典型的贪心法（退化的动态规划法） * 第8章 内排序 ??1. 重点排序算法：直接插入法、★Shell排序、★快速排序、★基数排序、归并排序 ??2. 算法分析 基于比较次数和移位次数分析最好、最坏的时间、空间 直接插入法、二分法插入排序、起泡排序、直接选择、快速排序、基数排序、归并排序 记住各种排序方法的平均时间 ??3. 各种排序方法的局部修改和混合应用 * 第9章 文件管理和外排序 方法及算法 ??1. ★置换选择排序? 2. ★多路归并 (败者树，最佳归并树，多路归并的读盘和写盘次数) * 第10章 检索 一. 概念 1. 平均检索长度 2. 二分法检索? ★3. 散列表、同义词、碰撞、堆积 二. 方法 1. 二分法检索的判定树、查找某个结点的比较次数 2. 散列表: 1) 散列函数选择(除余法、平方取中法、折叠法) 2) 冲突处理方法(分离同义词子表、线性探测、双散列函数) ★三. 散列算法（查找、插入、删除，对墓碑的处理 * 第11章 索引技术 一. 概念 ?1. 顺序文件 2. 散列文件 3. 倒排文件 4. 静态索引结构? 5.动态索引结构(B树) 6. 红黑树 二. 方法（不考算法） ★1. B树、B+树的插入与删除(注意保持性质，特别是等高；以及子 结点和关键码个数的上下限制) ★2. B树/B+树的读盘和写盘次数分析? ? * 3. B树/B+树的效率分析 B树中关键码没有重复，父结点中的关键码是其子结点的分界；B+中最底层是关键码的一个全集，往根的方向一层层复写。 B树插入 与删除、B+树插入与删除 ?★4. 红黑树的插入方法。删除算法不考，可考性质 插入算法首先是采用BST的方法把结点插入到位，然后注意调整。尤其是“红红”冲突的解决，注意有换色、重构 * 第12章 高级数据结构 一. 概念 1. 多维数组和稀疏矩阵 2. 广义表 3. Trie树 4. Patricia 5. AVL树 6. 伸展树 二. 方法（不考具体算法，但要求掌握方法并应用） ★1. 特殊矩阵和稀疏矩阵的计算。 ★2. 广义表的结构和周游 3. 字符树：Trie树和Patricia树 * 4. 最佳二叉有哪些信誉好的足球投注网站树，理解平均检索长度最优的特点 ★5. AVL平衡二叉树的插入方法：LL、LR、RL、RR的四种旋转调整。不考删除算法，但可考性质 ★6. 伸展树及其简单应用： 伸展树在有哪些信誉好的足球投注网站过程中旋转调整结构，使访问最频繁的结点靠近树结构的根。伸展树的旋转分为：单旋转、一字形旋转和之字形旋转。注意伸展树的变种，例如半伸展树。splay树的插入、删除以及区间操作都要求掌握 * * 再见… 联系信息： 电子邮件：gjsong@pku.edu.cn 电 话： 办公地点：理科2号楼2307室 * 张铭 红黑树 * * C 是黑色，且左红、右黑 C 是黑色，且右红色 张铭 红