騰訊?C ?筆試/面試題及答案

↓推薦關(guān)注↓

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

問題點(diǎn)：

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

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

答：（1）C語言特點(diǎn)：

1.作為一種面向過程的結(jié)構(gòu)化語言，易于調(diào)試和維護(hù)；

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

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

4.C語言還具有效率高，可移植性強(qiáng)等特點(diǎn)。

（2）C 語言特點(diǎn)：

1.在C語言的基礎(chǔ)上進(jìn)行擴(kuò)充和完善，使C 兼容了C語言的面向過程特點(diǎn)，又成為了一種面向?qū)ο蟮某绦蛟O(shè)計(jì)語言；

2.可以使用抽象數(shù)據(jù)類型進(jìn)行基于對(duì)象的編程；

3.可以使用多繼承、多態(tài)進(jìn)行面向?qū)ο蟮木幊蹋?/p>4.可以擔(dān)負(fù)起以模版為特征的泛型化編程。

C 與C語言的本質(zhì)差別：在于C 是面向?qū)ο蟮?，而C語言是面向過程的?；蛘哒fC 是在C語言的基礎(chǔ)上增加了面向?qū)ο蟪绦蛟O(shè)

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

2、C 的多態(tài)

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

調(diào)用相應(yīng)的函數(shù)。如果對(duì)象類型是派生類，就調(diào)用派生類的函數(shù)；如果對(duì)象類型是基類，就調(diào)用基類的函數(shù)。

1）：用virtual關(guān)鍵字申明的函數(shù)叫做虛函數(shù)，虛函數(shù)肯定是類的成員函數(shù)；

2）：存在虛函數(shù)的類都有一個(gè)一維的虛函數(shù)表叫做虛表，類的對(duì)象有一個(gè)指向虛表開始的虛指針。虛表是和類對(duì)應(yīng)的，虛表指針是

和對(duì)象對(duì)應(yīng)的；

3）：多態(tài)性是一個(gè)接口多種實(shí)現(xiàn)，是面向?qū)ο蟮暮诵?，分為類的多態(tài)性和函數(shù)的多態(tài)性。；

4）：多態(tài)用虛函數(shù)來實(shí)現(xiàn)，結(jié)合動(dòng)態(tài)綁定.；

5）：純虛函數(shù)是虛函數(shù)再加上 = 0；

6）：抽象類是指包括至少一個(gè)純虛函數(shù)的類；

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

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

答：簡單地說，每一個(gè)含有虛函數(shù)（無論是其本身的，還是繼承而來的）的類都至少有一個(gè)與之對(duì)應(yīng)的虛函數(shù)表，其中存放著該類

所有的虛函數(shù)對(duì)應(yīng)的函數(shù)指針。例：

其中：

B的虛函數(shù)表中存放著B::foo和B::bar兩個(gè)函數(shù)指針。

D的虛函數(shù)表中存放的既有繼承自B的虛函數(shù)B::foo，又有重寫（override）了基類虛函數(shù)B::bar的D::bar，還有新增的虛函數(shù)D::quz。

虛函數(shù)表構(gòu)造過程：

從編譯器的角度來說，B的虛函數(shù)表很好構(gòu)造，D的虛函數(shù)表構(gòu)造過程相對(duì)復(fù)雜。下面給出了構(gòu)造D的虛函數(shù)表的一種方式（僅供參考）：

虛函數(shù)調(diào)用過程

以下面的程序?yàn)槔?/p>

4、C和C 內(nèi)存分配問題

答：（1）C語言編程中的內(nèi)存基本構(gòu)成

C的內(nèi)存基本上分為4部分：靜態(tài)存儲(chǔ)區(qū)、堆區(qū)、棧區(qū)以及常量區(qū)。他們的功能不同，對(duì)他們使用方式也就不同。

1.棧 ——由編譯器自動(dòng)分配釋放；

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

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

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

4.另外還有一個(gè)專門放常量的地方，程序結(jié)束釋放；

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

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

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

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

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

(f)在函數(shù)體內(nèi)定義的static表示只在該函數(shù)體內(nèi)有效；

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

（2）C 編程中的內(nèi)存基本構(gòu)造

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

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

2、堆，就是那些由new分配的內(nèi)存塊，他們的釋放編譯器不去管，由我們的應(yīng)用程序去控制，一般一個(gè)new就要對(duì)應(yīng)一個(gè)delete。如

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

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

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

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

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

內(nèi)存模型組成部分：自由存儲(chǔ)區(qū)，動(dòng)態(tài)區(qū)、靜態(tài)區(qū)；

根據(jù)c/c 對(duì)象生命周期不同，c/c 的內(nèi)存模型有三種不同的內(nèi)存區(qū)域，即：自由存儲(chǔ)區(qū)，動(dòng)態(tài)區(qū)、靜態(tài)區(qū)。

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

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

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

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

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

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

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

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

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

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

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

主要基于以下考慮：

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

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

