1. 考点：最小生成树：克鲁斯卡尔算法

2. 考点：最小生成树：普里姆算法

3. 考点：最短路径：底杰斯特拉算法

3.1 思考1：迪杰斯特拉算法采用的算法策略是？

答案：贪心算法（Greedy Algorithm）。

解析：
如图所示，迪杰斯特拉（Dijkstra）算法的核心思想是：“每次从未求出最短路径的点中，取出距离起点最小路径的点，以这个点为桥梁刷新未求出最短路径的点的距离。”
这种在每一步选择中都采取当前状态下最好（即距离起点最近）的选择，从而希望导致结果是全局最优的策略，正是贪心算法的典型特征。

1. 考点：基本概念

2. 经典例题

2.1 题目一

2.2 题目二

题目： 对有向图 $G$ 进行拓扑排序得到的拓扑序列中，顶点 $V_i$ 在顶点 $V_j$ 之前，则说明 $G$ 中（ B ）。

• A. 不一定存在有向弧 $<V_i, V_j>$
• B. 一定不存在有向弧 $<V_i, V_j>$
• C. 必定存在从 $V_i$ 到 $V_j$ 的路径
• D. 必定存在从 $V_j$ 到 $V_i$ 的路径

考点：遍历类型

经典例题

题目一

1. 考点：图的定义

2. 考点：数组存储

3. 考点：链表存储

4. 经典例题

4.1 题目一

题目： 某简单无向连通图 $G$ 的顶点数为 $n$，则图 $G$ 最少和最多分别有（ ）条边。

• A. $n, \dfrac{n^2}{2}$
• B. $n - 1, \dfrac{n(n-1)}{2}$
• C. $n, \dfrac{n(n-1)}{2}$
• D. $n - 1, \dfrac{n^2}{2}$

1. 考点：最优二叉树基本概念

1.1 需要了解的基本概念

• 叶子结点的路径长度：从根结点到该叶子结点之间的分支线数量（即层数减 1，若根结点算第 0 层）。

• 树的路径长度：所有叶子结点路径长度之和。

• 权（Weight） ：叶子结点的数值（代表该结点的重要程度或出现频率）。

• 叶子结点的带权路径长度：该结点的 权重 $\times$ 路径长度。

• 树的带权路径长度（WPL，树的代价） ：所有叶子结点带权路径长度之和：

  $$\text{WPL} = \sum_{i=1}^{n} (w_i \times l_i)$$

1. 考点：查找二叉树的特点

1.1 核心定义与性质

• 二叉排序树（Binary Sort Tree, BST） ：又称二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树：

  1. 若左子树不空，则左子树上所有结点的值均小于它的根结点的值。
  2. 若右子树不空，则右子树上所有结点的值均大于它的根结点的值。
  3. 它的左、右子树也分别为二叉排序树。
  • 大小关系口诀：$\text{左孩子} < \text{根} < \text{右孩子}$

1. 考点：二叉树的遍历方式

1.1 二叉树的四种核心遍历方式

• 层次遍历：从上至下，从左至右逐层访问。
• 前序遍历：【根 - 左 - 右】（先访问根节点，再遍历左子树，最后遍历右子树）。
• 中序遍历：【左 - 根 - 右】（先遍历左子树，再访问根节点，最后遍历右子树）。
• 后序遍历：【左 - 右 - 根】（先遍历左子树，再遍历右子树，最后访问根节点）。

1. 考点：树的基本组成元素

术语分类	核心概念与定义	补充说明 / 图示理解
基础元素	•结点：图中的圆圈，表示数据元素。 •分支：结点之间的连线。	整个树结构由结点和分支构成。
度 (Degree)	•结点的度：该结点的子树数目。 •树的度：各结点度的最大值。	• 比如根结点有2个孩子，其度为2。 • 整棵树中度最大的那个结点的度即为树的度。
结点类型	•叶子结点：度为$0$的结点（无分支）。 •分支结点（非终端结点） ：度不为$0$的结点（有分支）。 •内部结点：除根结点以外的分支结点。	• 叶子结点相当于“末端”。 • 内部结点既不是根，也不是叶子。
层次与高度	•层次：根结点为第$1$层，往下依次类推。 •树的高度（深度） ：一棵树的最大层次数（总层数）。	• 如图所示，该树共有$4$层，因此其高度为$4$。
相对关系	•父结点、子结点、兄弟结点：描述结点之间的上下级与同级关系。	树形结构特有的亲缘关系描述。

1. 考点：数组与矩阵的存储地址计算

1.1 基本概念

• 下标规则：在计算机中，数组的下标一般从 $0$ 开始计算。

• 符号说明：

  • $a$：数组的起始内存地址（基地址）。
  • $\text{len}$：单个元素所占用的字节数（存储长度）。

1. 考点：串的基本概述

1.1 串的定义

• 基本概念：串（String）是仅由字符构成的有限序列，本质上是一种特殊的线性表。

• 表示方法：一般记为：

  $$S = 'a_1a_2a_3 \dots a_n$$

  • 其中，$S$ 是串名。
  • 单引号括起来的字符序列 $a_1a_2a_3 \dots a_n$ 是串值。
  • $n$ 为串的长度（即字符个数），当 $n = 0$ 时称为空串。