文档内容
2023下 粉笔 教资
《 信 息技术》
数 据 结 构与算法 4 / 5
▹ 讲师：阿彬
更多干货关注 粉笔教师教育 粉笔教师❀
复习一下三、树和二叉树的应用 P285
（一）二叉排序树
1.二叉排序树的定义
19
13 50
11 66
26
9 12
21 30 60 70
特点：左子树 < 根节点 < 右子树（二）二叉排序树 P285
2. 二叉排序树的查找
特点：从根节点开始，小在左，大在右（二）哈夫曼树和哈夫曼编码 P285
1.哈夫曼树的定义
➢又称最优二叉树，是带权路径长度（WPL）最短的树 。
✓ 权：为节点赋予某种意义的数值
✓ 节点的带权路径长度：从根到节点的路径长度与该节点上权值的乘积
✓ 树的带权路径长度：树中所有叶子节点的带权路径长度之和（二）哈夫曼树和哈夫曼编码 P286
2.哈夫曼树的构造
【例】给定权值集w={7，5，2，4}，构造关于w的哈夫曼树，并求其加权路径长度WPL。
第1步：找最小的2个数
第2步：组成二叉树（左小右大）根为2数之和
第3步：删除这2个数，并加入根（2数之和）
第4步：重复上述步骤书上无
给定整数集合｛ 3, 5, 6, 9, 12 ｝ ， 与之对应的哈夫曼树是（ ）。（二）哈夫曼树和哈夫曼编码 P287
3.哈夫曼编码
编码规则：左分支赋予0，右分支赋予1书上无
已知字符集{a，b，c，d，e，f}，若各字符出现的次数分别为6、3、 8、 2、10、 4 ，则对应
字符集中各字符的哈弗曼编码可能是（ ）。
A. 00, 1011 , 01 , 1010, 11, 100
B. 00, 100, 110,000, 0010, 01
C. 10 , 1011 , 11 , 0011 , 00, 010
D. 0011 , 10, 11 , 0010, 01 , 000
第1步：构造哈夫曼树
第2步：左0右1得到编码（二）哈夫曼树和哈夫曼编码 P287
【例】已知某系统在通信联络中只可能出现8 种字符（A ～ H），其概率分别为0.05，0.29，0.07，
0.08，0.14，0.23 ，0.03 ，0.11，试设计哈夫曼编码。
第1步：构造哈夫曼树
第2步：左0右1得到编码（二）哈夫曼树和哈夫曼编码 P287
【例】已知某系统在通信联络中只可能出现8 种字符（A ～ H），其概率分别为0.05，0.29，0.07，
0.08，0.14，0.23 ，0.03 ，0.11，试设计哈夫曼编码。第五节 图一、图的基本概念 P288
（一）图的定义
➢ 图由顶点集V和边集E组成，记为G=(V,E) 。
➢ V(G)：图G 的顶点集合
➢ E(G)：图G 的边集合（二）图的相关术语 P288
1. 有向图（边有箭头）
边用有序对(弧)表示 <2,3>
2.无向图（边无箭头）
边用无序对表示（2,3）或者（3,2）（二）图的相关术语 P289
3. 无向完全图、有向完全图
n个顶点有n(n–1)/2 条边 n个顶点有n(n–1)条边（二）图的相关术语 P289
4. 子图
子图就是图的一部分（二）图的相关术语 P289
5. 邻接、依附、关联
BC相邻接 B邻接到C
（B,C）依附于B和C顶点 C邻接自B
BD不邻接（二）图的相关术语 P290
6. 度、入度、出度
➢度（TD）
✓ 和顶点v相关联的边的数目
总度数=2×总边数
➢入度（ID）
✓ 发出箭头的数目
➢出度（OD）
✓ 箭头指向的数目
出度=入度=边数（二）图的相关术语 P290
7.路径
➢从顶点vi到顶点vj，依次经过的顶点序列。
8.连通、连通图（无向图）
➢两顶点有路径则连通
➢任意两顶点有路径的图为连通图
➢n 个顶点，并且边数小于 n –1 ，则此图必是非连通图。
8.强连通、强连通图（有向图）
➢两顶点正反都有路径存在，则强连通
➢任意两顶点都是强连通，则图为强连通图（二）图的相关术语 P290
10. 权、网
➢边上有数值，该数值称为权。
➢带权的图通常称为网。
权值二、图的存储 P291
（一）邻接矩阵
图：有边写1，无边写0
网：有边写值，无边写∞二、图的存储 P292
（二）邻接表
无向图：写与该顶点相连的
有向图：写由该顶点出发的三、图的遍历 P292
（一）深度优先遍历
➢类似树的先序遍历，从任意顶点出发，沿一个方向遍历相邻顶点，然后回溯三、图的遍历 P293
（二）广度优先遍历
➢类似树的层遍历，从任意顶点出发，先遍历完该顶点所有相邻顶点，再遍历下一层书上无
若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是（ ）。
A. h、c、a、b、d、e、g、f
B. e、a、f、g、b、h、c、d
C. d、b、c、a、h、e、f、g
D. a、b、c、d、h、e、f、g四、图的应用 P293
旅行商问题（TSP）
◆
➢从一个城市出发，需要经过所有城市一次并且仅一次之后， 回到出发城市。
➢要求总路程最短。
两种解决方法（贪心）
◆
➢最短链接策略【关注的是边】
➢最近邻点策略【关注的是顶点】1.最短链接策略 P293
【例】假设 5 个相互可直达且距离已知的城市如下图（a）所示，采用最短链接策略从城市 1 出发回
到城市 1 。
城市 距离 可用否
1
5 2
4 3
第1步：按距离升序排列
第2步：依次加入最短边
•要求①：无回路
•要求②：每个顶点≤2条边2.最近邻点策略 P294
【例】假设 5 个相互可直达且距离已知的城市如下图（a）所示，采用最近邻点策略从城市 1 出发回
到城市 1 。
1
5 2
第1步：找顶点A相邻的最短路径，确定下一个顶点B
4 3
第2步：从B出发，继续找B相邻的最短路径
•要求①：无回路
•要求②：选未到过的顶点书上无
（2021 下· 高中）“绿水青山就是金山银山”，加强环境保护对经济社会发展十分必要，长
江和重要支流进入十年禁渔期，一大批长江保护巡查员常年在“水上漂”，目的就是及时发
现不法分子对长江水域的各种破坏活动。有五个相互可直达且距离已知的工作站甲、乙、丙、
丁、戊，如下表所示，某巡查员从工作地甲出发，其他四个工作站巡查完后再回到工作站甲。
产生式得出最短巡查路线的距离x 是（ ）。
甲
A. 42
甲 乙 丙 丁 戊
B. 38
甲 —— 7 5 10 10
乙 丙
C. 36 乙 7 —— 7 10 10
丙 5 7 —— 6 9
D. 47
丁 10 10 6 —— 8
丁 戊
戊 10 10 9 8 ——下
节
内
容
