題很多，先上題后上答案，便于大家思考

問題點：

1、C和C 的特點與區(qū)別？
2、C 的多態(tài)
3、虛函數實現(xiàn)
4、C和C 內存分配問題
5、協(xié)程
6、CGI的了解
7、進程間通信方式和線程間通信方式
8、TCP握手與釋放
9、http和https的區(qū)別？
10、虛擬內存的概念與介紹
11、單鏈表的反轉算法
12、紅黑樹以及其查找復雜度
13、KPM字符串匹配
14、TCP超時等待、重傳以及流量控制
15、數據庫引擎
16、數據庫索引

1、C和C 的特點與區(qū)別？

答：（1）C語言特點：

1.作為一種面向過程的結構化語言，易于調試和維護；

2.表現(xiàn)能力和處理能力極強，可以直接訪問內存的物理地址；

3.C語言實現(xiàn)了對硬件的編程操作，也適合于應用軟件的開發(fā)；

4.C語言還具有效率高，可移植性強等特點。

（2）C 語言特點：

1.在C語言的基礎上進行擴充和完善，使C 兼容了C語言的面向過程特點，又成為了一種面向對象的程序設計語言；

2.可以使用抽象數據類型進行基于對象的編程；

3.可以使用多繼承、多態(tài)進行面向對象的編程；

4.可以擔負起以模版為特征的泛型化編程。

C 與C語言的本質差別：在于C 是面向對象的，而C語言是面向過程的?；蛘哒fC 是在C語言的基礎上增加了面向對象程序設

計的新內容，是對C語言的一次更重要的改革，使得C 成為軟件開發(fā)的重要工具。

2、C 的多態(tài)

答：C 的多態(tài)性用一句話概括：在基類的函數前加上virtual關鍵字，在派生類中重寫該函數，運行時將會根據對象的實際類型來

調用相應的函數。如果對象類型是派生類，就調用派生類的函數；如果對象類型是基類，就調用基類的函數。

1）：用virtual關鍵字申明的函數叫做虛函數，虛函數肯定是類的成員函數；

2）：存在虛函數的類都有一個一維的虛函數表叫做虛表，類的對象有一個指向虛表開始的虛指針。虛表是和類對應的，虛表指針是

和對象對應的；

3）：多態(tài)性是一個接口多種實現(xiàn)，是面向對象的核心，分為類的多態(tài)性和函數的多態(tài)性。；

4）：多態(tài)用虛函數來實現(xiàn)，結合動態(tài)綁定.；

5）：純虛函數是虛函數再加上 = 0；

6）：抽象類是指包括至少一個純虛函數的類；

純虛函數：virtual void fun()=0;即抽象類，必須在子類實現(xiàn)這個函數，即先有名稱，沒有內容，在派生類實現(xiàn)內容。

3、虛函數實現(xiàn)

答：簡單地說，每一個含有虛函數（無論是其本身的，還是繼承而來的）的類都至少有一個與之對應的虛函數表，其中存放著該類

所有的虛函數對應的函數指針。例：

其中：

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部分：靜態(tài)存儲區(qū)、堆區(qū)、棧區(qū)以及常量區(qū)。他們的功能不同，對他們使用方式也就不同。

1.棧 ——由編譯器自動分配釋放；

2.堆 ——一般由程序員分配釋放，若程序員不釋放，程序結束時可能由OS回收；

3.全局區(qū)（靜態(tài)區(qū)）——全局變量和靜態(tài)變量的存儲是放在一塊的，初始化的全局變量和靜態(tài)變量在一塊區(qū)域，未初始化的全局變量

和未初始化的靜態(tài)變量在相鄰的另一塊區(qū)域（C 中已經不再這樣劃分），程序結束釋放；

4.另外還有一個專門放常量的地方，程序結束釋放；

(a)函數體中定義的變量通常是在棧上；

(b)用malloc, calloc, realloc等分配內存的函數分配得到的就是在堆上；

(c)在所有函數體外定義的是全局量；

(d)加了static修飾符后不管在哪里都存放在全局區(qū)（靜態(tài)區(qū)）；

(e)在所有函數體外定義的static變量表示在該文件中有效，不能extern到別的文件用；

(f)在函數體內定義的static表示只在該函數體內有效；

