概述计算机结构 现代计算机模型是基于冯诺依曼结构 基本概念 操作系统 操作系统是一个大型的程序系统，负责计算机的全部软、硬资源的分配、调度工作，控制和协调并发活动，实现信息的存取和保护 提供用户接口，使用户获得良好的工作环境，操作系统使整个计算机系统实现了高效率、高度自动化、高利用率和高可靠性。 操作系统的组成 计算机系统由硬件和软件两部分组成 硬件部分：指其物理装置本身，包括各种处理

等比数列求和：$S_n = a_1`` * \frac{1-q^n}{1-q} = \frac{a_n*q - a_1}{q-1}$ 等差数列求和：Sn = $\frac {n (a_1 + a_n)}{2} $ = $n*a_1 + \frac{n(n-1)}{2}*d$ 组合数列公式 $C_n^m =\frac{A_n^m

动态规划 动态规划和分治的区别：是否有子问题重复出现 动态规划和贪心的区别： 关于最优子结构贪心：每一步的最优解一定包含上一步的最优解，上一步之前的最优解无需记录动态规划：全局最优解中一定包含某个局部最优解，但不一定包含上一步的局部最优解，因此需要记录之前的所有的局部最优解 关于子问题最优解组合成原问题最优解的组合方式贪心：如果把所有的子问题看成一棵树的话，贪心从根出发，每次向下遍历最优子树即可，

二叉树名词解释 叶子节点：末尾的子节点，自己下面不再连接有节点的节点（即末端），称为叶子节点（又称为终端结点） 二叉树旋转左旋 逆时针旋：头节点变成了心头节点的左孩子 右旋 顺时针旋：头节点变成了新头结点的右孩子。 旋转的情况 LL RR LR RL 遍历方式广度优先遍历(BFS) 广度优先遍历先从树的最高层开始，从左向右逐层向下访问树中

优先队列(堆) 堆就是用数组实现的完全二叉树 所以在堆中，在当前层级所有的节点都已经填满之前不允许开是下一层的填充，所以堆总是有这样的形状 堆和二叉搜索树的区别 节点的顺序。在二叉搜索树中，左子节点必须比父节点小，右子节点必须必比父节点大。但是在堆中并非如此。在最大堆中两个子节点都必须比父节点小，而在最小堆中，它们都必须比父节点大。 内存占用。普通树占用的内存空间比它们存储的数据要多。你必须为节

经典哈希函数特性 输入域是无穷大的，输出域是有限的 固定的输入，返回的输出hashCode也是固定的 必然有不同的输入相同的输出 哈希函数具有离散性 常见的HASH算法 直接定址法 直接以关键字K或者K加上某个常数(K+C)作为HASH地址 数字分析法 提供关键字中取值比较均匀的数字作为Hash地址 除留余数法 用关键字K除以某个不大于Hash表长度m的数P,将所得余数作为Hash地址

最大公约数和最小公倍数1234567 public static long gcb(long a, long b) { return b == 0 ? a : gcb(b, a % b); }// 最小公倍数 public static long lcm(long a, long b) { return a / gcb(a, b) *

排序算法1、基本介绍​ 排序算法比较基础，但是涉及到很多计算机科学的想法，如下：​ 1、比较和非比较的策略​ 2、迭代和递归的实现​ 3、分而治之思想​ 4、最佳、最差、平均情况时间复杂度分析​ 5、随机算法 稳定性 假定待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，称这种排序算法是稳定的，否则称为不稳定的 2、排序算法的分类算

[tOC] 栈 先进后出只能从栈顶访问和删除的数据结构，栈数据结构可以用于匹配分隔符以及大数相加的操作，可以用向量（数组）和链表的方式实现，其中链表的方式与抽象栈更匹配。在向量和链表形式的栈中，出栈操作的复杂度为O(1)，在向量栈中最坏的入栈复杂度为O(n)，而在链表栈中仍为O(1)。 单调栈 单调递增栈：单调递增栈就是从栈底到栈顶数据是从大到小 单调递减栈：单调递减栈就是从栈底到栈顶数据是从小

算法 算法的分类 决定性算法：对于给定的输入只有一种方式能确定下一步采取的操作，如求一个集合的合只需要逐个相加并不需要进行猜测。非决定性算法：非决定性算法将问题分解成猜测和验证两个阶段。算法的猜测阶段是非确定性的，算法的验证阶段是确定性的，它验证猜测阶段给出解的正确性。如查找算法会先猜测数组中某个数，再验证其是否是需要查找的那个数。 需要解决的判定问题的分类 P问题：能够用决定性算法在多项