博客详情 - Bitworld OJ

bitworld 的博客
【CSP-算法】普及组知识点
bitworld 最强壮的男人 SU @ 2025-4-26 10:52:42

整型数据类型：如何声明 int 类型的变量并进行赋值和运算。
浮点型数据类型：如 float 和 double，了解精度和常见误差。
字符型数据类型：char 类型的使用及 ASCII 编码的基本知识。
布尔型数据类型：bool 类型，常用于逻辑判断，值为 true 和 false。
算术运算符：+、-、*、/、% 的使用，特别是整数除法和取模运算的细节。
赋值运算符：=、+=、-=、*=、/= 等复合赋值运算符。
关系运算符：==、!=、>、<、>=、<= 的使用，常用于条件判断。
逻辑运算符：&&（与）、||（或）、!（非）的组合应用。
位运算符：&、|、^、~、<<、>>，了解基本的二进制位操作。
条件判断：if 语句的基本结构和使用场景。
多分支判断：if-else if-else 的多分支选择逻辑。
switch 语句：在多种情况选择中使用，尤其是常量枚举的选择。
for 循环：循环控制结构的使用，掌握基本的迭代方式。
while 循环：基于条件的循环控制，理解退出条件。
do...while 循环：至少执行一次的循环结构，常见于输入验证。
循环中的控制语句：break 和 continue 的用法，分别用于跳出循环和跳过某次迭代。
数组的定义和初始化：一维数组的声明、初始化和元素访问。
二维数组：二维数组的定义和遍历方式，应用于矩阵类问题。
字符串的定义：字符数组、字符串的基本操作，包括声明、初始化和输出。
字符串操作函数：如 strlen、strcpy、strcmp 等标准库函数的使用。
字符串拼接：使用 strcat 拼接两个字符串。
字符串比较：用 strcmp 比较两个字符串的字典顺序。
字符操作：字符的 ASCII 值转换和简单字符操作，如 toupper 和 tolower。
输入输出操作：scanf 和 printf 的格式控制，尤其是多变量输入输出。
格式化输出：控制输出的小数点位数、宽度对齐等格式。
输入输出重定向：如何从文件读取输入和输出到文件，使用 freopen。
常量定义：#define 宏和 const 关键字定义常量。
递归函数：递归的定义及其在解决问题中的应用，如汉诺塔问题、斐波那契数列。
函数定义与调用：如何定义函数，传递参数，并获取返回值。
函数的参数传递：值传递与引用传递的区别。
全局变量与局部变量：变量的作用域及生命周期。
指针的基础概念：指针的定义、初始化及其与数组的关系。
指针运算：指针的加减运算和指向的值的访问。
动态内存分配：使用 malloc 和 free 动态分配和释放内存。
结构体：struct 的定义和使用，创建复杂数据类型。
结构体数组：如何声明结构体数组并操作其成员。
枚举类型：enum 的使用，定义一组命名的常量。
时间复杂度：理解常见算法的时间复杂度，如 O(1)、O(n)、O(n^2) 等。
空间复杂度：分析算法的空间使用情况。
排序算法：掌握冒泡排序、选择排序和插入排序的基本原理和实现。
二分查找：在有序数组中实现二分查找的算法，时间复杂度 O(log n)。
线性查找：无序数组中的遍历查找算法，时间复杂度 O(n)。
冒泡排序的优化：理解如何通过提前终止条件优化冒泡排序。
选择排序的实现：基本选择排序的原理与实现步骤。
插入排序的实现：了解插入排序的基本原理，适合小规模数组的排序。
堆排序：理解二叉堆结构，学习如何进行堆排序，时间复杂度 O(n log n)。
递归与回溯：掌握基本递归思想，理解回溯算法的应用，如八皇后问题。
动态规划基础：理解分治思想，掌握简单的动态规划问题，如斐波那契数列优化。
贪心算法：解决最优子结构问题的贪心策略，如最小硬币找零问题。
图的基本表示：掌握邻接矩阵和邻接表表示法，并理解其优缺点。
冒泡排序的时间复杂度：最坏情况下冒泡排序的时间复杂度为 O(n²)，最好情况下为 O(n)（数组已经有序时）。
选择排序的时间复杂度：无论数组是否有序，选择排序的时间复杂度始终为 O(n²)。
插入排序的时间复杂度：最坏情况下为 O(n²)，最优情况下（数组已经有序）为 O(n)。
堆排序的时间复杂度：在平均和最坏情况下，堆排序的时间复杂度为 O(n log n)。
二分查找的前提条件：数组必须是有序的，时间复杂度为 O(log n)。
线性查找的时间复杂度：无序数组中的查找，时间复杂度为 O(n)。
快速排序的时间复杂度：平均时间复杂度为 O(n log n)，最坏情况下（每次分割点最偏向一侧）为 O(n²)。
归并排序的时间复杂度：归并排序的时间复杂度为 O(n log n)，且空间复杂度为 O(n)。
递归的时间复杂度分析：如斐波那契数列的递归解法，时间复杂度为 O(2^n)，应避免直接使用递归计算大规模斐波那契数。
动态规划的时间复杂度：如斐波那契数列的动态规划解法时间复杂度为 O(n)，通过记录已计算结果避免重复计算。
最大子序和问题：利用动态规划解决最大连续子序和问题，时间复杂度为 O(n)。
贪心算法应用：如求解最小硬币找零问题，通过贪心算法选择面值最大的硬币，时间复杂度为 O(n)。
深度优先搜索（DFS）：使用递归或栈实现的图遍历算法，时间复杂度为 O(V+E)（V 为顶点数，E 为边数）。
广度优先搜索（BFS）：使用队列实现的图遍历算法，时间复杂度为 O(V+E)。
最短路径算法：Dijkstra 算法的时间复杂度为 O(E + V log V)，使用优先队列可以优化算法效率。
邻接矩阵：图的表示法之一，空间复杂度为 O(V²)，适用于稠密图。
邻接表：图的另一种表示法，空间复杂度为 O(V+E)，适用于稀疏图。
回溯算法的时间复杂度：如八皇后问题，时间复杂度为 O(n!)。
哈希表的时间复杂度：哈希表在理想情况下查找、插入和删除操作的时间复杂度为 O(1)。
哈希冲突解决方法：使用开放地址法或链地址法解决哈希冲突问题。
字符串哈希：通过将字符串映射为一个哈希值，常用于字符串匹配问题，时间复杂度为 O(n)。
字符串匹配算法：如 KMP 算法，时间复杂度为 O(n + m)，n 为文本长度，m 为模式长度。
栈的基本操作：栈的 push（入栈）、pop（出栈）、top（获取栈顶元素）操作，时间复杂度均为 O(1)。
队列的基本操作：队列的 enqueue（入队）、dequeue（出队）、front（获取队头元素）操作，时间复杂度均为 O(1)。
链表的操作：单向链表的插入、删除、遍历操作，时间复杂度为 O(n)。
双向链表的操作：双向链表支持从两端操作，插入、删除和遍历的时间复杂度仍为 O(n)。
优先队列：基于堆实现的优先队列，插入元素和取出最小（或最大）元素的时间复杂度为 O(log n)。
二叉搜索树（BST）：查找、插入和删除的平均时间复杂度为 O(log n)，最坏情况为 O(n)（当树退化为链表时）。
平衡二叉树：如 AVL 树和红黑树，插入、删除和查找的时间复杂度均为 O(log n)。
Trie 树：用于高效存储和查找字符串的树结构，时间复杂度为 O(m)（m 为字符串长度）。
动态数组：如 vector，插入、删除和访问的时间复杂度分别为 O(n)、O(n) 和 O(1)。
常用排序函数：了解 C++ 中的 sort 函数，时间复杂度为 O(n log n)。
随机数生成：使用 rand() 生成伪随机数，理解伪随机数生成的原理和范围控制。
浮点数精度误差：理解浮点数运算的精度问题，如浮点数比较时要考虑误差（如 fabs(a - b) < 1e-9）。
整除和模运算：掌握取整和取模操作的应用场景，特别是在循环、序列计算中。
递归深度限制：理解递归调用时的栈深度限制，避免递归过深导致的栈溢出。
动态规划的记忆化搜索：通过保存已经计算过的状态来优化递归算法，避免重复计算。
最大公约数（GCD）：使用欧几里得算法（辗转相除法）求解两个数的最大公约数，时间复杂度为 O(log(min(a, b)))。
最小公倍数（LCM）：通过 LCM(a, b) = (a * b) / GCD(a, b) 计算最小公倍数。
质数判断：简单的质数判断算法时间复杂度为 O(√n)。
埃拉托色尼筛法：高效求解 n 以内所有质数的算法，时间复杂度为 O(n log log n)。
乘法逆元：在模运算中，乘法逆元可以通过扩展欧几里得算法计算。
模运算：掌握大数运算时如何使用模运算（如取模避免溢出）。
位运算的应用：如判断奇偶数（n & 1）、快速计算 2 的幂次（1 << k）等。
位掩码：使用位运算处理多个布尔值的组合问题，如集合的子集生成。
斐波那契数列的矩阵快速幂：使用矩阵快速幂方法求解斐波那契数列，时间复杂度为 O(log n)。
求和公式：掌握常用的求和公式，如等差数列求和、等比数列求和。
组合数学基础：如组合数 C(n, k) 的计算公式，以及如何使用动态规划或递归计算组合数。
排列与组合：掌握排列 A(n, k) 和组合 C(n, k) 的基本概念及应用。
素数分解：将一个数分解为质数因子的算法，时间复杂度为 O(√n)。
求 n!（阶乘）：通过循环或递归计算 n!，了解其时间复杂度为 O(n)。
阶乘尾零的计算：通过计算阶乘中有多少个 10 的倍数，进一步拆解为 2 和 5 的因子对数。
斐波那契数列的迭代法：通过迭代计算斐波那契数列，时间复杂度为 O(n)，并避免递归造成的栈溢出问题。
大数相加：实现多个大整数的加法，可以使用字符串处理模拟大数相加。
大数相乘：使用类似竖式的算法模拟大数相乘，时间复杂度为 O(n*m)，其中 n 和 m 为两个数的位数。
数位和：给定一个整数，计算其各位数字之和，通常通过取模和整除操作实现。
位逆序：将一个数的二进制表示反转，如将 1101 变成 1011，常用于位运算题。
欧拉函数：计算小于 n 且与 n 互质的整数个数，理解其与质数的关系。
前缀和：常用于高效计算数组的某一段区间和，时间复杂度为 O(1)（预处理时间为 O(n)）。
差分数组：用于快速处理区间加减操作，差分数组在区间修改时可以实现 O(1) 时间复杂度。
哈夫曼编码：一种用于数据压缩的贪心算法，通过构建最优前缀码来编码字符，常用于压缩问题。
排列的字典序：给定一个排列，求下一个字典序排列的算法（next permutation）。
ST表：用于解决静态区间最值查询问题，时间复杂度为 O(n log n) 预处理，查询时间复杂度为 O(1)。
倍增法：常用于解决 LCA（最近公共祖先）问题，或加速二分查找过程，时间复杂度为 O(log n)。
并查集：一种用于动态连通性问题的算法，支持合并集合和判断两个元素是否在同一集合中，时间复杂度为 O(α(n))。
路径压缩优化的并查集：通过路径压缩和按秩合并，优化并查集的性能。
拓扑排序：用于有向无环图（DAG）中的顶点排序，常用于任务调度问题，时间复杂度为 O(V + E)。
Kruskal 最小生成树算法：基于边权排序和并查集的最小生成树算法，时间复杂度为 O(E log E)。
Prim 最小生成树算法：基于贪心策略的最小生成树算法，适用于稠密图，时间复杂度为 O(V²) 或 O(V log V + E)。
Bellman-Ford 算法：用于解决带负权边的单源最短路径问题，时间复杂度为 O(VE)。
Floyd-Warshall 算法：用于解决任意两点之间的最短路径问题，时间复杂度为 O(V³)。
堆的基本操作：了解如何插入、删除堆顶元素、维护最小（或最大）堆的结构，时间复杂度为 O(log n)。
优先队列中的堆实现：C++ 中的 priority_queue 实现堆操作，适用于动态选择最大值或最小值。
多重背包问题：在 0-1 背包问题的基础上，考虑每种物品的数量限制，使用动态规划解决，时间复杂度为 O(nW)。
完全背包问题：每种物品可以选无限次的背包问题，时间复杂度为 O(nW)，W 为背包容量。
记忆化搜索：结合递归和缓存技术，避免重复计算子问题，常用于优化递归算法。
最长递增子序列（LIS）：通过动态规划或二分查找优化求解，时间复杂度分别为 O(n²) 和 O(n log n)。
滑动窗口：用于高效处理数组中的区间问题，时间复杂度为 O(n)。
双指针法：用于高效处理数组中的特定问题，如有序数组的两数和问题，时间复杂度为 O(n)。
最长公共子序列（LCS）：使用动态规划解决最长公共子序列问题，时间复杂度为 O(nm)。
0-1 背包问题：动态规划解法，时间复杂度为 O(nW)，n 为物品数，W 为背包容量。
二维数组的动态规划：如最小路径和问题（从左上角到右下角），时间复杂度为 O(mn)。
状态压缩动态规划：通过二进制压缩状态信息，常用于 TSP（旅行商）等问题，时间复杂度为 O(n²2ⁿ)。
数位 DP：用于处理数位上的问题，如统计满足特定条件的数，常结合递归和动态规划。
莫队算法：用于离线查询问题，如区间众数查询，时间复杂度为 O((n + q)√n)，q 为查询次数。
差分约束系统：解决一类带约束的最短路径问题，常用于时间规划和调度问题。
Trie树的动态插入与查询：用于字符串集合的存储和快速查询，插入和查询时间复杂度均为 O(k)，k 为字符串长度。
位操作实现集合子集遍历：通过位操作遍历集合的所有子集，时间复杂度为 O(2ⁿ)，n 为集合元素个数。
布隆过滤器：通过多个哈希函数实现高效判断元素是否存在，允许一定的误判率。
线性筛法：用于高效求解 n 以内的所有质数，时间复杂度为 O(n)。
最大流问题：通过网络流模型求解最大流，使用 Edmonds-Karp 算法实现，时间复杂度为 O(VE²)。
二分图匹配：使用匈牙利算法解决二分图中的最大匹配问题，时间复杂度为 O(VE)。
KMP 字符串匹配算法：通过构建部分匹配表（前缀函数）实现快速字符串匹配，时间复杂度为 O(n+m)。
Manacher 算法：用于在 O(n) 时间内求解字符串中的最长回文子串。
动态开点线段树：用于动态维护区间操作，时间复杂度为 O(log n)。
线段树的区间修改与查询：常用于处理动态区间查询问题，时间复杂度为 O(log n)。
树状数组的单点更新与区间查询：用于解决区间和问题，时间复杂度为 O(log n)。
笛卡尔积问题：通过枚举两个集合中的元素对，时间复杂度为 O(n²)。
组合数学中的鸽巢原理：用于证明在特定条件下必定存在某种结果，常用于计数问题。
容斥原理：用于解决涉及多个集合的计数问题，计算多个事件的并集个数。
并查集的路径压缩：通过路径压缩提高并查集的效率，时间复杂度接近 O(1)。
按秩合并优化的并查集：在合并两个集合时总是将规模较小的集合合并到较大的集合中，优化效率。
LCA（最近公共祖先）：通过倍增法或 Tarjan 算法解决树中两个节点的最近公共祖先问题，时间复杂度为 O(log n) 或 O(n)。
矩阵的转置：将矩阵的行和列互换，常用于图像处理或线性代数问题。
矩阵快速幂：用于快速求解矩阵的高次幂，时间复杂度为 O(n³ log k)，适用于斐波那契数列的快速计算。
高斯消元法：求解线性方程组的算法，时间复杂度为 O(n³)，常用于解方程和矩阵问题。
最小二乘法：用于解决拟合直线的问题，通过最小化误差平方和来找到最佳拟合直线。
叉积和点积：在二维或三维空间中使用向量叉积和点积计算面积、体积或角度。
凸包问题：通过 Graham 扫描或 Jarvis 步进法构建平面上的凸包，时间复杂度为 O(n log n)。
动态凸包维护：通过数据结构动态维护一组点的凸包，适用于实时更新点集的几何问题。
线性规划：通过单纯形法或内点法求解线性规划问题，常用于优化问题。
最大公约数和最小公倍数：使用辗转相除法（欧几里得算法）计算两个数的最大公约数和最小公倍数。
扩展欧几里得算法：用于解不定方程 ax + by = gcd(a, b) 的整数解，常用于计算乘法逆元。
阶乘的素因子分解：计算 n! 中包含的某个素数的幂次，常用于组合数学问题。
高精度乘法：通过模拟竖式乘法实现大数相乘，常用于解决乘积超出常规数据类型范围的问题。
高精度除法：通过模拟竖式除法实现大数除法，解决超大整数的整除运算。
快速排序的随机化优化：通过随机选择枢轴元素，避免最坏情况下的 O(n²) 时间复杂度。
三路快排：对数组中含有大量重复元素的情况进行优化，时间复杂度为 O(n log n)。
希尔排序：基于插入排序的改进版，通过逐步减小步长的插入排序提高效率，时间复杂度为 O(n log² n)。
桶排序：用于分布范围较为均匀的数列，时间复杂度为 O(n + k)。
基数排序：通过逐位比较进行排序，适用于非负整数的排序，时间复杂度为 O(nk)，k 为整数位数。
计数排序：适用于整数范围较小的情况，时间复杂度为 O(n + k)，k 为整数的最大值。
弗洛伊德环检测算法：检测链表中是否存在环，并找到环的起点，时间复杂度为 O(n)。
双向广度优先搜索：在图的搜索中同时从起点和终点开始搜索，减少搜索空间，时间复杂度为 O(b^(d/2))，其中 b 是分支因子，d 是搜索深度。
双端队列（Deque）：一种允许从两端插入和删除元素的队列，常用于滑动窗口问题。
STL 容器的使用：了解 C++ 中常用的 STL 容器，如 vector、map、set、stack、queue 等，掌握其基本操作和时间复杂度。
动态数组扩容机制：了解动态数组（如 vector）的自动扩容机制及其对时间复杂度的影响，摊还时间复杂度为 O(1)。
链表与数组的区别：链表的插入和删除时间复杂度为 O(1)，但访问时间复杂度为 O(n)，而数组的随机访问时间复杂度为 O(1)。
环形链表：通过设置链表的尾节点指向头节点构成环形链表，常用于循环调度问题。
栈的应用：如使用栈解决括号匹配问题，或者在递归问题中模拟系统调用栈。
单调栈：用于解决某些区间问题，如求数组中每个元素右边第一个比它大的元素，时间复杂度为 O(n)。
单调队列：用于求解滑动窗口的最值问题，时间复杂度为 O(n)。
线性探测法：处理哈希冲突的一种方式，在发生冲突时线性探测下一个空闲位置。
二次探测法：处理哈希冲突的一种方式，通过二次探测来避免聚集冲突。
二分法的实际应用：如在数列中查找满足某条件的最小值或最大值。
以空间换时间的技巧：通过预处理存储中间结果来提高查询效率，如使用前缀和数组或缓存递归结果。
整数拆分问题：将一个整数拆分为若干个正整数之和的方案数，使用动态规划解决。
最大矩形面积问题：在一个二维矩阵中找出只包含 1 的最大矩形面积，时间复杂度为 O(nm)。
最大正方形问题：求二维矩阵中只包含 1 的最大正方形面积，时间复杂度为 O(nm)。
子集和问题：判断给定的集合中是否存在一个子集，其元素之和等于给定值，使用动态规划解决。
数独解题：使用回溯算法解决数独问题，理解剪枝技巧的应用。
八皇后问题：使用回溯算法在 8x8 的棋盘上放置 8 个皇后，使它们互相不能攻击，时间复杂度为 O(n!)。
最小编辑距离：通过动态规划求解两个字符串的最小编辑距离，时间复杂度为 O(nm)。
分治法：将问题分成若干子问题，分别解决后合并子问题的解，适用于求解大规模问题，如归并排序。
分治法的递归树分析：通过递归树分析分治算法的时间复杂度，如 T(n) = 2T(n/2) + O(n) 的时间复杂度为 O(n log n)。
最大流 Dinic 算法：一种求解最大流问题的高效算法，时间复杂度为 O(V²E)。
可持久化数据结构：如可持久化线段树，支持查询历史版本的操作，时间复杂度为 O(log n)。
K-D 树：一种用于解决多维空间最近邻查询问题的数据结构，时间复杂度为 O(log n)。
线性基：用于解决位运算问题，如求解最大异或和，时间复杂度为 O(n)。
位图：一种高效的存储大量布尔值的数据结构，适用于处理大规模数据集合。
组合数公式：组合数 C(n, k) 的公式为 C(n, k) = n! / (k! * (n - k)!)，可以用于计算从 n 个元素中选取 k 个元素的方案数。
组合数的递推关系：组合数可以通过递推公式 C(n, k) = C(n-1, k-1) + C(n-1, k) 进行计算，常用于动态规划。
组合数的递归计算：可以通过递归实现组合数的计算，但效率较低，通常用于小规模问题。
杨辉三角（帕斯卡三角形）：利用动态规划构建杨辉三角，可以在 O(n²) 时间内计算出所有组合数。
快速计算组合数：通过预处理阶乘和逆元数组，可以在 O(1) 时间内计算组合数，预处理时间为 O(n)。
组合数取模：由于组合数值很大，常需要将其结果对一个大质数取模，通常使用费马小定理来处理除法取模问题。
排列数 A(n, k)：排列数公式 A(n, k) = n! / (n - k)!，表示从 n 个元素中选取 k 个排列的方案数。
全排列生成：使用递归或 STL 的 next_permutation 函数生成一个数组的所有全排列，时间复杂度为 O(n!)。
重复元素的排列：处理包含重复元素的全排列时，需要去重，可以通过排序加跳过相同元素实现。
组合的生成：利用递归或二进制枚举的方法生成从 n 个元素中选取 k 个元素的所有组合，时间复杂度为 O(C(n, k))。
与运算（&）：a & b 是按位与运算，结果是两个数对应位上都为 1 时取 1，否则取 0，常用于掩码操作。
或运算（|）：a | b 是按位或运算，结果是两个数对应位上有一个为 1 时取 1，常用于合并标志位。
异或运算（^）：a ^ b 是按位异或运算，结果是对应位上不相同时取 1，相同时取 0，常用于交换两个变量或找出不成对的数。
取反运算（~）：~a 是按位取反运算，将 a 的所有位都取反，1 变 0，0 变 1。
左移运算（<<）：a << b 是将 a 的二进制表示左移 b 位，等价于 a 乘以 2 的 b 次方，时间复杂度为 O(1)。
右移运算（>>）：a >> b 是将 a 的二进制表示右移 b 位，等价于 a 除以 2 的 b 次方，时间复杂度为 O(1)。
快速计算 2 的幂：通过左移运算可以快速计算 2 的幂，如 1 << n 表示 2 的 n 次方。
判断奇偶性：通过 n & 1 可以判断 n 是奇数还是偶数，1 表示奇数，0 表示偶数。
清除最低位的 1：n & (n - 1) 可以快速清除 n 的二进制表示中最低位的 1，常用于统计二进制中 1 的个数。
二进制中 1 的个数：通过不断使用 n & (n - 1) 可以在 O(log n) 时间内统计 n 的二进制表示中 1 的个数。
位掩码：通过与运算和或运算，可以使用位掩码来处理多个布尔变量，常用于状态压缩。
二进制枚举：利用二进制数的位来表示选取的元素，可以用来枚举所有子集，时间复杂度为 O(2ⁿ)，n 为集合大小。
交换两个变量：使用异或运算 a = a ^ b; b = a ^ b; a = a ^ b; 可以在不使用临时变量的情况下交换 a 和 b。
取二进制的某一位：(a >> k) & 1 可以得到 a 的二进制表示中第 k 位的值（0 或 1）。
设置二进制的某一位：a | (1 << k) 可以将 a 的二进制表示中的第 k 位设置为 1。
清除二进制的某一位：a & ~(1 << k) 可以将 a 的二进制表示中的第 k 位设置为 0。
翻转二进制的某一位：a ^ (1 << k) 可以将 a 的二进制表示中的第 k 位取反。
位运算加法：使用 a ^ b（不进位加法）和 (a & b) << 1（进位）可以模拟二进制加法。
位运算乘法：通过位移和加法，可以模拟二进制乘法，如 a << 1 等价于 a * 2。
位运算除法：通过右移可以模拟二进制除法，如 a >> 1 等价于 a / 2。
二叉树的定义：二叉树是一种每个节点最多有两个子节点的数据结构，分别称为左子节点和右子节点。
二叉树的遍历：包括前序遍历（根-左-右）、中序遍历（左-根-右）和后序遍历（左-右-根），可以递归或迭代实现。
二叉树的层次遍历：通过使用队列实现二叉树的层次遍历（广度优先遍历），每次访问一层的节点。
满二叉树：如果一棵二叉树的所有节点都有 0 或 2 个子节点，并且所有叶节点都在同一层，则称为满二叉树。
完全二叉树：完全二叉树的每一层除了最后一层是满的，并且最后一层的节点从左到右连续排列。
平衡二叉树：一种特殊的二叉树，要求左右子树的高度差不能超过 1，常用于提高查找效率。
二叉搜索树（BST）：一种特殊的二叉树，满足每个节点的左子树的值都小于该节点的值，右子树的值都大于该节点的值。
二叉搜索树的查找：在二叉搜索树中查找某个值的时间复杂度为 O(log n)，最坏情况下为 O(n)。
二叉搜索树的插入：向二叉搜索树中插入一个新值，时间复杂度为 O(log n)，最坏情况下为 O(n)。
二叉搜索树的删除：在二叉搜索树中删除某个节点，分为删除叶子节点、单子树节点和双子树节点三种情况。
二叉搜索树的最小值和最大值：二叉搜索树中最小值位于最左边的节点，最大值位于最右边的节点。
二叉搜索树的中序遍历结果：二叉搜索树的中序遍历结果是一个升序排列的序列。
二叉树的高度：通过递归或迭代计算二叉树的高度，时间复杂度为 O(n)。
二叉树的最大路径和：利用递归计算二叉树中任意两节点之间的最大路径和，时间复杂度为 O(n)。
二叉树的深度：通过递归或迭代计算二叉树的深度，时间复杂度为 O(n)。
平衡二叉树的判定：通过递归检查每个节点的左右子树高度差是否超过 1，时间复杂度为 O(n)。
AVL树：一种自平衡二叉搜索树，通过旋转操作保持树的平衡，插入和删除的时间复杂度为 O(log n)。
红黑树：一种近似平衡的二叉搜索树，红黑树的插入、删除和查找的时间复杂度均为 O(log n)。
堆：堆是一棵完全二叉树，分为最大堆（每个节点的值大于等于子节点）和最小堆（每个节点的值小于等于子节点），常用于优先队列。
堆的插入和删除：在堆中插入一个新元素或删除堆顶元素，时间复杂度为 O(log n)。

