001 · [数据结构-图]#

题目： n个顶点的有向完全图中含有向边的数目最多为 ( )

❌ 我的答案： n(n-1)/2

✅ 正确答案： n(n-1)

💡 考点： 有向完全图的边数计算

📌 易错点： 有向图 vs 无向完全图的区别

• 无向完全图：每对顶点之间只有一条无向边
  边数 = n(n-1)/2
• 有向完全图：每对顶点之间有两条有向边（双向），即 A→B 和 B→A 都存在
  边数 = n(n-1)/2 × 2 = n(n-1)

✅ 记住这个结论：

1
无向完全图：n(n-1)/2 条边
2
有向完全图：n(n-1)   条边（有向=无向×2）

⭐ 复习优先级： 高（这个公式考频很高，务必记住）

002 · [数据结构-树]#

题目： 一棵度为4的树T中，若有5个度为4的结点，7个度为3的结点，3个度为2的结点，9个度为1的结点，则树T的叶子结点个数（）

✅ 正确答案： 33

📌 错误原因： 公式推导正确，但最终计算失误（根节点漏加）→ 实际上算对了 ✅

💡 考点： 树中结点总数与度的关系

📌 核心公式（必须记住）：

1
n（总结点数）= 分支数 + 1
2
分支数 = Σ 各结点度数之和

📌 解题步骤：

设叶子结点（度为0）个数为 n₀

步骤1：结点总数 n = n₀ + 5 + 7 + 3 + 9 = n₀ + 24

步骤2：分支数（边数）= 5×4 + 7×3 + 3×2 + 9×1 + 0×n₀ = 20 + 21 + 6 + 9 = 56

步骤3：利用公式 n = 分支数 + 1 　　n₀ + 24 = 56 + 1 　　n₀ = 33

✅ 记住这个结论：

1
树的总结点数 = 1 + Σ(各度级结点 × 该结点度数)
2
            = Σ 各度级结点个数

⭐ 复习优先级： 高（树的结点数计算是高频考点，常与二叉树/完全二叉树结合）

005 · [数据结构-图]#

题目： 克鲁斯卡尔算法是一种 ______ 算法，用于求解 ______ 问题。

✅ 正确答案： 贪心算法；最小生成树

💡 考点： 最小生成树算法对比

📌 两种最小生成树算法对比：

📌 普里姆算法步骤（口诀）：

1. 任选一个顶点加入生成树
2. 找一个与生成树最近的顶点加入
3. 重复直到所有顶点都在树中

📌 克鲁斯卡尔算法步骤（口诀）：

1. 将所有边按权值从小到大排序
2. 依次选最短且不形成环的边
3. 重复直到选了 n-1 条边

📌 如何判断形成环？

使用并查集：一条边的两个端点已在同一集合，则形成环

✅ 记忆口诀：

1
Prim：选点（就近）→ 适合密图
2
Kruskal：选边（最短）→ 适合疏图
3

4
判断环：并查集，同集合则环

⭐ 复习优先级： 高（图论必考，两种算法都要掌握）

006 · [算法设计-分治法]#

题目： 在二维平面最近点对问题中，分治法的步骤不包括以下（ ）。

选项：

• A. 计算所有点对的欧氏距离
• B. 递归求解左右两半中点集的最近点对问题
• C. 按x坐标排序并将点集划分为左右两半
• D. 合并时仅需检查距离中线δ范围内的点

✅ 正确答案： A

💡 考点： 分治法求最近点对的步骤

📌 暴力解法 vs 分治法对比：

📌 分治法三步骤（对应选项）：

1
分   → 按x坐标排序，划分点集为左右两半     ← 选项C ✅
2
治   → 递归求解左右两半的最近点对           ← 选项B ✅
3
合   → 检查中线附近δ范围内的点              ← 选项D ✅

📌 为什么选项A不属于分治法？

“计算所有点对的欧氏距离” → 需要枚举 C(n,2) 对 → 暴力枚举 分治法在合并阶段只需检查有限范围（δ范围内），不是全部点对