(g)另外，函數中的"adgfdf"這樣的字符串存放在常量區(qū)。

（2）C 編程中的內存基本構造

在C 中內存分成5個區(qū)，分別是堆、棧、全局/靜態(tài)存儲區(qū)、常量存儲區(qū)和代碼區(qū)；

1、棧，就是那些由編譯器在需要的時候分配，在不需要的時候自動清楚的變量的存儲區(qū)，里面的變量通常是局部變量、函數參數等。

2、堆，就是那些由new分配的內存塊，他們的釋放編譯器不去管，由我們的應用程序去控制，一般一個new就要對應一個delete。如

果程序員沒有釋放掉，那么在程序結束后，操作系統(tǒng)會自動回收。

3、全局/靜態(tài)存儲區(qū)，全局變量和靜態(tài)變量被分配到同一塊內存中，在以前的C語言中，全局變量又分為初始化的和未初始化的，在

C 里面沒有這個區(qū)分了，他們共同占用同一塊內存區(qū)。

4、常量存儲區(qū)，這是一塊比較特殊的存儲區(qū)，他們里面存放的是常量，不允許修改（當然，你要通過非正當手段也可以修改）。

5、代碼區(qū) （.text段），存放代碼（如函數），不允許修改（類似常量存儲區(qū)），但可以執(zhí)行（不同于常量存儲區(qū)）。

內存模型組成部分：自由存儲區(qū)，動態(tài)區(qū)、靜態(tài)區(qū)；

根據c/c 對象生命周期不同，c/c 的內存模型有三種不同的內存區(qū)域，即：自由存儲區(qū)，動態(tài)區(qū)、靜態(tài)區(qū)。

自由存儲區(qū)：局部非靜態(tài)變量的存儲區(qū)域，即平常所說的棧；

動態(tài)區(qū)：用new ，malloc分配的內存，即平常所說的堆；

靜態(tài)區(qū)：全局變量，靜態(tài)變量，字符串常量存在的位置；

注：代碼雖然占內存，但不屬于c/c 內存模型的一部分；

一個正在運行著的C編譯程序占用的內存分為5個部分：代碼區(qū)、初始化數據區(qū)、未初始化數據區(qū)、堆區(qū) 和棧區(qū)；

（1）代碼區(qū)（text segment）：代碼區(qū)指令根據程序設計流程依次執(zhí)行，對于順序指令，則只會執(zhí)行一次（每個進程），如果反復，則需要使用跳轉指令，如果進行遞歸，則需要借助棧來實現(xiàn)。注意：代碼區(qū)的指令中包括操作碼和要操作的對象（或對象地址引用）。如果是立即數（即具體的數值，如5），將直接包含在代碼中；

（2）全局初始化數據區(qū)/靜態(tài)數據區(qū)（Data Segment）：只初始化一次。

（3）未初始化數據區(qū)（BSS）：在運行時改變其值。

（4）棧區(qū)（stack）：由編譯器自動分配釋放，存放函數的參數值、局部變量的值等，其操作方式類似于數據結構中的棧。

（5）堆區(qū)（heap）：用于動態(tài)內存分配。

為什么分成這么多個區(qū)域？

主要基于以下考慮：

#代碼是根據流程依次執(zhí)行的，一般只需要訪問一次，而數據一般都需要訪問多次，因此單獨開辟空間以方便訪問和節(jié)約空間。

#未初始化數據區(qū)在運行時放入棧區(qū)中，生命周期短。

#全局數據和靜態(tài)數據有可能在整個程序執(zhí)行過程中都需要訪問，因此單獨存儲管理。

#堆區(qū)由用戶自由分配，以便管理。

5、協(xié)程

答：定義：協(xié)程是一種用戶態(tài)的輕量級線程。

協(xié)程擁有自己的寄存器上下文和棧。協(xié)程調度切換時，將寄存器上下文和棧保存到其他地方，在切回來的時候，恢復先前保存的寄存器上下文和棧。因此：協(xié)程能保留上一次調用時的狀態(tài)（即所有局部狀態(tài)的一個特定組合），每次過程重入時，就相當于進入上一次調用的狀態(tài)，換種說法：進入上一次離開時所處邏輯流的位置；

線程是搶占式，而協(xié)程是協(xié)作式；