计算机网络

OSI 七层模型：包括物理层、数据链路层、网络层、传输层、会话层、表示层和应用层，各层负责的功能不同。
TCP/IP 模型：分为四层，包括网络接口层、网络层、传输层和应用层，是互联网通信的基础协议。
IP 地址：用于唯一标识网络中的每一台主机，分为 IPv4 和 IPv6，IPv4 是 32 位地址，IPv6 是 128 位地址。
IPv4 地址分类：包括 A 类、B 类、C 类、D 类和 E 类，分别用于不同规模的网络。
子网掩码：用于划分网络中的子网，常见的子网掩码如 255.255.255.0 表示前 24 位为网络部分。
DHCP 协议：动态主机配置协议，用于自动为设备分配 IP 地址。
NAT（网络地址转换）：用于在路由器或防火墙上将私有 IP 地址转换为公有 IP 地址，以便多个设备通过一个公共 IP 地址访问互联网。
DNS（域名系统）：用于将域名解析为 IP 地址，常见的 DNS 服务器如 Google 的 8.8.8.8。
TCP（传输控制协议）：一种面向连接的、可靠的传输协议，提供数据包的顺序传输和确认机制。
UDP（用户数据报协议）：一种无连接的、不可靠的传输协议，常用于实时通信、视频流等场景。
TCP 三次握手：建立 TCP 连接的过程，客户端和服务器之间通过 SYN 和 ACK 报文进行三次通信。
TCP 四次挥手：断开 TCP 连接的过程，通过 FIN 和 ACK 报文进行四次通信。
流量控制：TCP 使用窗口机制进行流量控制，防止发送方发送过多数据超出接收方的处理能力。
拥塞控制：TCP 的拥塞控制机制通过慢启动、拥塞避免、快速重传和快速恢复来避免网络拥塞。
HTTP 协议：超文本传输协议，用于 Web 浏览器与服务器之间的通信，常用端口号为 80。
HTTPS 协议：在 HTTP 协议的基础上增加了 SSL/TLS 加密，提供安全的数据传输，常用端口号为 443。
SSL/TLS 协议：用于加密网络通信，确保数据在传输过程中不被窃听和篡改。
FTP 协议：文件传输协议，用于在客户端和服务器之间传输文件，常用端口号为 21。
SMTP 协议：简单邮件传输协议，用于发送电子邮件，常用端口号为 25。
POP3 和 IMAP 协议：用于接收电子邮件，POP3 常用端口号为 110，IMAP 常用端口号为 143。
DNS 解析流程：浏览器向 DNS 服务器发送查询请求，DNS 服务器返回对应的 IP 地址。
ICMP 协议：用于发送网络诊断和错误消息，常见应用如 ping 和 traceroute。
ping 命令：用于测试主机之间的网络连通性，基于 ICMP 协议。
traceroute 命令：用于显示数据包在网络中经过的路由节点，帮助诊断网络问题。
ARP 协议：地址解析协议，用于将 IP 地址映射为物理地址（MAC 地址），在局域网中使用。
MAC 地址：网卡的物理地址，是全球唯一的，通常由 48 位二进制数表示。
交换机的工作原理：交换机工作在数据链路层，用于在局域网中转发数据包，根据 MAC 地址进行转发。
路由器的工作原理：路由器工作在网络层，用于在不同的网络之间转发数据包，根据 IP 地址进行路由选择。
路由表：路由器用于选择下一跳路由的表格，包含网络目标、子网掩码、网关和接口等信息。
默认网关：当数据包的目标 IP 地址不在当前子网内时，发送到默认网关，由其转发到其他网络。
防火墙：网络安全设备，用于监控和控制进出网络的流量，根据预定义的规则允许或阻止流量。
代理服务器：中介服务器，客户端通过代理服务器访问其他服务器，常用于缓存和隐藏 IP 地址。
负载均衡：通过分发网络流量到多个服务器上，提升服务的可靠性和性能。
VPN（虚拟专用网络）：通过加密隧道技术，允许用户安全地通过公共网络访问私有网络。
数据包的结构：数据包包含头部（header）和数据部分，头部包含源 IP、目标 IP、源端口、目标端口等信息。
MTU（最大传输单元）：在网络上传输的最大数据包大小，常见的 MTU 值为 1500 字节。
数据包的分片与重组：当数据包的大小超过 MTU 时，需要进行分片，接收方负责将分片的数据包重新组装。
粘包与拆包：在 TCP 协议中，由于数据流的连续性，可能会出现粘包或拆包现象，常通过增加头部信息或定长包处理。