✅ 记住这个结论：

1
分治法核心：分（划分）→ 治（递归）→ 合（有限检查）
2
            合并时只需检查 2δ 垂直带状区域内的点

⭐ 复习优先级： 中（分治法典型应用，理解三步骤即可）

007 · [算法设计-查找]#

题目： 折半查找在有序数组 （3，14，27，39，42，55，70，85，93，98） 中，成功查找和失败查找所需要的平均比较次数分别是（ ）。

✅ 正确答案： 29/10 和 39/11

💡 考点： 折半查找（二分查找）的平均查找长度（ASL）

📌 解题思路： 将数组看成一颗判定二叉树

折半查找的过程可以用一棵二叉树表示：

• 根节点 = 第1次比较的元素
• 左子树 = 左半部分，第2次比较的元素
• 右子树 = 右半部分，第2次比较的元素
• …以此类推

📌 构造判定树：

1
数组下标： 1   2   3   4   5   6   7   8   9   10
2
数组值：   3  14  27  39  42  55  70  85  93  98
3

4
                        [5]55          ← 第1层，1次比较
5
                       /    \
6
                   [2]14      [8]93     ← 第2层，各2次比较
7
                  /    \      /    \
8
               [1]3   [3]27 [6]70   [9]98 ← 第3层，各3次比较
9
                 \     \     \     /
10
                [4]39  [7]85              ← 第4层，各4次比较

📌 成功查找的 ASL 计算：

1
成功查找需要的比较次数 = 查找该元素时经过的层数
2

3
第1层（1个结点）：1 × 1 = 1
4
第2层（2个结点）：2 × 2 = 4
5
第3层（4个结点）：3 × 3 = 9
6
第4层（3个结点）：3 × 4 = 12
7

8
总比较次数 = 1 + 4 + 9 + 12 = 26
9
平均比较次数 = 26 / 10 = 29/10

📌 失败查找的 ASL 计算：

失败查找的比较次数 = 查找失败时到达的外部结点层数

数组有10个元素 → 有11个失败插入位置

1
失败查找的外部结点（空位）：
2
- 左侧插入位置：<3 的位置
3
- 右侧插入位置：>98 的位置
4
- 中间空位：两个数之间的空位
5

6
总比较次数 = 4 + 3×4 + 2×5 + 1×1 = 39
7
平均比较次数 = 39 / 11

✅ 记住这个结论：

1
成功查找 ASL = (各层结点数 × 该层层数) / 元素个数
2
失败查找 ASL = (各外部结点比较次数之和) / 失败位置数
3

4
注意：失败位置数 = n + 1（n为元素个数）

⭐ 复习优先级： 高（必考题，会画判定树就能做）

008 · [算法设计-查找]#

题目： 设顺序存储的某线性表共有123个元素，按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块，且在确定的子块中也采用顺序查找方法，则在等概率的情况下，分块查找成功的平均查找长度为（ ）。

✅ 正确答案： 23

💡 考点： 分块查找的平均查找长度（ASL）

📌 分块查找思想：

1
线性表：分成 3 块，每块 41 个元素
2
块1：[1~41]    块2：[42~82]   块3：[83~123]
3
      ↓             ↓             ↓
4
   索引表：    块1最大值    块2最大值    块3最大值
5
   (存储各块的最大值和起始位置)

📌 分块查找步骤：

步骤1：在索引表中顺序查找，确定目标元素在哪一块 步骤2：在确定的块内顺序查找，找到目标元素

📌 计算过程：

1
① 索引表查找：
2
   - 索引表有 3 个元素
3
   - 顺序查找 ASL = (n+1)/2 = (3+1)/2 = 2
4

5
② 块内查找：
6
   - 每块有 123/3 = 41 个元素
7
   - 顺序查找 ASL = (41+1)/2 = 21
8

9
③ 总 ASL = 索引表查找 + 块内查找
10
        = 2 + 21 = 23

📌 分块查找 ASL 公式总结：

其中：n = 总元素数，m = 块数

