画个图就知道了，前面的下三角词语是误导，因为有i<j，所以其实要压缩的矩阵是上三角矩阵

B/C/D 是算法设计的评价维度，非 “分析” 核心

单向链表的节点只有data和next指针（只能指向后继，无法反向找前驱），这是关键约束：

• 已知头指针：能直接访问头节点，遍历到尾节点需要 O (n) 时间；
• 已知尾指针：能直接访问尾节点，但无法直接找到尾节点的前驱（要删尾节点必须先找前驱，需遍历 O (n) 时间）。

非递归重写递归程序必须用栈 → 错（可用循环）

中缀表达式转后缀的核心是利用栈管理运算符的优先级，规则如下：

1. 数字 / 操作数：直接输出到结果中；
2. 运算符（+、-、*、/）：
   • 栈空 → 直接入栈；
   • 栈非空 → 比较当前运算符与栈顶运算符的优先级：
     • 当前优先级 > 栈顶 → 入栈；
     • 当前优先级 ≤ 栈顶 → 弹出栈顶运算符到结果，重复比较直到栈空 / 当前优先级更高，再将当前运算符入栈；
3. 括号（本题无，但同类题常见）：
   • 左括号 (：直接入栈；
   • 右括号 )：弹出栈内运算符到结果，直到遇到左括号（左括号弹出但不输出）；
4. 遍历结束：将栈内剩余运算符依次弹出到结果。

核心规则（后缀→中缀）

1. 遍历后缀表达式的每个字符；
2. 遇到操作数：直接压入栈中；
3. 遇到运算符：
   • 弹出栈顶第一个数 → 记为 右操作数；
   • 弹出栈顶第二个数 → 记为 左操作数；
   • 拼接成 (左操作数 运算符 右操作数) 的中缀形式；
   • 将拼接后的字符串压入栈中；
4. 遍历结束后，栈中仅剩的字符串就是最终的中缀表达式。

核心规则（中缀→前缀）：先把表达式反向

1. 操作数：直接加入临时结果列表；
2. 运算符（+、-、*、/）：
   • 栈空 → 直接入栈；
   • 栈非空 → 比较当前运算符与栈顶优先级：
     • 当前优先级 ≥ 栈顶 → 弹出栈顶到临时结果，重复比较直到栈空 / 当前优先级更低；
     • 当前优先级 < 栈顶 → 直接入栈；
3. 括号：
   • 右括号 ) → 直接入栈；
   • 左括号 ( → 弹出栈内运算符到临时结果，直到遇到右括号（右括号弹出但不加入结果）；
4. 遍历结束：将栈内剩余运算符依次弹出到临时结果；
5. 最终反转：将临时结果列表反转，得到前缀表达式。

三对角矩阵（仅主对角线、上对角线、下对角线非零）行优先存储（下标从 0 开始）：

• 第 1 行：2 个元素（m11,m12）；
• 第 2~29 行：每行 3 个元素；
• 第 30 行：m30,30 是第 2 个元素；
• 总数 = 2 + 28×3 +1 = 2+84+1=87（下标从 0 开始，直接对应 87）

注意表述，“原来的森林里”

森林的后根遍历序列与对应二叉树的中序遍历序列相同

• 链队需要快速访问队头（出队）和队尾（入队）；
• 只带队头指针的非循环双链表：入队需遍历到队尾（O (n)），效率最低

循环队列约定 “牺牲一个空位” 判满：

• 队空：sq.rear==sq.front；
• 队满：(sq.rear+1)% maxsize == sq.front（避免与队空混淆）

用size记录元素个数，无需牺牲空位，因此数组大小为 m 时，最多容纳 m 个元素

前序（根左右），后序（左右根）。若相反，只有（根左）或（根右），树退化为线性结构。

中序序列是升序，因此是二叉搜索树

最终排序结果（作为判断标准）

先对原序列（默认是选项的公共元素集合）进行完全排序，得到最终序列：[2, 5, 12, 16, 28, 32, 60, 72]后续判断每个选项中，满足 “左右元素都有序” 的基准数量是否≥3。

如果第一趟的位置在两端，则第二趟只能定一个位置，否则可以定两个位置

二分查找的最坏比较次数 = 二叉判定树的高度（查找失败时，需走到叶子结点的下一层）。

折半查找的判定树是严格的二叉平衡树（左子树和右子树的高度差不超过 1，且结点分布符合 “中间元素为根” 的规则）

折半查找整个算法中，关于mid的取值向上/向下需要统一。
如果待查找序列中节点总数是偶数，计算mid值的时候一定涉及向上/向下取值问题。

向下取整：如果待查找序列中节点总数是偶数，且向下取整，那么mid作为排序树的根节点，它的左子树中节点总数一定比右子树中节点总数小1。
如果待查找序列中节点总数是2，且向下取整，mid一定是其中较小的那一个，剩下的的那一个节点变成mid的右子树
向上取整：同理，如果待查找序列中节点总数是偶数，且向上取整，那么mid作为排序树的根节点，它的左子树中节点总数一定比右子树中节点总数大1。
如果待查找序列中节点总数是2，且向上取整，mid一定是其中较大的那一个，剩下的的那一个节点变成mid的左子树

判定树分析：$n=10$ 的判定树高度为 $\lfloor \log_2 10 \rfloor + 1 = 4$。查找不成功会落到外部结点。在判定树中，外部结点的层数为 $h$ 或 $h-1$。因此，查找不成功最少需要 $4-1=3$ 次比较，最多 4 次。

• I 正确：叶结点删除 / 插入可能改变树结构（如删除后平衡调整，插入位置不同）；
• II 错误：非叶结点删除 + 插入，可能恢复原结构；
• III 错误：非叶结点操作后结构可能不同。

哈希表理想情况下平均查找长度为 O (1)，与结点数无关

平均查找长度取决于冲突解决策略和装填因子，无固定复杂度（理想 O (1)，最坏 O (N)）。

• 比较次数：1+2+…+9=45（最坏情况）；
• 移动次数：比较次数 - 1=44（直接插入排序移动次数 = 比较次数 - 1）

要保证任何情况都连通，需考虑 “最极端的非连通情况” 的边数上限，再加 1 条边即可。

• 最极端的非连通情况：9 个顶点构成完全图，剩余 1 个孤立顶点
• 再加 1 条边，就能让孤立顶点与完全图连通，此时无论如何都不会非连通。

• 核心思路：要让连通分量的数量最大，我们应该尽可能让更多的顶点成为孤立点（即每个点自己就是一个连通分量）。为此，我们需要将所有的 17 条边尽可能集中在最少数量的顶点上

• A. (V0, V2)：V0 是 V2 的祖先（爷爷），这是回边，可能存在。

• B. (V0, V6)：V0 是 V6 的祖先，这是回边，可能存在。

• D. (V4, V6)：V4 是 V6 的祖先（爷爷），这是回边，可能存在。

• C. (V1, V5)：V1 在左分支，V5 在右分支。如果这条边存在，当 DFS 访问到 V1 时，V5 还是未访问状态，DFS 会直接走 (V1, V5) 这条路，导致 V5 成为 V1 的孩子。但在给定的边集合中，V5 是 V4 的孩子（即必须等 V1 那边回溯完了，回到 V0，再走 V4 才能到 V5）。这说明 V1 和 V5 之间不可能有直接连边。