題很多，先上題後上答案，便于大家思考
問題點：
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、KMP字元串比對
（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+樹的索引結構：