有关阶段小结(二)-非线性结构.ppt

Chapter9 优先队列 Huffman编码及应用 Huffman编码是一种应用广泛且非常有效的数据压缩技术，该技术一般可以将数据文件压缩掉20%-90%，其压缩效率取决于被压缩文件的特征。 数据压缩 - 例如JPEG标准中基准模式采用的就是Huffman编码。 通信、密码 Huffman编码在相关领域中的应用研究 Huffman编码在相关领域中的应用研究 练习1 练习2 练习3 练习4 练习5 练习6 练习7 练习8 练习9 练习10 练习11 练习12 练习13 练习14 练习15 *数组和矩阵 * 阶段小结（二） ——非线性结构 Chapter8 树和二叉树 Chapter9 优先队列 Chapter10 有哪些信誉好的足球投注网站树 Chapter12 图 各章重点内容回顾 Chapter8 树和二叉树 1、树和二叉树的概念 2、二叉树的性质、完全二叉树及满二叉树 3、二叉树顺序表示和链式表示 两种方法分别如何表示一棵二叉树以及其各自的优缺点 4、二叉树的遍历及应用 已知一棵二叉树的前序遍历序列（或后序遍历序列）和中序遍历序列，可唯一确定一棵二叉树； 二叉树遍历的应用。 1、堆 堆的定义、判定； 堆的插入、删除及相应的调整算法； 堆排序及其效率 2、 Huffman树 Huffman树的特点 Huffman树构造方法 Huffman编码。 JPEG压缩模块结构图 Chapter11 有哪些信誉好的足球投注网站树 1、二叉有哪些信誉好的足球投注网站（排序）树 二叉有哪些信誉好的足球投注网站树的特点及构造方法 二叉有哪些信誉好的足球投注网站树查找、插入及删除操作 二叉有哪些信誉好的足球投注网站树查找成功时的平均查找（有哪些信誉好的足球投注网站）长度 2、AVL树 AVL树的特点及构造方法 AVL树的插入及非平衡的旋转 AVL树查找成功时的平均查找（有哪些信誉好的足球投注网站）长度 Chapter12 图 1、图的基本概念 2、图的存储表示 邻接矩阵 邻接表 3、图的遍历 图的深度优先遍历 图的宽度优先遍历 4、图的应用 寻找路径 连通图和连通分量 课堂练习 已知一棵完全二叉树中共有768结点，则该树中共有_____个叶子结点。 384 已知一棵完全二叉树中共有767结点，则该树中共有_____个叶子结点。（2003年软考试题） 384 完全二叉树中度为1的节点数只有两种可能：要么为0个，要么为1个。 设节点x和y是二叉树中任意两个节点，在该二叉树的前序遍历序列中x在y之前，而在后序遍历序列中x在y之后，则x和y的关系是： A、x是y的左兄弟 B、x是y的右兄弟 C、x是y的祖先 D、x是y的后裔 C （2004年软考试题） 下列序列不是堆的是 。 A、（100，85，98，77，80，60，82，40，20，10，66） B、（100，98，85，82，80，77，66，60，40，20，10） C、（10，20，40，60，66，77，80，82，85，98，100） D、（100，85，40，77，80，60，66，98，82，10，20） D 在数据压缩编码应用中，Huffman算法可以用来构造具有 （1） 的二叉树，这是一种采用了 （2） 算法的算法。 （1）A、前缀码 B、最优前缀码 C、后缀码 D、最优后缀码 （2）A、贪心 B、分治 C、递推 D、回溯 解答：（1）B （2） A 假设用于通信的电文仅由a，b，c，d，e，f，g，h，8个字母组成，各字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。 （1）试为这8个字母设计Huffman编码（需画出相应的Huffman树）。 （2）使用0-7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。（提示：试从两种编码的带权路径长度上进行比较说明） WPLHF=2.61，WPLEQ=3 提高通信信道的利用率，提高报文发送速度或/和节省存储空间。 B 有数据{53，30，37，12，45，24，96}，从空二叉树开始逐个插入数据来形成二叉有哪些信誉好的足球投注网站树，若希望高度最小，则应选择下面哪个序列输入 。 A、45，24，53，12，37，96，30 B、37，24，12，30，53，45，96 C、12，24，30，37，45，53，96 D、30，24，12，37，45，96，53 一棵二叉有哪些信誉好的足球投注网站树，其节点