協(xié)程的優(yōu)點：

跨平臺

跨體系架構

無需線程上下文切換的開銷

無需原子操作鎖定及同步的開銷

方便切換控制流，簡化編程模型

高并發(fā) 高擴展性 低成本：一個CPU支持上萬的協(xié)程都不是問題。所以很適合用于高并發(fā)處理。

協(xié)程的缺點：

無法利用多核資源：協(xié)程的本質是個單線程,它不能同時將 單個CPU 的多個核用上,協(xié)程需要和進程配合才能運行在多CPU；

進行阻塞（Blocking）操作（如IO時）會阻塞掉整個程序：這一點和事件驅動一樣，可以使用異步IO操作來解決。

6、CGI的了解

答：CGI：通用網關接口（Common Gateway Interface）是一個Web服務器主機提供信息服務的標準接口。通過CGI接口，Web服務

器就能夠獲取客戶端提交的信息，轉交給服務器端的CGI程序進行處理，最后返回結果給客戶端。

CGI通信系統(tǒng)的組成是兩部分：一部分是html頁面，就是在用戶端瀏覽器上顯示的頁面。另一部分則是運行在服務器上的Cgi程序。

7、進程間通信方式和線程間通信方式

答：（1）進程間通信方式：

# 管道( pipe )：管道是一種半雙工的通信方式，數據只能單向流動，而且只能在具有親緣關系的進程間使用。進程的親緣關系通常是指父子進程關系。

# 信號量( semophore ) ：信號量是一個計數器，可以用來控制多個進程對共享資源的訪問。它常作為一種鎖機制，防止某進程正在訪問共享資源時，其他進程也訪問該資源。因此，主要作為進程間以及同一進程內不同線程之間的同步手段。

# 消息隊列( message queue ) ：消息隊列是由消息的鏈表，存放在內核中并由消息隊列標識符標識。消息隊列克服了信號傳遞信息少、管道只能承載無格式字節(jié)流以及緩沖區(qū)大小受限等缺點。

# 共享內存( shared memory ) ：共享內存就是映射一段能被其他進程所訪問的內存，這段共享內存由一個進程創(chuàng)建，但多個進程都可以訪問。共享內存是最快的 IPC 方式，它是針對其他進程間通信方式運行效率低而專門設計的。它往往與其他通信機制，如信號兩，配合使用，來實現(xiàn)進程間的同步和通信。

# 套接字( socket ) ：套解口也是一種進程間通信機制，與其他通信機制不同的是，它可用于不同及其間的進程通信。

（2）線程間通信方式：

#全局變量；

#Messages消息機制；

#CEvent對象（MFC中的一種線程通信對象，通過其觸發(fā)狀態(tài)的改變實現(xiàn)同步與通信）。

8、TCP握手與釋放

答：（1）握手

#第一次握手：主機A發(fā)送握手信號syn＝1和seq=x（隨機產生的序列號）的數據包到服務器，主機B由SYN=1知道，A要求建立聯(lián)機；

#第二次握手：主機B收到請求后要確認聯(lián)機信息，向A發(fā)送syn=1，ack=x（x是主機A的Seq） 1，以及隨機產生的確認端序列號

seq=y的包；

#第三次握手：主機A收到后檢查ack是否正確（ack=x 1），即第一次發(fā)送的seq 1，若正確，主機A會再發(fā)送ack=y 1，以及隨機序

列號seq=z，主機B收到后確認ack值則連接建立成功；

#完成三次握手，主機A與主機B開始傳送數據。

注：上述步驟中，第二和第三次確認包中都還包含一個標志位未予以說明，該標志位為1表示正常應答；

具體可見圖片：

為什么需要“三次握手”？