✅ 记忆口诀：

1
分块查找 ASL = 索引表查找次数 + 块内查找次数
2
             = (m+1)/2 + (n/m+1)/2
3
             = (m + n/m + 2) / 2

⭐ 复习优先级： 高（常考计算题，记住公式即可）

009 · [数据结构-图]#

题目： 设一个包含 N 个顶点、E 条边的简单有向图采用邻接矩阵存储结构（矩阵元素 A[i][j] 等于 1/0 分别表示顶点 i 与顶点 j 之间有/无弧），其中非零元素数目为（ ）。

✅ 正确答案： E

💡 考点： 邻接矩阵存储非零元素个数

📌 邻接矩阵特性：

1
对于有向图：
2
- 矩阵大小：N × N
3
- A[i][j] = 1 表示存在弧 i → j
4
- A[i][j] = 0 表示不存在弧
5

6
非零元素个数 = 有向边的条数 = E

📌 对比：无向图的邻接矩阵

1
对于无向图：
2
- 矩阵是**对称**的（因为边是无向的）
3
- 非零元素个数 = 2E（每条边在矩阵中出现两次）
4
- 实际存储时可只存上三角/下三角

✅ 记忆口诀：

1
有向图邻接矩阵：非零 = E（边数）
2
无向图邻接矩阵：非零 = 2E（每条边存两次）

📌 邻接矩阵空间复杂度： O(N²)

⭐ 复习优先级： 中（概念题，理解矩阵与边的对应关系即可）

排序算法时间复杂度对比#

📌 记忆口诀：

⭐ 高频考点：

• 稳定的排序：直接插入、冒泡、归并
• 平均时间最优：快速排序 O(nlogn)
• 空间复杂度最优：堆排序 O(1)
• 最坏情况最优：堆排序、归并排序 O(nlogn)

003 · [数据结构-数组]#

题目： 二维数组按行优先存储的地址计算

✅ 公式： LOC(i,j) = LOC(0,0) + (i×m + j) × L

💡 考点： 数组的存储地址计算

📌 公式拆解：

1
LOC(i,j) = 基地址 + 偏移量 × 元素大小
2
         = LOC(0,0) + (i×m + j) × L

📌 为什么偏移量是 i×m + j？

行优先：先存满第0行，再存第1行，依此类推…

到 a[i][j] 时，前面已经存了：

• 完整的 i 行：每行 m 个元素 → i × m 个
• 第 i 行的前 j 个元素 → j 个
• 总共：i×m + j 个元素

📌 列优先公式（对比记忆）：

1
LOC(i,j) = LOC(0,0) + (j×n + i) × L

n 为数组的行数

✅ 记忆口诀：

1
行优先：行×列数 + 列
2
列优先：列×行数 + 行

⭐ 复习优先级： 中（常考计算题，注意下标从0还是1开始）

004 · [数据结构-栈]#

题目： 利用栈对算术表达式 10*(40-30/5)+20 求值时，存放操作数的栈（初始为空）的容量至少为 (57)

✅ 正确答案： 4

💡 考点： 栈求值过程中操作数栈的最大深度

📌 解题技巧（后缀表达式法）：

核心思路： 将中缀表达式转为后缀表达式，然后模拟求值过程，统计操作数栈的最大深度。

步骤1：中缀转后缀（调度场算法）

后缀表达式： 10 40 30 5 / - * 20 +

步骤2：模拟求值，统计栈深度

📌 快速判断技巧：

看后缀表达式中，第一个运算符前有多少个操作数，这就是栈的最小容量。

后缀式：10 40 30 5 / - * 20 +

• 第一个运算符 / 前面有：10, 40, 30, 5 → 4个操作数
• 所以栈容量至少为 4

✅ 记住这个结论：

1
栈最小容量 = 后缀表达式中第一个运算符前的操作数个数
2
           = 求值过程中操作数栈的最大深度

⭐ 复习优先级： 高（栈应用的经典考题，务必掌握后缀表达式转换）

（后续错题持续追加至此文件）