文档内容
~ 2 0 2 4 年 教 师 资 格 ~
《 信 息技术( 科技) 》
数 据 结 构与算法 4 / 5
讲师：阿彬
更多干货关注 粉笔教师教育 粉笔教师❀
复习一下P285
三、树和二叉树的应用
（一）二叉排序树
1.二叉排序树的定义
19
13 50
11 66
26
9 12
21 30 60 70
特点：左子树 < 根节点 < 右子树P285
（二）二叉排序树
2.二叉排序树的查找
查找4 查找 7
特点：从根节点开始，小在左，大在右书上无
试题巩固
已知二叉排序树如下图所示，元素之间应满足的大小关系是（ ）。
A. x1
2.无向图（边无箭头）
边用无序对表示（2,3）或者（3,2）P289
（二）图的相关术语
3. 无向完全图、有向完全图
n个顶点有n(n–1)/2 条边 n个顶点有n(n–1)条边书上无
试题巩固
设某完全无向图中有n个顶点，则该完全无向图中有（ ）条边。
A.(n(n-1))/2
B.n(n-1)
C.n2-1
D.n2P289
（二）图的相关术语
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 ，则此图必是非连通图
9.强连通、强连通图（有向图）
➢强连通：有向图中若两顶点正反都有路径存在，则称两顶点强连通
➢强连通图：图中任意两顶点都是强连通P290
（二）图的相关术语
10. 权、网
➢边上有数值，该数值称为权
➢带权的图通常称为网
权值
图 网P291
二、图的存储
（一）邻接矩阵
图：有边写1，无边写0
网：有边写值，无边写∞书上无
试题巩固
设图的邻接矩阵A如下图所示。各顶点的度依次是（ ）。
A.1、2、1、2
B.2、2、1、1
C.3、4、2、3
D.4、4、2、2P292
二、图的存储
（二）邻接表
无向图：写与该顶点相连的
有向图：写由该顶点出发的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、gP293
四、图的应用（旅行商问题）
旅行商问题（TSP）
◆
➢从一个城市出发，需要经过所有城市一次并且仅一次之后， 回到出发城市。
➢要求总路程最短。
两种解决方法（贪心）
◆
➢最短链接策略【关注的是边】
➢最近邻点策略【关注的是顶点】P293
1. 最短链接策略
【例】假设 5 个相互可直达且距离已知的城市如下图（a）所示，采用最短链接策略从城市 1 出发
回到城市 1 。
城市 距离 可用否
1
5 2
4 3
第1步：按距离升序排列
第2步：依次加入最短边
•要求①：无回路
•要求②：每个顶点≤2条边P294
2.最近邻点策略
【例】假设 5 个相互可直达且距离已知的城市如下图（a）所示，采用最短链接策略从城市 1 出发
回到城市 1 。
1
5 2
4 3
第1步：找顶点A相邻的最短路径，确定下一个顶点B
第2步：从B出发，继续找B相邻的最短路径
•要求①：无回路
•要求②：选未到过的顶点书上无
试题巩固
（2021 下· 高中）“绿水青山就是金山银山”，加强环境保护对经济社会发展十分必要，
长江和重要支流进入十年禁渔期，一大批长江保护巡查员常年在“水上漂”，目的就是及时
发现不法分子对长江水域的各种破坏活动。有五个相互可直达且距离已知的工作站甲、乙、
丙、丁、戊，如下表所示，某巡查员从工作地甲出发，其他四个工作站巡查完后再回到工作
站甲。产生式得出最短巡查路线的距离x 是（ ）。 甲
A. 42
甲 乙 丙 丁 戊
甲 —— 7 5 10 10 乙 丙
B. 38
乙 7 —— 7 10 10
C. 36
丙 5 7 —— 6 9
D. 47
丁 10 10 6 —— 8
丁 戊
戊 10 10 9 8 ——书上无
试题巩固
（2023 上· 高中）有五个相互可直达且距离已知的学校A、B、C、D、E，如下表所示，
调研员从学校A 出发，去每个学校各调研一次，最后回到学校A，请找出一条路径最短的路
线。（ ）
A. ADEBCA
B. ACDEBA
C. ABCDEA
D. ADCBEA下
节
内
容
2024FENBI