“三次握手”的目的是“為了防止已失效的連接請求報文段突然又傳送到了服務端，因而產生錯誤”。具體例如：client發(fā)出的第一個連接請求報文段并沒有丟失，而是在某個網絡結點長時間的滯留了，以致延誤到連接釋放以后的某個時間才到達server。本來這是一個早已失效的報文段。但server收到此失效的連接請求報文段后，就誤認為是client再次發(fā)出的一個新的連接請求。于是就向client發(fā)出確認報文段，同意建立連接。假設不采用“三次握手”，那么只要server發(fā)出確認，新的連接就建立了。由于現(xiàn)在client并沒有發(fā)出建立連接的請求，因此不會理睬server的確認，也不會向server發(fā)送數據。但server卻以為新的運輸連接已經建立，并一直等待client發(fā)來數據。這樣，server的很多資源就白白浪費掉了。采用“三次握手”的辦法可以防止上述現(xiàn)象發(fā)生。例如剛才那種情況，client不會向server的確認發(fā)出確認。server由于收不到確認，就知道client并沒有要求建立連接。主要目的防止server端一直等待，浪費資源。

（2）揮手

由于TCP連接是全雙工的，因此每個方向都必須單獨進行關閉。這原則是當一方完成它的數據發(fā)送任務后就能發(fā)送一個FIN來終止這個方向的連接。收到一個 FIN只意味著這一方向上沒有數據流動，一個TCP連接在收到一個FIN后仍能發(fā)送數據。首先進行關閉的一方將執(zhí)行主動關閉，而另一方執(zhí)行被動關閉。

(1) TCP客戶端發(fā)送一個FIN，用來關閉客戶到服務器的數據傳送(報文段4)；

(2) 服務器收到這個FIN，發(fā)回一個ACK，確認序號為收到的序號加1(報文段5)。和SYN一樣，一個FIN將占用一個序號；

(3) 服務器關閉客戶端的連接后，再發(fā)送一個FIN給客戶端(報文段6)；

(4) 客戶段收到服務端的FIN后，發(fā)回ACK報文確認，并將確認序號設置為收到序號加1(報文段7)；

注意：TCP連接的任何一方都可以發(fā)起揮手操作，上述步驟只是兩種之一；

具體過程見圖：

為什么是“四次揮手”？

因為當收到對方的FIN報文通知時，它僅僅表示對方沒有數據發(fā)送給你了；但未必你所有的數據都全部發(fā)送給對方了，所以你可能還需要發(fā)送一些數據給對方，再發(fā)送FIN報文給對方來表示你同意現(xiàn)在可以關閉連接了，故這里的ACK報文和FIN報文多數情況下都是分開發(fā)送的，也就造成了4次揮手。

握手，揮手過程中各狀態(tài)介紹：

（1）3次握手過程狀態(tài)：

#LISTEN: 這個也是非常容易理解的一個狀態(tài)，表示服務器端的某個SOCKET處于監(jiān)聽狀態(tài)，可以接受連接了。

#SYN_SENT: 當客戶端SOCKET執(zhí)行CONNECT連接時，它首先發(fā)送SYN報文，因此也隨即它會進入到了SYN_SENT狀態(tài)，并等待服務端的發(fā)送三次握手中的第2個報文。SYN_SENT狀態(tài)表示客戶端已發(fā)送SYN報文。(發(fā)送端)

#SYN_RCVD: 這個狀態(tài)與SYN_SENT遙想呼應這個狀態(tài)表示接受到了SYN報文，在正常情況下，這個狀態(tài)是服務器端的SOCKET在建立TCP連接時的三次握手會話過程中的一個中間狀態(tài)，很短暫，基本上用netstat你是很難看到這種狀態(tài)的，除非你特意寫了一個客戶端測試程序，故意將三次TCP握手過程中最后一個ACK報文不予發(fā)送。因此這種狀態(tài)時，當收到客戶端的ACK報文后，它會進入到ESTABLISHED狀態(tài)。(服務器端)

#ESTABLISHED：這個容易理解了，表示連接已經建立了。

（2）4次揮手過程狀態(tài)：

#FIN_WAIT_1: 這個狀態(tài)要好好解釋一下，其實FIN_WAIT_1和FIN_WAIT_2狀態(tài)的真正含義都是表示等待對方的FIN報文。而這兩種狀態(tài)的區(qū)別是：FIN_WAIT_1狀態(tài)實際上是當SOCKET在ESTABLISHED狀態(tài)時，它想主動關閉連接，向對方發(fā)送了FIN報文，此時該SOCKET即進入到FIN_WAIT_1狀態(tài)。而當對方回應ACK報文后，則進入到FIN_WAIT_2狀態(tài)，當然在實際的正常情況下，無論對方何種情況下，都應該馬上回應ACK報文，所以FIN_WAIT_1狀態(tài)一般是比較難見到的，而FIN_WAIT_2狀態(tài)還有時常常可以用netstat看到。(主動方)