#全局?jǐn)?shù)據(jù)和靜態(tài)數(shù)據(jù)有可能在整個(gè)程序執(zhí)行過程中都需要訪問，因此單獨(dú)存儲(chǔ)管理。

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

還有騰訊，阿里，京東等一線大廠面試題及答案整理，因篇幅有限，需要集錦的朋友可以 qun720209036免費(fèi)獲取。

5、協(xié)程

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

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

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

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

跨平臺(tái)

跨體系架構(gòu)

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

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

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

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

協(xié)程的缺點(diǎn)：

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

進(jìn)行阻塞（Blocking）操作（如IO時(shí)）會(huì)阻塞掉整個(gè)程序：這一點(diǎn)和事件驅(qū)動(dòng)一樣，可以使用異步IO操作來解決。

6、CGI的了解

答：CGI：通用網(wǎng)關(guān)接口（Common Gateway Interface）是一個(gè)Web服務(wù)器主機(jī)提供信息服務(wù)的標(biāo)準(zhǔn)接口。通過CGI接口，Web服務(wù)

器就能夠獲取客戶端提交的信息，轉(zhuǎn)交給服務(wù)器端的CGI程序進(jìn)行處理，最后返回結(jié)果給客戶端。

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

7、進(jìn)程間通信方式和線程間通信方式

答：（1）進(jìn)程間通信方式：

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

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

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

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

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

（2）線程間通信方式：

#全局變量；

#Messages消息機(jī)制；

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

8、TCP握手與釋放

答：（1）握手

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

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

seq=y的包；

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

列號(hào)seq=z，主機(jī)B收到后確認(rèn)ack值則連接建立成功；

#完成三次握手，主機(jī)A與主機(jī)B開始傳送數(shù)據(jù)。

注：上述步驟中，第二和第三次確認(rèn)包中都還包含一個(gè)標(biāo)志位未予以說明，該標(biāo)志位為1表示正常應(yīng)答；

具體可見圖片：

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

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

（2）揮手

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

(1) TCP客戶端發(fā)送一個(gè)FIN，用來關(guān)閉客戶到服務(wù)器的數(shù)據(jù)傳送(報(bào)文段4)；

(2) 服務(wù)器收到這個(gè)FIN，發(fā)回一個(gè)ACK，確認(rèn)序號(hào)為收到的序號(hào)加1(報(bào)文段5)。和SYN一樣，一個(gè)FIN將占用一個(gè)序號(hào)；

(3) 服務(wù)器關(guān)閉客戶端的連接后，再發(fā)送一個(gè)FIN給客戶端(報(bào)文段6)；

(4) 客戶段收到服務(wù)端的FIN后，發(fā)回ACK報(bào)文確認(rèn)，并將確認(rèn)序號(hào)設(shè)置為收到序號(hào)加1(報(bào)文段7)；

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

具體過程見圖：

為什么是“四次揮手”？

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

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

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

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

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

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

#ESTABLISHED：這個(gè)容易理解了，表示連接已經(jīng)建立了。

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

#FIN_WAIT_1: 這個(gè)狀態(tài)要好好解釋一下，其實(shí)FIN_WAIT_1和FIN_WAIT_2狀態(tài)的真正含義都是表示等待對(duì)方的FIN報(bào)文。而這兩種狀態(tài)的區(qū)別是：FIN_WAIT_1狀態(tài)實(shí)際上是當(dāng)SOCKET在ESTABLISHED狀態(tài)時(shí)，它想主動(dòng)關(guān)閉連接，向?qū)Ψ桨l(fā)送了FIN報(bào)文，此時(shí)該SOCKET即進(jìn)入到FIN_WAIT_1狀態(tài)。而當(dāng)對(duì)方回應(yīng)ACK報(bào)文后，則進(jìn)入到FIN_WAIT_2狀態(tài)，當(dāng)然在實(shí)際的正常情況下，無論對(duì)方何種情況下，都應(yīng)該馬上回應(yīng)ACK報(bào)文，所以FIN_WAIT_1狀態(tài)一般是比較難見到的，而FIN_WAIT_2狀態(tài)還有時(shí)常?？梢杂胣etstat看到。(主動(dòng)方)

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

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

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

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

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

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

答：HTTPS協(xié)議是由SSL HTTP協(xié)議構(gòu)建的可進(jìn)行加密傳輸、身份認(rèn)證的網(wǎng)絡(luò)協(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é)議是應(yīng)用層協(xié)議；

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

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

（1）Http協(xié)議

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

①TPC/IP協(xié)議是傳輸層協(xié)議，主要解決數(shù)據(jù)如何在網(wǎng)絡(luò)中傳輸，而HTTP是應(yīng)用層協(xié)議，主要解決如何包裝數(shù)據(jù)；

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

