一、核心知识点 邻接矩阵与图结构： 设节点编号为 \(v_0, v_1, \dots, v_{n-1}\)，邻接矩阵中 主对角线以下元素全为 0（即 \(i > j\) 时，\(A[i][j] = 0\)），意味着 边只能从编号...

详细知识点 广度优先遍历（BFS）逻辑： 需 访问每个节点（入队、出队标记），并 遍历每个节点的邻接边（确定后续节点）。 邻接表存储的开销： 节点层面：共 n 个节点，每个节点入队、出队各一次，操作总时间为 O(n...

平衡因子定义： 平衡因子 = 左子树高度 − 右子树高度。本题中非叶节点平衡因子均为 1，故对任意非叶节点，左子树高度 = 右子树高度 + 1。 递归结构推导： 设高度为 h 的该平衡树节点数为 \(N(h)\)，递归关系如下： ...

左右孩子的相对顺序不能改变（先序和后序）

中缀表达式转后缀表达式 在计算机中，中缀表达式转后缀表达式 时需要借助一个栈，用于保存暂时还不能确定运算顺序的运算符。我们以 中缀表达式 A + B * (C - D) - E / F 转后缀表达式 为例，包含 +、-、*、/&nb...

一、双指针遍历法（高效定位第 n 小元素） ⑴ 基本设计思想 利用两个升序序列的有序性，通过 双指针同步遍历 直接定位第n小的元素（即中位数）：   定义指针 i、j 分别遍历序列 S1、S2，指针 k ...

第一种思路是 暴力枚举法，核心逻辑： 适用场景 图的顶点少（如本题 6 个顶点），从源点（0）到汇点（5）的路径数量有限，可手动枚举。 步骤 定位端点：确定源点（入度为 0，本题是顶点 0）和汇点（出度为 0，本题是顶点 5）。 枚举路径：列出所有从源点到汇点的简单...

要分析哈希表查找效率的优化措施，需结合 哈希表的核心概念（装填因子、哈希函数、冲突处理、堆积现象）逐一推导： 1. 概念回顾 装填因子 \(\alpha\)：\(\alpha = \frac{\text{已存元素数}}{\text{哈希表长度}}\)，反映表的 &l...

命题 Ⅰ：回路是简单路径 回路：起点和终点相同的路径（路径是顶点和边的序列）。 简单路径：路径中所有顶点互不重复的路径。   回路的起点和终点必然相同（顶点重复），因此回路不可能是简单路径。 → Ⅰ 错误。 命题 Ⅱ：存储稀疏图，用邻接矩阵比邻接表...

要判断哪个序列不可能是二叉排序树的查找路径，需依据二叉排序树的查找规则： 在查找过程中，从根节点开始，每个后续节点必须满足：   若比前一个节点小，则进入左子树，且后续所有节点都必须小于前一个节点； 若比前一个节点大，则进入右子树，且后续所有节点都必须大于前一个节点。 ...

核心知识点：树→二叉树的转换规则 树转二叉树时，遵循 “左孩子，右兄弟” 原则：   每个节点的 第一个子节点 成为二叉树的 左孩子； 每个节点的 相邻兄弟节点 成为二...

要解决完全二叉树叶节点个数的问题，需结合 完全二叉树的结构特性 和 二叉树的基本性质，步骤如下： 核心知识点回顾 完全二叉树的结构： 前 \(h-1\) 层是满二叉树（每层节点数达到最大值 \(2^{i-1}\)），第&n...

要解决这个问题，我们需要理解循环队列的基本原理，特别是队头（front）和队尾（rear）指针的初始状态与插入第一个元素后的关系。 核心知识点：循环队列的指针逻辑 循环队列是一种特殊的队列，其存储空间是一个首尾相连的数组（A [0..n-1]），通过取模运算实现 “循环&r...

要解决这道题，需结合CSMA/CD 协议原理、信号传播与数据传输的时间计算、以太网帧结构等知识点，以下是详细拆解： 一、问题 (1) 涉及的知识点与解析 核心知识点 CSMA/CD 协议的冲突检测机制： 当多个主机同时发送数据时，信号会在传输介质中碰撞（冲突），主机需...

问题（1）：逻辑地址对应页号的计算 整数：十进制整数 → [除R取余] → 逆序余数 → R进制整数 知识点：页式存储中页号与页内偏移的划分 页大小为 1KB = 2¹⁰ 字节，因此 页内偏移占 10 位，逻辑地址的高...

问题（1）涉及知识点 磁盘空闲块管理 - 位示图法 原理：通过连续二进制位映射磁盘块状态，1 位对应 1 个磁盘块，0标记空闲、1标记占用。 容量匹配：16384 个磁盘块需 16384 位；2KB = 2×1024×8 ...

一、Cache 基本结构与容量计算 假设 CPU 执行一条 “从内存加载数据到寄存器” 的指令（如 ld r1, [addr]）：   统一 Cache：CPU 既要从 Cache 取这条 ...

(1) 指令系统最多可有多少条指令？该计算机最多有多少个通用寄存器？存储器地址寄存器（MAR）和存储器数据寄存器（MDR）至少各需要多少位？（4分） 最多指令条数：指令操作码字段（OP）占4位（位15~12），因此最多可支持 24=1624=16 ...

我们需要设计一个算法，将一维数组 R 中的 n 个整数循环左移 P 个位置。例如，原始数组为 ⟨X0, X1, ..., Xn-1⟩，循环左移 P 个位置后变为 ⟨...