下载文档原格式
6.3哈夫曼树6.3.1基本术语1.路径和路径长度若在一棵中存在着一个结点序列k1 ,k2,…,kj，使得ki是k1+i 的双亲(1ji<≤)，则称此结点序列是从k1～kj的路径，因树中每个结点只有一个双亲结点，所以它也是这两个结点之间k 1～kj所经过的分支数称为这两点之间的路径长度，它等于路径上的结点数减1(实际就是边数)。
如在图5-19(a)所示的二叉树中，从树根结点L到叶子结点P的路径为结点序列L、M、S、P，路径长度为3。
(a) (b)(c) (d)图5-19 二叉排序树的删除2.结点的权和带权路径长度在许多应用中，常常将树中的结点赋上一个有着某种意义的实数，我们称此实数为该结点的权。
结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点上权的乘积3.树的带权路径长度树的带权路径长度定义为树中所有叶子结点的带权路径长度这和，通常记为：2 WPL = ∑=n i i i lw 1其中n 表示叶子结点的数目，i w 和i l 分别表示叶子结点i k 的权值和根到i k 之间的路径长度 。
4.哈夫曼树哈夫曼(Huffman)树又称最优二叉树。
它是n 个带权叶子结点构成的所有二叉树中，带权路径长度 WPL 最小的二叉树。
因为构造这种树的算法是最早由哈夫曼于1952年提出的，所以被称之为哈夫曼树。
例如，有四个叶子结点a 、b 、c 、d ，分别带权为9、4、5、2，由它们构成的三棵不同的二叉树（当然还有其它许多种）分别如图5-20(a)到图5-20(c)所示。
b ac a b cd d c a b d(a) (b) (c)图5-20 由四个叶子结点构成的三棵不同的带权二叉树 每一棵二叉树的带权路径长度WPL 分别为：(a) WPL = 9×2 + 4×2 + 5×2 + 2×2 = 40(b) WPL = 4×1 + 2×2 + 5×3 + 9×3 = 50(c) WPL = 9×1 + 5×2 + 4×3 + 2×3 = 37其中图5-20(c)树的WPL 最小，稍后便知，此树就是哈夫曼树。
第六章习题答案一、选择填空1、A2、C3、D4、B5、D6、A7、C8、A9、D 10、A11、C 12、A 13、B 14、C 15、C 16、D 17、B 18、C 19、A 20、D21、C 22、B二、判断下列描述的正确性，对者划√，错者划×。
1、√2、×3、×4、×5、√6、√7、×8、√9、×10、√11、√12、√13、√14、√15、×16、√17、√18、√19、√20、×21、×22、×三、分析下列程序的输出结果。
1、运行该程序输出结果如下所示。
Default constructor calledConstructor calleda=0,b=0a=4,b=82、运行该程序输出结果如下所示。
a=7,b=93、运行该程序输出结果如下所示。
1044、运行该程序输出结果如下所示。
1035，789.5045、运行该程序输出结果如下所示。
1{}{0，1，2，3，4，5，6，7，8}1{11，12，13，14，15，16，17，18，19}{19，18，17，16，15，14，13，12，11}6、运行该程序输出结果如下所示。
Starting1:Default constructor called.Default constructor called.Default constructor called.Eding1:Starting2:Constructor: a=5,b=6Constructor: a=7,b=8Constructor: a=9,b=10Ending2:Destructor called.a=9,b=10Destructor called.a=7,b=8Destructor called.a=5,b=6Destructor called.a=5,b=6Destructor called.a=3,b=4Destructor called.a=1,b=27、运行该程序输出结果如下所示。
Python习题第六章人名最多数统计解题思路Python习题第六章包含【人名最多数统计编程思路】1.关于大括号{}，以下描述正确的是：A直接使用{}将生成一个列表类型B直接使用{}将生成一个元组类型C直接使用{}将生成一个集合类型D直接使用{}将生成一个字典类型正确答案 D考点：集合类型和字典类型最外侧都用{}表示，不同在于，集合类型元素是普通元素，字典类型元素是键值对。
字典在程序设计中非常常用，因此，直接采用{}默认生成一个空字典。
2.列表ls，哪个选项对ls.append(x)的描述是正确的？A向列表ls最前面增加一个元素xB替换列表ls最后一个元素为xC只能向列表ls最后增加一个元素xD向ls中增加元素，如果x是一个列表，则可以同时增加多个元素正确答案 C考点：ls.append(x)，如果x是一个列表，则该列表作为一个元素增加的ls 中。
3.以下不是Python序列类型的是：A字符串类型B列表类型C元组类型D数组类型正确答案 D考点：Python内置数据类型中没有数组类型。
4.给定字典d，哪个选项对x in d的描述是正确的？A x是一个二元元组，判断x是否是字典d中的键值对B判断x是否是字典d中的值C判断x是否是在字典d中以键或值方式存在D判断x是否是字典d中的键正确答案D考点：键是值的序号，也是字典中值的索引方式。
因此，x in d 中的x被当作d中的序号进行判断。
5.序列s，哪个选项对s.index(x)的描述是正确的？A返回序列s中元素x所有出现位置的序号B返回序列s中序号为x的元素C返回序列s中元素x第一次出现的序号D返回序列s中x的长度正确答案 C考点：s.index(x)返回第一次出现x的序号，并不返回全部序号。
5.哪个选项是下面代码的输出结果？d= {'a': 1 'b': 2 'b': '3'}print(d['b'])A 1B 2C {'b':2}D 3正确答案 D考点：创建字典时，如果相同键对应不同值，字典采用最后（最新）一个"键值对"。
《C语言程序设计》教案第一章：C语言概述1.1 C语言的发展历史1.2 C语言的特点1.3 C语言的应用领域1.4 集成开发环境的使用第二章：C语言基础语法2.1 数据类型2.1.1 整型2.1.2 浮点型2.1.3 字符型2.2 变量和常量2.2.1 变量的声明和使用2.2.2 常量的定义和使用2.3 运算符与表达式2.3.1 算术运算符2.3.2 关系运算符2.3.3 逻辑运算符2.3.4 赋值运算符2.3.5 条件运算符2.3.6 逗号运算符2.4 输入输出函数2.4.1 标准输入输出函数2.4.2 格式化输入输出函数第三章：控制语句3.1 顺序结构3.2 选择结构3.2.1 if语句3.2.2 switch语句3.3 循环结构3.3.1 while循环3.3.2 do-while循环3.3.3 for循环3.3.4 循环控制语句第四章：函数与编译预处理4.1 函数的定义和调用4.1.1 函数的声明4.1.2 函数的实现4.1.3 函数的调用4.2 变量的作用域4.2.1 全局变量4.2.2 局部变量4.3 静态变量和动态内存分配4.3.1 静态变量的使用4.3.2 动态内存分配函数4.4 编译预处理指令4.4.1 宏定义4.4.2 文件包含4.4.3 条件编译第五章：数组和字符串5.1 一维数组5.1.1 数组的声明和初始化5.1.2 数组的访问和操作5.2 二维数组5.2.1 二维数组的声明和初始化5.2.2 二维数组的访问和操作5.3 字符串5.3.1 字符串的概念5.3.2 字符串的存储结构5.3.3 字符串的操作函数第六章：指针6.1 指针的概念6.2 指针的声明和赋值6.3 指针与数组6.3.1 指向数组的指针6.3.2 指针数组6.3.3 数组的指针6.4 指针与函数6.4.1 指针作为函数参数6.4.2 返回指针的函数6.5 指针与动态内存分配6.5.1 动态内存分配的概念6.5.2 动态内存分配函数6.5.3 内存泄漏与释放第七章：结构体、联合体和枚举7.1 结构体的定义和使用7.1.1 结构体的声明7.1.2 结构体的初始化7.1.3 结构体的访问7.2 联合体的定义和使用7.2.1 联合体的声明7.2.2 联合体的初始化7.2.3 联合体的访问7.3 枚举类型的定义和使用7.3.1 枚举类型的声明7.3.2 枚举类型的访问第八章：文件操作8.1 文件的概念8.2 文件打开与关闭8.2.1 文件打开函数8.2.2 文件关闭函数8.3 文件的读写操作8.3.1 文件读取函数8.3.2 文件写入函数8.4 文件指针的定位8.4.1 文件位置指针8.4.2 文件定位函数8.5 文件操作的错误处理第九章：标准库函数9.1 标准输入输出库函数9.2 字符串处理库函数9.3 数学计算库函数9.4 日期和时间库函数9.5 高级输入输出库函数第十章：编程实践与案例分析10.1 数据结构的应用10.1.1 链表的实现10.1.2 栈和队列的应用10.2 算法设计与分析10.2.1 排序算法10.2.2 搜索算法10.3 数据库编程10.3.1 数据库连接10.3.2 数据库操作10.4 网络编程10.4.1 套接字编程基础10.4.2 网络通信协议10.5 实际项目案例分析10.5.1 项目需求分析10.5.2 项目设计与实现10.5.3 项目测试与优化重点和难点解析一、C语言的发展历史和特点重点关注C语言的历史背景和设计初衷，以及其为何能在多年后仍然被广泛使用。
