共计 13860 个字符，预计需要花费 35 分钟才能阅读完成。
题很多，先上题后上答案，便于大家思考
问题点：
1、C 和 C ++ 的特点与区别？
2、C++ 的多态
3、虚函数实现
4、C 和 C ++ 内存调配问题
5、协程
6、CGI 的理解
7、过程间通信形式和线程间通信形式
8、TCP 握手与开释
9、http 和 https 的区别？
10、虚拟内存的概念与介绍
11、单链表的反转算法
12、红黑树以及其查找复杂度
13、KPM 字符串匹配
14、TCP 超时期待、重传以及流量管制
15、数据库引擎
16、数据库索引
1、C 和 C ++ 的特点与区别？
答：（1）C 语言特点：
1. 作为一种面向过程的结构化语言，易于调试和保护；
2. 体现能力和解决能力极强，能够间接拜访内存的物理地址；
3.C 语言实现了对硬件的编程操作，也适宜于应用软件的开发；
4.C 语言还具备效率高，可移植性强等特点。
（2）C++ 语言特点：
1. 在 C 语言的根底上进行裁减和欠缺，使 C ++ 兼容了 C 语言的面向过程特点，又成为了一种面向对象的程序设计语言；
2. 能够应用抽象数据类型进行基于对象的编程；
3. 能够应用多继承、多态进行面向对象的编程；
4. 能够担负起以模版为特色的泛型化编程。
C++ 与 C 语言的实质差异：在于 C ++ 是面向对象的，而 C 语言是面向过程的。或者说 C ++ 是在 C 语言的根底上减少了面向对象程序设
计的新内容，是对 C 语言的一次更重要的改革，使得 C ++ 成为软件开发的重要工具。
2、C++ 的多态
答：C++ 的多态性用一句话概括：在基类的函数前加上 virtual 关键字，在派生类中重写该函数，运行时将会依据对象的理论类型来
调用相应的函数。如果对象类型是派生类，就调用派生类的函数；如果对象类型是基类，就调用基类的函数。
1）：用 virtual 关键字申明的函数叫做虚函数，虚函数必定是类的成员函数；
2）：存在虚函数的类都有一个一维的虚函数表叫做虚表，类的对象有一个指向虚表开始的虚指针。虚表是和类对应的，虚表指针是
和对象对应的；
3）：多态性是一个接口多种实现，是面向对象的外围，分为类的多态性和函数的多态性。；
4）：多态用虚函数来实现，联合动静绑定.；
5）：纯虚函数是虚函数再加上 = 0；
6）：抽象类是指包含至多一个纯虚函数的类；
纯虚函数：virtual void fun()=0; 即抽象类，必须在子类实现这个函数，即先有名称，没有内容，在派生类实现内容。
3、虚函数实现
答：简略地说，每一个含有虚函数（无论是其自身的，还是继承而来的）的类都至多有一个与之对应的虚函数表，其中寄存着该类
所有的虚函数对应的函数指针。例：
其中：
B 的虚函数表中寄存着 B::foo 和 B::bar 两个函数指针。
D 的虚函数表中寄存的既有继承自 B 的虚函数 B::foo，又有重写（override）了基类虚函数 B::bar 的 D::bar，还有新增的虚函数 D::quz。
虚函数表结构过程：
从编译器的角度来说，B 的虚函数表很好结构，D 的虚函数表结构过程绝对简单。上面给出了结构 D 的虚函数表的一种形式（仅供参考）：
虚函数调用过程
以上面的程序为例：
4、C 和 C ++ 内存调配问题
答：（1）C 语言编程中的内存根本形成
C 的内存基本上分为 4 局部：动态存储区、堆区、栈区以及常量区。他们的性能不同，对他们应用形式也就不同。
1. 栈 ——由编译器主动调配开释；
2. 堆 ——个别由程序员调配开释，若程序员不开释，程序完结时可能由 OS 回收；
3. 全局区（动态区）——全局变量和动态变量的存储是放在一块的，初始化的全局变量和动态变量在一块区域，未初始化的全局变量
和未初始化的动态变量在相邻的另一块区域（C++ 中曾经不再这样划分），程序完结开释；
4. 另外还有一个专门放常量的中央，程序完结开释；
(a)函数体中定义的变量通常是在栈上；
(b)用 malloc, calloc, realloc 等分配内存的函数调配失去的就是在堆上；
(c)在所有函数体外定义的是全局量；
(d)加了 static 修饰符后不论在哪里都寄存在全局区（动态区）；
(e)在所有函数体外定义的 static 变量示意在该文件中无效，不能 extern 到别的文件用；
(f)在函数体内定义的 static 示意只在该函数体内无效；
(g)另外，函数中的 ”adgfdf” 这样的字符串寄存在常量区。
（2）C++ 编程中的内存根本结构
在 C ++ 中内存分成 5 个区，别离是堆、栈、全局 / 动态存储区、常量存储区和代码区；
1、栈，就是那些由编译器在须要的时候调配，在不须要的时候主动分明的变量的存储区，外面的变量通常是局部变量、函数参数等。
2、堆，就是那些由 new 调配的内存块，他们的开释编译器不去管，由咱们的应用程序去管制，个别一个 new 就要对应一个 delete。如
果程序员没有开释掉，那么在程序完结后，操作系统会主动回收。
3、全局 / 动态存储区，全局变量和动态变量被调配到同一块内存中，在以前的 C 语言中，全局变量又分为初始化的和未初始化的，在
C++ 外面没有这个辨别了，他们独特占用同一块内存区。
4、常量存储区，这是一块比拟非凡的存储区，他们外面寄存的是常量，不容许批改（当然，你要通过非正当伎俩也能够批改）。
5、代码区（.text 段），寄存代码（如函数），不容许批改（相似常量存储区），但能够执行（不同于常量存储区）。
内存模型组成部分：自在存储区，动静区、动态区；
依据 c /c++ 对象生命周期不同，c/c++ 的内存模型有三种不同的内存区域，即：自在存储区，动静区、动态区。
自在存储区：部分非动态变量的存储区域，即平时所说的栈；
动静区：用 new，malloc 调配的内存，即平时所说的堆；
动态区：全局变量，动态变量，字符串常量存在的地位；
注：代码尽管占内存，但不属于 c /c++ 内存模型的一部分；
一个正在运行着的 C 编译程序占用的内存分为 5 个局部：代码区、初始化数据区、未初始化数据区、堆区 和栈区；
（1）代码区（text segment）：代码区指令依据程序设计流程顺次执行，对于程序指令，则只会执行一次（每个过程），如果重复，则须要应用跳转指令，如果进行递归，则须要借助栈来实现。留神：代码区的指令中包含操作码和要操作的对象（或对象地址援用）。如果是立刻数（即具体的数值，如 5），将间接蕴含在代码中；
（2）全局初始化数据区 / 静态数据区（Data Segment）：只初始化一次。
（3）未初始化数据区（BSS）：在运行时扭转其值。
（4）栈区（stack）：由编译器主动调配开释，寄存函数的参数值、局部变量的值等，其操作形式相似于数据结构中的栈。
（5）堆区（heap）：用于动态内存调配。
为什么分成这么多个区域？
次要基于以下思考：
代码是依据流程顺次执行的，个别只须要拜访一次，而数据个别都须要拜访屡次，因而独自开拓空间以不便拜访和节约空间。
未初始化数据区在运行时放入栈区中，生命周期短。
全局数据和静态数据有可能在整个程序执行过程中都须要拜访，因而独自存储管理。
堆区由用户自在调配，以便治理。
还有腾讯，阿里，京东等一线大厂面试题及答案整顿，须要集锦的敌人能够 +qun720209036 收费获取。
5、协程
答：定义：协程是一种用户态的轻量级线程。
协程领有本人的寄存器上下文和栈。协程调度切换时，将寄存器上下文和栈保留到其余中央，在切回来的时候，复原先前保留的寄存器上下文和栈。因而：协程能保留上一次调用时的状态（即所有部分状态的一个特定组合），每次过程重入时，就相当于进入上一次调用的状态，换种说法：进入上一次来到时所处逻辑流的地位；
线程是抢占式，而协程是合作式；
协程的长处：
跨平台
跨体系架构
无需线程上下文切换的开销
无需原子操作锁定及同步的开销
不便切换控制流，简化编程模型
高并发 + 高扩展性 + 低成本：一个 CPU 反对上万的协程都不是问题。所以很适宜用于高并发解决。
协程的毛病：
无奈利用多核资源：协程的实质是个单线程, 它不能同时将 单个 CPU 的多个核用上, 协程须要和过程配合能力运行在多 CPU；
进行阻塞（Blocking）操作（如 IO 时）会阻塞掉整个程序：这一点和事件驱动一样，能够应用异步 IO 操作来解决。
6、CGI 的理解
答：CGI：通用网关接口（Common Gateway Interface）是一个 Web 服务器主机提供信息服务的标准接口。通过 CGI 接口，Web 服务
器就可能获取客户端提交的信息，转交给服务器端的 CGI 程序进行解决，最初返回后果给客户端。
CGI 通信零碎的组成是两局部：一部分是 html 页面，就是在用户端浏览器上显示的页面。另一部分则是运行在服务器上的 Cgi 程序。
7、过程间通信形式和线程间通信形式
答：（1）过程间通信形式：
管道(pipe)：管道是一种半双工的通信形式，数据只能单向流动，而且只能在具备亲缘关系的过程间应用。过程的亲缘关系通常是指父子过程关系。
信号量(semophore)：信号量是一个计数器，能够用来管制多个过程对共享资源的拜访。它常作为一种锁机制，避免某过程正在访问共享资源时，其余过程也拜访该资源。因而，次要作为过程间以及同一过程内不同线程之间的同步伎俩。
音讯队列(message queue)：音讯队列是由音讯的链表，寄存在内核中并由音讯队列标识符标识。音讯队列克服了信号传递信息少、管道只能承载无格局字节流以及缓冲区大小受限等毛病。
共享内存(shared memory)：共享内存就是映射一段能被其余过程所拜访的内存，这段共享内存由一个过程创立，但多个过程都能够拜访。共享内存是最快的 IPC 形式，它是针对其余过程间通信形式运行效率低而专门设计的。它往往与其余通信机制，如信号两，配合应用，来实现过程间的同步和通信。
套接字(socket)：套解口也是一种过程间通信机制，与其余通信机制不同的是，它可用于不同及其间的过程通信。
（2）线程间通信形式：
全局变量；
Messages 音讯机制；
CEvent 对象（MFC 中的一种线程通信对象，通过其触发状态的扭转实现同步与通信）。
8、TCP 握手与开释
答：（1）握手
第一次握手：主机 A 发送握手信号 syn=1 和 seq=x（随机产生的序列号）的数据包到服务器，主机 B 由 SYN= 1 晓得，A 要求建设联机；
第二次握手：主机 B 收到申请后要确认联机信息，向 A 发送 syn=1，ack=x（x 是主机 A 的 Seq）+1，以及随机产生的确认端序列号
seq= y 的包；
第三次握手：主机 A 收到后查看 ack 是否正确（ack=x+1），即第一次发送的 seq+1，若正确，主机 A 会再发送 ack=y+1，以及随机序
列号 seq=z，主机 B 收到后确认 ack 值则连贯建设胜利；
实现三次握手，主机 A 与主机 B 开始传送数据。
注：上述步骤中，第二和第三次确认包中都还蕴含一个标记位未予以阐明，该标记位为 1 示意失常应答；
具体可见图片：
为什么须要“三次握手”？
“三次握手”的目标是“为了避免已生效的连贯申请报文段忽然又传送到了服务端，因此产生谬误”。具体例如：client 收回的第一个连贯申请报文段并没有失落，而是在某个网络结点长时间的滞留了，以至延误到连贯开释当前的某个工夫才达到 server。原本这是一个早已生效的报文段。但 server 收到此生效的连贯申请报文段后，就误认为是 client 再次收回的一个新的连贯申请。于是就向 client 收回确认报文段，批准建设连贯。假如不采纳“三次握手”，那么只有 server 收回确认，新的连贯就建设了。因为当初 client 并没有收回建设连贯的申请，因而不会理会 server 的确认，也不会向 server 发送数据。但 server 却认为新的运输连贯曾经建设，并始终期待 client 发来数据。这样，server 的很多资源就白白浪费掉了。采纳“三次握手”的方法能够避免上述景象产生。例如方才那种状况，client 不会向 server 的确认收回确认。server 因为收不到确认，就晓得 client 并没有要求建设连贯。次要目标避免 server 端始终期待，浪费资源。
（2）挥手
因为 TCP 连贯是全双工的，因而每个方向都必须独自进行敞开。这准则是当一方实现它的数据发送工作后就能发送一个 FIN 来终止这个方向的连贯。收到一个 FIN 只意味着这一方向上没有数据流动，一个 TCP 连贯在收到一个 FIN 后仍能发送数据。首先进行敞开的一方将执行被动敞开，而另一方执行被动敞开。
(1) TCP 客户端发送一个 FIN，用来敞开客户到服务器的数据传送(报文段 4)；
(2) 服务器收到这个 FIN，发回一个 ACK，确认序号为收到的序号加 1(报文段 5)。和 SYN 一样，一个 FIN 将占用一个序号；
(3) 服务器敞开客户端的连贯后，再发送一个 FIN 给客户端(报文段 6)；
(4) 客户段收到服务端的 FIN 后，发回 ACK 报文确认，并将确认序号设置为收到序号加 1(报文段 7)；
留神：TCP 连贯的任何一方都能够发动挥手操作，上述步骤只是两种之一；
具体过程见图：
为什么是“四次挥手”？
因为当收到对方的 FIN 报文告诉时，它仅仅示意对方没有数据发送给你了；但未必你所有的数据都全副发送给对方了，所以你可能还须要发送一些数据给对方，再发送 FIN 报文给对方来示意你批准当初能够敞开连贯了，故这里的 ACK 报文和 FIN 报文少数状况下都是离开发送的，也就造成了 4 次挥手。
握手，挥手过程中各状态介绍：
（1）3 次握手过程状态：
LISTEN: 这个也是非常容易了解的一个状态，示意服务器端的某个 SOCKET 处于监听状态，能够承受连贯了。
SYN_SENT: 当客户端 SOCKET 执行 CONNECT 连贯时，它首先发送 SYN 报文，因而也随即它会进入到了 SYN_SENT 状态，并期待服务端的发送三次握手中的第 2 个报文。SYN_SENT 状态示意客户端已发送 SYN 报文。(发送端)
SYN_RCVD: 这个状态与 SYN_SENT 遐想响应这个状态示意承受到了 SYN 报文，在失常状况下，这个状态是服务器端的 SOCKET 在建设 TCP 连贯时的三次握手会话过程中的一个中间状态，很短暂，基本上用 netstat 你是很难看到这种状态的，除非你特意写了一个客户端测试程序，成心将三次 TCP 握手过程中最初一个 ACK 报文不予发送。因而这种状态时，当收到客户端的 ACK 报文后，它会进入到 ESTABLISHED 状态。(服务器端)
ESTABLISHED：这个容易了解了，示意连贯曾经建设了。
（2）4 次挥手过程状态：
FIN_WAIT_1: 这个状态要好好解释一下，其实 FIN_WAIT_1 和 FIN_WAIT_2 状态的真正含意都是示意期待对方的 FIN 报文。而这两种状态的区别是：FIN_WAIT_1 状态实际上是当 SOCKET 在 ESTABLISHED 状态时，它想被动敞开连贯，向对方发送了 FIN 报文，此时该 SOCKET 即进入到 FIN_WAIT_1 状态。而当对方回应 ACK 报文后，则进入到 FIN_WAIT_2 状态，当然在理论的失常状况下，无论对方何种状况下，都应该马上回应 ACK 报文，所以 FIN_WAIT_1 状态个别是比拟难见到的，而 FIN_WAIT_2 状态还有时经常能够用 netstat 看到。(被动方)
FIN_WAIT_2：下面曾经具体解释了这种状态，实际上 FIN_WAIT_2 状态下的 SOCKET，示意半连贯，也即有一方要求 close 连贯，但另外还通知对方，我临时还有点数据须要传送给你(ACK 信息)，稍后再敞开连贯。(被动方)
TIME_WAIT: 示意收到了对方的 FIN 报文，并发送出了 ACK 报文，就等 2MSL 后即可回到 CLOSED 可用状态了。如果 FIN_WAIT_1 状态下，收到了对方同时带 FIN 标记和 ACK 标记的报文时，能够间接进入到 TIME_WAIT 状态，而无须通过 FIN_WAIT_2 状态。(被动方)
CLOSING(比拟少见): 这种状态比拟非凡，理论状况中应该是很少见，属于一种比拟常见的例外状态。失常状况下，当你发送 FIN 报文后，按理来说是应该先收到 (或同时收到) 对方的 ACK 报文，再收到对方的 FIN 报文。然而 CLOSING 状态示意你发送 FIN 报文后，并没有收到对方的 ACK 报文，反而却也收到了对方的 FIN 报文。什么状况下会呈现此种状况呢? 其实细想一下，也不难得出结论：那就是如果单方简直在同时 close 一个 SOCKET 的话，那么就呈现了单方同时发送 FIN 报文的状况，也即会呈现 CLOSING 状态，示意单方都正在敞开 SOCKET 连贯。
CLOSE_WAIT: 这种状态的含意其实是示意在期待敞开。怎么了解呢? 当对方 close 一个 SOCKET 后发送 FIN 报文给本人，你零碎毫无疑问地会回应一个 ACK 报文给对方，此时则进入到 CLOSE_WAIT 状态。接下来呢，实际上你真正须要思考的事件是观察你是否还有数据发送给对方，如果没有的话，那么你也就能够 close 这个 SOCKET，发送 FIN 报文给对方，也即敞开连贯。所以你在 CLOSE_WAIT 状态下，须要实现的事件是期待你去敞开连贯。(被动方)
LAST_ACK: 这个状态还是比拟容易好了解的，它是被动敞开一方在发送 FIN 报文后，最初期待对方的 ACK 报文。当收到 ACK 报文后，也即能够进入到 CLOSED 可用状态了。(被动方)
9、http 和 https 的区别？
答：HTTPS 协定是由 SSL+HTTP 协定构建的可进行加密传输、身份认证的网络协议，要比 http 协定平安。
HTTPS（Secure Hypertext Transfer Protocol）平安超文本传输协定，与 http 次要区别在于：
http 是超文本传输协定，信息是明文传输，https 则是具备安全性的 ssl 加密传输协定；
http 和 https 应用的是齐全不同的连贯形式用的端口也不一样, 前者是 80, 后者是 443；
上面具体介绍一下 HTTP 和 HTTPS 协定：
首先阐明一下：HTTP 和 HTTPS 协定是应用层协定；
上图充沛表明：HTTP 是应用层协定，并且 HTTPS 是在 HTTP 协定根底上增加 SSL 等加密策略后的协定；
TLS/SSL 中应用了非对称加密，对称加密以及 HASH 算法。
（1）Http 协定
1）HTTP 协定和 TCP 协定之间的区别分割
①TPC/IP 协定是传输层协定，次要解决数据如何在网络中传输，而 HTTP 是应用层协定，次要解决如何包装数据；
②HTTP 的默认端口号是 80，TCP/IP 协定通信编程时端口号须要本人指定（例如 socket 编程）；
③HTTP 协定是在 TCP/IP 协定根底上实现的，即 HTTP 数据包是通过 TCP/IP 协定实现传输的；
④HTTP 是无状态的短连贯协定，TCP 是有状态的长连贯协定；
HTTP 是在有状态长连贯 TCP/IP 协定的根底上实现的，为什么却是无状态短连贯协定？
答：因为 HTTP 协定每次申请完结就会主动敞开连贯，这样就变成了短连贯；
短连贯又导致了该次申请相干信息的失落，也就造成了 HTTP 协定对于后期事务处理没有记忆能力，故为无状态协定。
2）HTTP 协定其残缺的工作过程可分为四步：
①连贯：首先客户机与服务器须要建设连贯（由 TCP/IP 握手连贯实现）。只有单击某个超级链接，HTTP 的工作开始；
②申请：建设连贯后，客户机发送一个申请给服务器，申请形式的格局为：对立资源标识符（URL）、协定版本号，后边是 MIME 信息包含申请修饰符、客户机信息和可能的内容；
③应答：服务器接到申请后，给予相应的响应信息，其格局为一个状态行，包含信息的协定版本号、一个胜利或谬误的代码，后边是 MIME 信息包含服务器信息、实体信息和可能的内容。客户端接管服务器所返回的信息通过浏览器显示在用户的显示屏上；
④敞开：当应答完结后，浏览器和服务器敞开连贯，以保障其余浏览器能够与服务器进行连贯。
更残缺的过程可能如下：
域名解析 –> 发动 TCP 的 3 次握手 –> 建设 TCP 连贯后发动 http 申请 –> 服务器响应 http 申请，浏览器失去 html 代码 –> 浏览器解析 html 代码，并申请 html 代码中的资源（如 js、css、图片等）–> 浏览器对页面进行渲染出现给用户。
如果在以上过程中的某一步呈现谬误，那么产生谬误的信息将返回到客户端，有显示屏输入。对于用户来说，这些过程是由 HTTP 本人实现的，用户只有用鼠标点击，期待信息显示就能够了。
（2）Https 协定
HTTPS 握手过程包含五步：
1）浏览器申请连贯；
2）服务器返回证书：证书外面蕴含了网站地址，加密公钥，以及证书的颁发机构等信息。
3）浏览器收到证书后作以下工作：
a) 验证证书的合法性；
b) 生成随机（对称）明码，取出证书中提供的公钥对随机明码加密；
c) 将之前生成的加密随机明码等信息发送给网站；
4）服务器收到音讯后作以下的操作：
a) 应用本人的私钥解密浏览器用公钥加密后的音讯，并验证 HASH 是否与浏览器发来的统一；
b) 应用加密的随机对称明码加密一段音讯，发送给浏览器；
5）浏览器解密并计算握手音讯的 HASH：如果与服务端发来的 HASH 统一，此时握手过程完结，之后所有的通信数据将由之前浏览
器生成的随机明码并利用对称加密算法进行加密。
留神：服务器有两个密钥，一个公钥、一个私钥，只有私钥才能够解密公钥加密的音讯；
如图：
或者如下图：
HTTPS 协定、SSL、和数字证书的关系介绍：
概述：对于 HTTPS 协定，所有的音讯都是通过 SSL 协定形式加密，而反对加密的文件正是数字证书；
（1）SSL
SSL 罕用的加密算法：对称明码算法、非对称明码算法、散列算法；
SSL 的加密过程：须要留神的是非对称加解密算法的效率要比对称加解密要低的多。所以 SSL 在握手过程中应用非对称明码算法来
协商密钥，理论应用对称加解密的办法对 http 内容加密传输；
（2）数字证书
数字证书是用于在 INTERNET 上标识集体或者机构身份的一种技术手段，它通过由一些公认的权威机构所认证，从而能够保障其
平安地被利用在各种场合。证书外面蕴含了网站地址，加密公钥，以及证书的颁发机构等信息。
10、虚拟内存的概念与介绍
答：虚拟内存中，容许将一个作业分屡次调入内存，须要时就调入，不须要的就先放在外存。因而，虚拟内存的实须要建设在离散
调配的内存治理形式的根底上。虚拟内存的实现有以下三种形式：
请求分页存储管理
申请分段存储管理
申请段页式存储管理
虚拟内存的意义：
一，虚拟内存能够使得物理内存更加高效。虚拟内存应用置换形式，须要的页就置换进来，不须要的置换进来，使得内存中只保留了须要的页，进步了利用率，也防止了不必要的写入与擦除；
二，应用虚拟地址能够使内存的治理更加便捷。在程序编译的时候就会生成虚拟地址，该虚拟地址并不是对应一个物理地址，使得也就极大地缩小了地址被占用的抵触，缩小治理难度；
三，为了安全性的思考。在应用虚拟地址的时候，裸露给程序员永远都是虚拟地址，而具体的物理地址在哪里，这个只有零碎才理解。这样就提
高了零碎的封装性。
11、单链表的反转算法
答：思维：创立 3 个指针，别离指向上一个节点、以后节点、下一个节点，遍历整个链表的同时，将正在拜访的节点指向上一个节点，当遍历完结后，就同时实现了链表的反转。
实现代码：
ListNode* ReverseList(ListNode* pHead) {
ListNode *p,*q,*r;
if(pHead==NULL || pHead->next==NULL){return pHead;}else{
p=pHead;
q=p->next;
pHead->next=NULL;
while(q!=NULL){
r=q->next;
q->next=p;
p=q;
q=r;
}
return p;
}
}12、红黑树以及其查找复杂度
答：（1）红黑树来源于二叉搜寻树，其在关联容器如 map 中利用宽泛，次要劣势在于其查找、删除、插入工夫复杂度小，但其也有毛病，就是容易偏差一边而变成一个链表。
红黑树是一种二叉查找树，但在每个结点上减少一个存储位示意结点的色彩，能够是 Red 或 Black。也就是说，红黑树是在二叉
查找树根底上进一步实现的；
红黑树的五个性质：
性质 1. 节点是红色或彩色；
性质 2. 根节点是彩色；
性质 3 每个叶节点（指树的末端的 NIL 指针节点或者空节点）是彩色的；
性质 4 每个红色节点的两个子节点都是彩色。(从每个叶子到根的所有门路上不能有两个间断的红色节点)；
性质 5. 从任一节点到其每个尾端 NIL 节点或者 NULL 节点的所有门路都蕴含雷同数目的彩色节点。
（注：上述第 3、5 点性质中所说的 NIL 或者 NULL 结点，并不蕴含数据，只充当树的门路完结的标记，即此叶结点十分见的叶子结点）。
因为一棵由 n 个结点随机结构的二叉查找树的高度为 lgn，所以牵强附会，二叉查找树的个别操作的执行工夫为 O(lgn)。但二叉查
找树若进化成了一棵具备 n 个结点的线性链后，则这些操作最坏状况运行工夫为 O(n)；
红黑树尽管实质上是一棵二叉查找树，但它在二叉查找树的根底上减少以上五个性质使得红黑树绝对均衡，从而保障了
红黑树的查找、插入、删除的工夫复杂度最坏为 O(log n)。
（2）左旋右旋
红黑树插入或删除后，个别就会扭转红黑树的个性，要复原红黑树上述 5 个性质，个别都要那就要做 2 方面的工作：
1、局部结点色彩，从新着色
2、调整局部指针的指向，即左旋、右旋。
左选右旋如图所示：
左旋，如图所示（左 -> 右），以 x ->y 之间的链为“支轴”进行，使 y 成为该新子树的根，x 成为 y 的左孩子，而 y 的左孩子则成为 x 的右孩
子。算法很简略，旋转后各个结点从左往右，依然都是从小到大。
左旋代码实现，分三步:
（1）开始变动，y 的左孩子成为 x 的右孩子；
（2）y 成为 x 的父结点；
（3）x 成为 y 的左孩子；
右旋相似，不再累述；
13、KPM 字符串匹配
（1）KMP 匹配算法代码实现：
int KmpSearch(char s, char p)
{
int i = 0;
int j = 0;
int sLen = strlen(s);
int pLen = strlen(p);
while (i < sLen && j < pLen)
{
//①如果 j = -1，或者以后字符匹配胜利（即 S[i] == P[j]），都令 i ++，j++
if (j == -1 || s[i] == p[j])
{
i++;
j++;
}
else
{
//②如果 j != -1，且以后字符匹配失败（即 S[i] != P[j]），则令 i 不变，j = next[j]
//next[j]即为 j 所对应的 next 值
j = next[j];
}
}
if (j == pLen)
return i – j;
else
return -1;
}
（2）next 数组求取
上述（1）中最重要的就是：一旦不匹配，模式串不是向后挪动一位，而是依据后面匹配信息挪动多位。而这个多位取得就是依据 next 数组，上面有 next 数组的求取形式：
Next 数组是依据模式串的前缀后缀获取的，如下：
①寻找前缀后缀最长公共元素长度
举个例子，如果给定的模式串为“abab”，那么它的各个子串的前缀后缀的公共元素的最大长度如下表格所示：
比方对于字符串 aba 来说，它有长度为 1 的雷同前缀后缀 a；而对于字符串 abab 来说，它有长度为 2 的雷同前缀后缀 ab（雷同前缀后缀的长度为 k + 1，k + 1 = 2）。
②求 next 数组
next 数组思考的是除以后字符外的最长雷同前缀后缀，所以通过第①步骤求得各个前缀后缀的公共元素的最大长度后，只有稍作变形即可：将第①步骤中求得的数组整体右移一位，而后第一个元素赋为 - 1 即可（留神：字符串下标须要从 0 开始），如下表格所示：
比方对于 aba 来说，第 3 个字符 a 之前的字符串 ab 中有长度为 0 的雷同前缀后缀，所以第 3 个字符 a 对应的 next 值为 0；而对于 abab 来说，第 4 个字符 b 之前的字符串 aba 中有长度为 1 的雷同前缀后缀 a，所以第 4 个字符 b 对应的 next 值为 1（雷同前缀后缀的长度为 k，k = 1）。
KMP 的 next 数组相当于通知咱们：当模式串中的某个字符跟文本串中的某个字符匹配失配时，模式串下一步应该跳到哪个地位（具体：放弃测试串的下标 i 不变，使得匹配串的下标 j =next[j]）。
前缀后缀长度求取以及 next 数组获取：
如果给定的模式串是：“ABCDABD”，从左至右遍历整个模式串，其各个子串的前缀后缀别离如下表格所示：
也就是说，原模式串子串对应的各个前缀后缀的公共元素的最大长度表为：
0 0 0 0 1 2 0；
故对应的 next 数组为：-1 0 0 0 0 1 2；
（留神：这里的字符串下标是从 0 开始的，若从 1 开始，next 数组所有元素都对应要加 1。）
求取 next 的实现代码：
string T; // T 为模式串
cin>>T;
int len=T.size();
queue<int> MaxLen;
vector<int> next;
MaxLen.push(0); // 第一个元素都设为 0
for(int i=1;i<len;i++)
{
int k=1,maxLen=0;
while(k<=i)
{
if(T.substr(0,k)==T.substr(i-k+1,k))
{
maxLen=k;
}
k++;
}
MaxLen.push(maxLen);
}
cout<<endl;
next.push_back(-1); // 第一个元素都设为 -1
while(MaxLen.size()>1)
{
int temp=MaxLen.front();
next.push_back(temp);
MaxLen.pop();
cout<<temp<<‘ ‘;
}
14、TCP 超时期待、重传以及流量管制
答：TCP 等待时间须要设定，超过了就认为丢包，须要重传；
为了避免拥塞状况，个别会采纳流量管制，其实现伎俩是用滑动窗口限度客户端发送分组数量；
15、数据库引擎
答：数据库引擎是用于存储、解决和爱护数据的外围服务。利用数据库引擎可管制拜访权限并疾速处理事务，从而满足企业内大多
数须要解决大量数据的应用程序的要求。
简言之，数据库引擎就是一段用于撑持所有数据库操作的外围程序，就如名称一样，是一个车的引擎性能；
常见的数据库引擎有：
（1）Microsoft JET (Joint Engineering Technologe) 用于 Access 和 VB 的内嵌数据库性能的外围元素；
（2）ODBC（Open DataBase Connectivity，凋谢数据库互连）是由 Microsoft 定义的一种数据库拜访规范，它提供一种规范的数据
库拜访办法以拜访不同平台的数据库。一个 ODBC 应用程序既能够拜访在本地 PC 机上的数据库，也能够拜访多种异构平台上的数据
库，例如 SQL Server、Oracle 或者 DB2；
（3）OLE DB 是 Microsoft 开发的最新数据库拜访接口，Microsoft 将其定义为 ODBC 接班人；
（4）MYSQL 反对三个引擎：ISAM、MYISAM 和 HEAP。另外两种类型 INNODB 和 BERKLEY（BDB）也经常能够应用；
①ISAM 执行读取操作的速度很快，而且不占用大量的内存和存储资源。ISAM 的两个次要不足之处在于，它不 反对事务处理，也不可能容错；
②MyISAM 是 MySQL 的 ISAM 扩大格局和缺省的数据库引擎 MYISAM。除了提供 ISAM 里所没有的索引和字段治理的大量性能，
MyISAM 还应用一种表格锁定的机制，来优化多个并发的读写操作，其代价是你须要常常运行 OPTIMIZE TABLE 命令，来复原被更新
机制所节约的空间；
③HEAP 容许只驻留在内存里的长期表格。驻留在内存里让 HEAP 要比 ISAM 和 MYISAM 都快，然而它所治理的数据是不稳固的，
而且如果在关机之前没有进行保留，那么所有的数据都会失落。
16、数据库索引
答：定义：数据库索引是对数据库表中一列或多列的值进行排序的一种构造，应用索引可快速访问数据库表中的特定信息；
举例：employee 表的人员编号列（id）就是数据库索引，select * from employee where id=10000 即可查找编号 10000 的人员信息。如果没有索引，必须遍历整个表直到 id=10000；
数据库索引作用：
一，大大放慢 数据的检索速度，这也是创立索引的最次要的起因；
二，保障数据库表中每一行数据的唯一性；
三，能够减速表和表之间的连贯，特地是在实现数据的参考完整性方面特地有意义；
四，在应用分组和排序子句进行数据检索时，同样能够显著缩小查问中分组和排序的工夫；
五，通过应用索引，能够在查问的过程中，应用优化暗藏器，进步零碎的性能。
数据库索引缺点：
一，表的增删改查、创立索引和保护索引要消耗工夫；
二，索引须要占物理空间；
数据库索引的两个特色：索引有两个特色，即唯一性索引和复合索引；
①惟一 性索引保障在索引列中的全副数据是惟一的，不会蕴含冗余数据；
②复合索引就是一个索引创立在两个列或者多个列上，搜寻时须要两个或者多个索引列作为一个要害值；
数据库索引好比是一本书后面的目录，索引分为聚簇索引和非聚簇索引两类：
1）聚簇索引是依照数据寄存的物理地位为程序的，其多个间断行的访问速度更快；
2）非聚簇索引是依照数据寄存的逻辑地位为程序的，其单行访问速度更快；
局部性原理与磁盘预读
局部性原理：当一个数据被用到时，其左近的数据也通常会马上被应用。程序运行期间所须要的数据通常比拟集中；
磁盘预读：正是因为局部性原理以及数据存储磁盘的读写速度慢的起因，每次对数据库进行读取都不是按需读取，而是读取多
于需要数据区域内的数据到内存，用于后续应用，进步写读取数据速度；
注：磁盘预读个别都是每次读取逻辑上的一页，或物理上的一块，不论理论需要是多少；
数据库索引的实现通常应用 B 树及其变种 B + 树，上面进行 B -/+Tree 构造的数据库索引的性能剖析：
（1）B 树索引构造：
数据库系统的设计者奇妙利用了磁盘预读原理，将 B 树的一个节点的大小设为等于一个页，这样每个节点只须要一次 I / O 就能够
齐全载入。为了达到这个目标，在理论实现 B -Tree 还须要应用如下技巧：
——每次新建节点时，间接申请一个页的空间，这样就保障一个节点物理上也存储在一个页；
B-Tree 中一次检索最多须要 h - 1 次 I /O（磁盘 IO 不包含根节点，因为根节点常驻内存），渐进复杂度为 O(h)=O(logdN)。一
般理论利用中，出度 d 是十分大的数字，通常超过 100，因而 h 十分小（通常不超过 3）。
而红黑树这种构造，h 显著要深的多。因为逻辑上很近的节点（父子）物理上可能很远，无奈利用局部性，所以红黑树的 I / O 渐进
复杂度也为 O(h)，效率显著比 B -Tree 差很多。
所以，B 树结构的数据库索引，在元素查找上效率很高；
（2）B+ 树的索引构造：
B+ 树则适当就义检索的工夫复杂度（都必须检索到叶子结点），但改善了节点插入和删除的工夫复杂度（相似用链表改善数组的效
果），所以 B + 树属于一种折中抉择。