操作系统

操作系统的功能：操作系统负责管理硬件资源、提供用户接口、控制程序执行，并进行文件系统管理。
进程和线程的区别：进程是程序的运行实例，线程是进程中的最小执行单位，多个线程共享同一进程的资源。
进程的状态：进程有三种主要状态：就绪状态、运行状态和等待状态。
进程调度算法：包括先来先服务（FCFS）、短作业优先（SJF）、优先级调度和轮转调度（RR）等。
线程的创建与终止：线程可以通过 pthread_create（Linux）或 CreateThread（Windows）创建，执行完成后会自动终止。
多线程的并发与并行：并发是指多个线程交替执行，并行是指多个线程同时执行，后者需要多核 CPU 支持。
死锁：当多个进程或线程互相等待对方释放资源，导致所有进程都无法继续执行，形成死锁。
死锁的必要条件：互斥、持有并等待、不可抢占、循环等待。
死锁的解决方法：可以通过预防、避免、检测和解除死锁来解决，如银行家算法用于避免死锁。
内存管理：包括分段和分页管理方式，用于有效利用物理内存，防止内存碎片。
虚拟内存：通过页表将物理内存与虚拟地址空间映射，使得程序可以使用比实际物理内存更大的内存空间。
分页机制：操作系统将内存划分为等大小的页（page）和页框（frame），通过页表管理内存的分配。
页面置换算法：用于决定当内存不足时应将哪一页调出内存，包括 FIFO、LRU 和 OPT 等算法。
文件系统的功能：负责文件的创建、删除、读写和权限管理，常见的文件系统如 FAT32、NTFS 和 EXT4。
I/O 管理：操作系统通过驱动程序管理设备 I/O 操作，提供缓冲、队列和设备独立性。
中断处理机制：操作系统通过中断处理程序响应硬件和软件的中断请求，确保程序的正常执行。
时钟中断：用于操作系统的定时调度和资源管理，周期性地触发进程调度。
文件的权限管理：通过读、写、执行权限控制用户对文件的访问，Linux 中常用的权限表示为 rwx。
进程间通信（IPC）：包括管道（pipe）、消息队列、共享内存和信号量，用于进程之间的数据交换。
信号量：用于解决多进程或多线程的同步与互斥问题，常用于实现生产者-消费者模型。
自旋锁：一种用于多线程同步的锁机制，线程在等待锁时不会进入睡眠，而是忙等待。
条件变量：用于线程之间的同步，线程可以在条件变量上等待特定条件满足后继续执行。
信号机制：操作系统通过信号通知进程某些事件的发生，进程可以捕获和处理信号，如 SIGINT、SIGKILL 等。
页表的多级结构：为了减少页表的存储开销，使用多级页表，每一级页表都只存储部分虚拟地址空间的映射关系。
硬链接和软链接：硬链接是指向文件数据的多个目录项，软链接是指向另一个文件路径的符号链接。
优先级反转：低优先级的进程占有资源而高优先级进程等待，可能会导致优先级反转问题。
分时系统：通过时间片轮转的方式为每个用户分配 CPU 使用权，提高系统响应能力。

【CSP-算法】普及组知识点

计算机网络

操作系统

还没有账户？

登录