③HTTP協(xié)議是在TCP/IP協(xié)議基礎(chǔ)上實(shí)現(xiàn)的，即HTTP數(shù)據(jù)包是經(jīng)過TCP/IP協(xié)議實(shí)現(xiàn)傳輸?shù)模?/p>④HTTP是無狀態(tài)的短連接協(xié)議，TCP是有狀態(tài)的長連接協(xié)議；

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

答：因?yàn)镠TTP協(xié)議每次請(qǐng)求結(jié)束就會(huì)自動(dòng)關(guān)閉連接，這樣就變成了短連接；

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

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

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

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

③應(yīng)答：服務(wù)器接到請(qǐng)求后，給予相應(yīng)的響應(yīng)信息，其格式為一個(gè)狀態(tài)行，包括信息的協(xié)議版本號(hào)、一個(gè)成功或錯(cuò)誤的代碼，后邊是MIME信息包括服務(wù)器信息、實(shí)體信息和可能的內(nèi)容?？蛻舳私邮辗?wù)器所返回的信息通過瀏覽器顯示在用戶的顯示屏上；

④關(guān)閉：當(dāng)應(yīng)答結(jié)束后，瀏覽器和服務(wù)器關(guān)閉連接，以保證其他瀏覽器可以與服務(wù)器進(jìn)行連接。

更完整的過程可能如下：

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

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

（2）Https協(xié)議

HTTPS握手過程包括五步：

1）瀏覽器請(qǐng)求連接；

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

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

a) 驗(yàn)證證書的合法性；

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

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

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

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

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

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

器生成的隨機(jī)密碼并利用對(duì)稱加密算法進(jìn)行加密。

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

如圖：

或者如下圖：

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

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

（1）SSL

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

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

協(xié)商密鑰，實(shí)際使用對(duì)稱加解密的方法對(duì)http內(nèi)容加密傳輸；

（2）數(shù)字證書

數(shù)字證書是用于在INTERNET上標(biāo)識(shí)個(gè)人或者機(jī)構(gòu)身份的一種技術(shù)手段，它通過由一些公認(rèn)的權(quán)威機(jī)構(gòu)所認(rèn)證，從而可以保證其

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

10、虛擬內(nèi)存的概念與介紹

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

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

#請(qǐng)求分頁存儲(chǔ)管理

#請(qǐng)求分段存儲(chǔ)管理

#請(qǐng)求段頁式存儲(chǔ)管理

虛擬內(nèi)存的意義：

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

二，使用虛擬地址可以使內(nèi)存的管理更加便捷。在程序編譯的時(shí)候就會(huì)生成虛擬地址，該虛擬地址并不是對(duì)應(yīng)一個(gè)物理地址，使得也就極大地減少了地址被占用的沖突，減少管理難度；

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

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

11、單鏈表的反轉(zhuǎn)算法

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

實(shí)現(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、紅黑樹以及其查找復(fù)雜度

答：（1）紅黑樹來源于二叉搜索樹，其在關(guān)聯(lián)容器如map中應(yīng)用廣泛，主要優(yōu)勢(shì)在于其查找、刪除、插入時(shí)間復(fù)雜度小，但其也有缺點(diǎn)，就是容易偏向一邊而變成一個(gè)鏈表。

紅黑樹是一種二叉查找樹，但在每個(gè)結(jié)點(diǎn)上增加一個(gè)存儲(chǔ)位表示結(jié)點(diǎn)的顏色，可以是Red或Black。也就是說，紅黑樹是在二叉

查找樹基礎(chǔ)上進(jìn)一步實(shí)現(xiàn)的；

紅黑樹的五個(gè)性質(zhì)：

性質(zhì)1. 節(jié)點(diǎn)是紅色或黑色；

性質(zhì)2. 根節(jié)點(diǎn)是黑色；

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

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

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

（注：上述第3、5點(diǎn)性質(zhì)中所說的NIL或者NULL結(jié)點(diǎn)，并不包含數(shù)據(jù)，只充當(dāng)樹的路徑結(jié)束的標(biāo)志，即此葉結(jié)點(diǎn)非常見的葉子結(jié)點(diǎn)）。

因?yàn)橐豢糜蒼個(gè)結(jié)點(diǎn)隨機(jī)構(gòu)造的二叉查找樹的高度為lgn，所以順理成章，二叉查找樹的一般操作的執(zhí)行時(shí)間為O(lgn)。但二叉查

找樹若退化成了一棵具有n個(gè)結(jié)點(diǎn)的線性鏈后，則這些操作最壞情況運(yùn)行時(shí)間為O(n)；

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

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

（2）左旋右旋

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

1、部分結(jié)點(diǎn)顏色，重新著色

2、調(diào)整部分指針的指向，即左旋、右旋。

左選右旋如圖所示：

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

子。算法很簡單，旋轉(zhuǎn)后各個(gè)結(jié)點(diǎn)從左往右，仍然都是從小到大。

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

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

（2） y成為x的父結(jié)點(diǎn)；

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

右旋類似，不再累述；

13、KMP字符串匹配

（1）KMP匹配算法代碼實(shí)現(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