#FIN_WAIT_2：上面已經詳細解釋了這種狀態(tài)，實際上FIN_WAIT_2狀態(tài)下的SOCKET，表示半連接，也即有一方要求close連接，但另外還告訴對方，我暫時還有點數據需要傳送給你(ACK信息)，稍后再關閉連接。(主動方)

#TIME_WAIT: 表示收到了對方的FIN報文，并發(fā)送出了ACK報文，就等2MSL后即可回到CLOSED可用狀態(tài)了。如果FIN_WAIT_1狀態(tài)下，收到了對方同時帶FIN標志和ACK標志的報文時，可以直接進入到TIME_WAIT狀態(tài)，而無須經過FIN_WAIT_2狀態(tài)。(主動方)

#CLOSING(比較少見): 這種狀態(tài)比較特殊，實際情況中應該是很少見，屬于一種比較罕見的例外狀態(tài)。正常情況下，當你發(fā)送FIN報文后，按理來說是應該先收到(或同時收到)對方的ACK報文，再收到對方的FIN報文。但是CLOSING狀態(tài)表示你發(fā)送FIN報文后，并沒有收到對方的ACK報文，反而卻也收到了對方的FIN報文。什么情況下會出現(xiàn)此種情況呢?其實細想一下，也不難得出結論：那就是如果雙方幾乎在同時close一個SOCKET的話，那么就出現(xiàn)了雙方同時發(fā)送FIN報文的情況，也即會出現(xiàn)CLOSING狀態(tài)，表示雙方都正在關閉SOCKET連接。

#CLOSE_WAIT: 這種狀態(tài)的含義其實是表示在等待關閉。怎么理解呢?當對方close一個SOCKET后發(fā)送FIN報文給自己，你系統(tǒng)毫無疑問地會回應一個ACK報文給對方，此時則進入到CLOSE_WAIT狀態(tài)。接下來呢，實際上你真正需要考慮的事情是察看你是否還有數據發(fā)送給對方，如果沒有的話，那么你也就可以close這個SOCKET，發(fā)送FIN報文給對方，也即關閉連接。所以你在CLOSE_WAIT狀態(tài)下，需要完成的事情是等待你去關閉連接。(被動方)

#LAST_ACK: 這個狀態(tài)還是比較容易好理解的，它是被動關閉一方在發(fā)送FIN報文后，最后等待對方的ACK報文。當收到ACK報文后，也即可以進入到CLOSED可用狀態(tài)了。(被動方)

9、http和https的區(qū)別？

答：HTTPS協(xié)議是由SSL HTTP協(xié)議構建的可進行加密傳輸、身份認證的網絡協(xié)議，要比http協(xié)議安全。

HTTPS（Secure Hypertext Transfer Protocol）安全超文本傳輸協(xié)議，與http主要區(qū)別在于：

#http是超文本傳輸協(xié)議，信息是明文傳輸，https 則是具有安全性的ssl加密傳輸協(xié)議；

#http和https使用的是完全不同的連接方式用的端口也不一樣,前者是80,后者是443；

下面具體介紹一下HTTP和HTTPS協(xié)議：

首先說明一下：HTTP和HTTPS協(xié)議是應用層協(xié)議；

上圖充分表明：HTTP是應用層協(xié)議，并且HTTPS是在HTTP協(xié)議基礎上添加SSL等加密策略后的協(xié)議；

TLS/SSL中使用了非對稱加密，對稱加密以及HASH算法。

（1）Http協(xié)議

1）HTTP協(xié)議和TCP協(xié)議之間的區(qū)別聯(lián)系

①TPC/IP協(xié)議是傳輸層協(xié)議，主要解決數據如何在網絡中傳輸，而HTTP是應用層協(xié)議，主要解決如何包裝數據；

②HTTP的默認端口號是80，TCP/IP協(xié)議通信編程時端口號需要自己指定（例如socket編程）；

③HTTP協(xié)議是在TCP/IP協(xié)議基礎上實現(xiàn)的，即HTTP數據包是經過TCP/IP協(xié)議實現(xiàn)傳輸的；

