红黑树红黑树简介红黑树（Red-Black Tree）是一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红色或黑色。
红黑树特性
每个节点或是黑色，或是红色。
根节点是黑色。
每个叶子节点是黑色。
如果一个节点是红色的，则它的子节点必须是黑色的。
从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
红黑树图示
图示网站
红黑树应用红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(logn)，效率非常之高。例如，Java集合中的 TreeSet 和 TreeMap，C++ STL中的 set、map，以及Linux虚拟内存的管理，...
前趋图前趋图：用于描述进程之间的执行顺序的一种有向无循环图。
结点表示： 一个进程、一个程序段或 一条语句。有向边表示： 前驱关系。箭头所指的是后继。
例题(2009年下半年软件设计师上午试卷25、26题)
进程P1、P2、P3和P4的前趋图如下：
若用PV操作控制这几个进程并发执行的过程，则需要设置4个信号量S1、S2、S3 和S4，且信号量初值都等于零。下图中a和b应分别填写（25)，c和d应分别填写(26)。
(25)A.P(S1) P(S2) 和 P(S3) B.P(S1) P(S2) 和 V(S1)
...
平衡二叉树平衡二叉树简介平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树的数据结构。
平衡二叉树性质平衡二叉树是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。
平衡二叉树特性
非叶子节点最多拥有两个子节点。
非叶子节点的值大于左边子节点、小于右边子节点。
树的左右两边的层级数相差不会大于 1 。
没有值相等重复的节点...
有限自动机
一般我们会用状态图来描述一个有限自动机。它有且只有一个起始状态（在状态图中，一个从不知道什么地方来的箭头指向的状态），有一些终止状态（状态图中的双圈节点）。
有限自动机的输出是接受或者拒绝。
例题（2009年上半年软件设计师第48题）下图所示有限自动机的特点是（）。
A.识别的0、1串是以0开头且以1结尾 B.识别的0、1串中1的数目为偶数
C.识别的0、1串中0后面必须是1 ==D.识别的0、1串中1不能连续出现==
解析：采取排除法，枚举各种可到终态的方法，从而排除不符合的选项。
1，排除A、B。
001，排除C。
（2010年下半年软件设计师第...
排序算法0 排序算法的时间复杂度、空间复杂度及其稳定性稳定 ：如果 a 原本在 b 前面，而 a = b ，排序之后 a 仍然在 b 的前面。不稳定 ：如果 a 原本在 b 的前面，而 a = b ，排序之后 a 可能会出现在 b 的后面。内排序 ：所有排序操作都在内存中完成。外排序 ：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行。时间复杂度 ： 一个算法执行所耗费的时间。空间复杂度 ：运行完一个程序所需内存的大小。
排序方法
平均时间复杂度
最坏时间复杂度
最好时间复杂度
空间复杂度
排序方式
稳定性
插入排序
O(n2)
O(n2)
O(n...
计算机组成与体系结构1 数据的表示1.1 R进制转十进制使用按权展开法其具体操作方式为：将 R 进制数的每一位数值用 Rk 形式表示，即幂的底数是 R，指数为 k ，k 与该位和小数点之间的距离有关。当该位位于小数点左边，k 值是该位和小数点之间数码的个数，而当该位位于小数点右边，k 值是负值，其绝对值是该位和小数点之间数码的个数加 1 。
例如：二进制 10100.01 =1 x 24 + 1 x 22 + 1 x 2-2例如：七进制 604.01= 6 x 72 + 4 x 70 + 1 x 7-2
1.2 十进制转R进制使用短除法将 42 转换为二进制数。
1.3 二进制转八进...
C++ stackstack简介stack（堆栈）是一种容器适配器，专门设计用于在==FILO（先进后出）==环境中操作，在该环境中，仅从容器的一端插入和提取元素。stack（堆栈）通过容器适配器来实现，是一种将特定的容器类作为其最底层的容器的类，它提供了一些特定的成员函数来访问自己的元素，元素只能在这个特定容器的后面，也就是栈的顶部，进行出栈和入栈操作。
头文件#include \
成员函数
empty() 返回当前栈是否为空（为空返回true）
pop() 移除栈顶元素
push() 在栈顶增加元素
size() 返回栈中元素数目
...
McCabe度量法McCabe度量法是通过定义环路复杂度，建立程序复杂性的度量，它基于一个程序模块的程序图中环路的个数。
计算有向图G的环路复杂性的公式为：V（G）= m-n+2或V（G）= 闭合区域+1
其中V（G）是有向图G中的环路个数，m是G中的有向弧数，n是G中的节点数。
例题
McCabe度量法是通过定义环路复杂度，建立程序复杂性的度量，它基于一个程序模块的程序图中环路的个数。下图所示程序图的程序复杂度是（）。
(2009年上半年软件设计师上午试卷32题)
A.2 ==B.3== C.4 D.5
有向弧数：8
节点数：7
V（G）= 有...
NULL与nullptr1、C程序中的NULL在C语言中，NULL通常被定义为：
1#define NULL ((void *)0)
所以说NULL实际上是一个空指针，如果在C语言中写入以下代码，编译是没有问题的，因为在C语言中把空指针赋给int和char指针的时候，发生了隐式类型转换，把void指针转换成了相应类型的指针。
12int *pi = NULL;char *pc = NULL;
2、C++程序中的NULL但是问题来了，以上代码如果使用C++编译器来编译则是会出错的，因为C++是强类型语言，void*是不能隐式转换成其他类型的指针的，所以实际上编译器提供的头文件做了相应的处...
TCP的三次握手和四次挥手1、TCP简介
TCP（Transmission Control Protocol，传输控制协议）是一种面向连接的、可靠的、基于字节流的传输层通信协议。数据在传输前要建立连接，传输完毕后还要断开连接。
面向连接：一定是一对一才能连接，不能像 UDP 协议可以一个主机同时向多个主机发送消息，也就是一对多是无法做到的。
可靠的：无论的网络链路中出现了怎样的链路变化，TCP 都可以保证一个报文一定能够到达接收端。
字节流：消息是没有边界的，所以无论我们消息有多大都可以进行传输。并且消息是有序的，当前一个消息没有收到的时候，即使它先收到了后面的字节，那么也不能扔给应用层...