④HTTP是無狀態(tài)的短連接協(xié)議，TCP是有狀態(tài)的長連接協(xié)議；

HTTP是在有狀態(tài)長連接TCP/IP協(xié)議的基礎上實現(xiàn)的，為什么卻是無狀態(tài)短連接協(xié)議？

答：因為HTTP協(xié)議每次請求結束就會自動關閉連接，這樣就變成了短連接；

短連接又導致了該次請求相關信息的丟失，也就造成了HTTP協(xié)議對于前期事務處理沒有記憶能力，故為無狀態(tài)協(xié)議。

2）HTTP協(xié)議其完整的工作過程可分為四步：

①連接：首先客戶機與服務器需要建立連接（由TCP/IP握手連接實現(xiàn)）。只要單擊某個超級鏈接，HTTP的工作開始；

②請求：建立連接后，客戶機發(fā)送一個請求給服務器，請求方式的格式為：統(tǒng)一資源標識符（URL）、協(xié)議版本號，后邊是MIME信息包括請求修飾符、客戶機信息和可能的內容；

③應答：服務器接到請求后，給予相應的響應信息，其格式為一個狀態(tài)行，包括信息的協(xié)議版本號、一個成功或錯誤的代碼，后邊是MIME信息包括服務器信息、實體信息和可能的內容?？蛻舳私邮辗掌魉祷氐男畔⑼ㄟ^瀏覽器顯示在用戶的顯示屏上；

④關閉：當應答結束后，瀏覽器和服務器關閉連接，以保證其他瀏覽器可以與服務器進行連接。

更完整的過程可能如下：

域名解析 --> 發(fā)起TCP的3次握手 --> 建立TCP連接后發(fā)起http請求 --> 服務器響應http請求，瀏覽器得到html代碼 --> 瀏覽器解析html代碼，并請求html代碼中的資源（如js、css、圖片等） --> 瀏覽器對頁面進行渲染呈現(xiàn)給用戶。

如果在以上過程中的某一步出現(xiàn)錯誤，那么產生錯誤的信息將返回到客戶端，有顯示屏輸出。對于用戶來說，這些過程是由HTTP自己完成的，用戶只要用鼠標點擊，等待信息顯示就可以了。

（2）Https協(xié)議

HTTPS握手過程包括五步：

1）瀏覽器請求連接；

2）服務器返回證書：證書里面包含了網站地址，加密公鑰，以及證書的頒發(fā)機構等信息。

3）瀏覽器收到證書后作以下工作：

a) 驗證證書的合法性；

b) 生成隨機（對稱）密碼，取出證書中提供的公鑰對隨機密碼加密；

c) 將之前生成的加密隨機密碼等信息發(fā)送給網站；

4）服務器收到消息后作以下的操作：

a) 使用自己的私鑰解密瀏覽器用公鑰加密后的消息，并驗證HASH是否與瀏覽器發(fā)來的一致；

b) 使用加密的隨機對稱密碼加密一段消息，發(fā)送給瀏覽器；

5）瀏覽器解密并計算握手消息的HASH：如果與服務端發(fā)來的HASH一致，此時握手過程結束，之后所有的通信數據將由之前瀏覽

器生成的隨機密碼并利用對稱加密算法進行加密。

注意：服務器有兩個密鑰，一個公鑰、一個私鑰，只有私鑰才可以解密公鑰加密的消息；

如圖：

或者如下圖：

HTTPS協(xié)議、SSL、和數字證書的關系介紹：

概述：對于HTTPS協(xié)議，所有的消息都是經過SSL協(xié)議方式加密，而支持加密的文件正是數字證書；

（1）SSL

SSL常用的加密算法：對稱密碼算法、非對稱密碼算法、散列算法；

SSL的加密過程：需要注意的是非對稱加解密算法的效率要比對稱加解密要低的多。所以SSL在握手過程中使用非對稱密碼算法來

協(xié)商密鑰，實際使用對稱加解密的方法對http內容加密傳輸；

（2）數字證書

數字證書是用于在INTERNET上標識個人或者機構身份的一種技術手段，它通過由一些公認的權威機構所認證，從而可以保證其

安全地被應用在各種場合。證書里面包含了網站地址，加密公鑰，以及證書的頒發(fā)機構等信息。

10、虛擬內存的概念與介紹

答：虛擬內存中，允許將一個作業(yè)分多次調入內存，需要時就調入，不需要的就先放在外存。因此，虛擬內存的實需要建立在離散

分配的內存管理方式的基礎上。虛擬內存的實現(xiàn)有以下三種方式：

#請求分頁存儲管理

#請求分段存儲管理

#請求段頁式存儲管理

虛擬內存的意義：

一，虛擬內存可以使得物理內存更加高效。虛擬內存使用置換方式，需要的頁就置換進來，不需要的置換出去，使得內存中只保存了需要的頁，提高了利用率，也避免了不必要的寫入與擦除；

二，使用虛擬地址可以使內存的管理更加便捷。在程序編譯的時候就會生成虛擬地址，該虛擬地址并不是對應一個物理地址，使得也就極大地減少了地址被占用的沖突，減少管理難度；

三，為了安全性的考慮。在使用虛擬地址的時候，暴露給程序員永遠都是虛擬地址，而具體的物理地址在哪里，這個只有系統(tǒng)才了解。這樣就提

高了系統(tǒng)的封裝性。

11、單鏈表的反轉算法

答：思想：創(chuàng)建3個指針，分別指向上一個節(jié)點、當前節(jié)點、下一個節(jié)點，遍歷整個鏈表的同時，將正在訪問的節(jié)點指向上一個節(jié)點，當遍歷結束后，就同時完成了鏈表的反轉。

實現(xiàn)代碼：

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）紅黑樹來源于二叉搜索樹，其在關聯(lián)容器如map中應用廣泛，主要優(yōu)勢在于其查找、刪除、插入時間復雜度小，但其也有缺點，就是容易偏向一邊而變成一個鏈表。

紅黑樹是一種二叉查找樹，但在每個結點上增加一個存儲位表示結點的顏色，可以是Red或Black。也就是說，紅黑樹是在二叉

查找樹基礎上進一步實現(xiàn)的；

紅黑樹的五個性質：

性質1. 節(jié)點是紅色或黑色；

性質2. 根節(jié)點是黑色；

性質3 每個葉節(jié)點（指樹的末端的NIL指針節(jié)點或者空節(jié)點）是黑色的；

性質4 每個紅色節(jié)點的兩個子節(jié)點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點)；

性質5. 從任一節(jié)點到其每個尾端NIL節(jié)點或者NULL節(jié)點的所有路徑都包含相同數目的黑色節(jié)點。

（注：上述第3、5點性質中所說的NIL或者NULL結點，并不包含數據，只充當樹的路徑結束的標志，即此葉結點非常見的葉子結點）。

因為一棵由n個結點隨機構造的二叉查找樹的高度為lgn，所以順理成章，二叉查找樹的一般操作的執(zhí)行時間為O(lgn)。但二叉查

找樹若退化成了一棵具有n個結點的線性鏈后，則這些操作最壞情況運行時間為O(n)；

紅黑樹雖然本質上是一棵二叉查找樹，但它在二叉查找樹的基礎上增加以上五個性質使得紅黑樹相對平衡，從而保證了

紅黑樹的查找、插入、刪除的時間復雜度最壞為O(log n)。

（2）左旋右旋

紅黑樹插入或刪除后，一般就會改變紅黑樹的特性，要恢復紅黑樹上述5個性質，一般都要那就要做2方面的工作：

1、部分結點顏色，重新著色

2、調整部分指針的指向，即左旋、右旋。

左選右旋如圖所示：

左旋，如圖所示（左->右），以x->y之間的鏈為“支軸”進行，使y成為該新子樹的根，x成為y的左孩子，而y的左孩子則成為x的右孩

子。算法很簡單，旋轉后各個結點從左往右，仍然都是從小到大。

左旋代碼實現(xiàn)，分三步:

（1） 開始變化，y的左孩子成為x的右孩子；

（2） y成為x的父結點；

（3） x成為y的左孩子；

右旋類似，不再累述；

13、KMP字符串匹配

（1）KMP匹配算法代碼實現(xiàn)：

int KmpSearch(char* s, char* p)
{
int i = 0;
int j = 0;
int sLen = strlen(s);
int pLen = strlen(p);
while (i < sLen