簡(jiǎn)單題（本題共30分）

請(qǐng)簡(jiǎn)述Tcp-ip的3次握手以及4次揮手過(guò)程？并解釋為何關(guān)閉連接需要4次揮手(10分)

詳細(xì)答案參見(jiàn)TCP/IP協(xié)議三次握手與四次握手流程解析

TCP三次握手、四次揮手過(guò)程如下:

通常情況下，一個(gè)正常的TCP連接，都會(huì)有三個(gè)階段:1、TCP三次握手; 2、數(shù)據(jù)傳送; 3、TCP四次揮手

• SYN: (同步序列編號(hào),Synchronize Sequence Numbers)該標(biāo)志僅在三次握手建立TCP連接時(shí)有效。表示一個(gè)新的TCP連接請(qǐng)求。
• ACK: (確認(rèn)編號(hào),Acknowledgement Number)是對(duì)TCP請(qǐng)求的確認(rèn)標(biāo)志,同時(shí)提示對(duì)端系統(tǒng)已經(jīng)成功接收所有數(shù)據(jù)。
• FIN: (結(jié)束標(biāo)志,FINish)用來(lái)結(jié)束一個(gè)TCP回話(huà).但對(duì)應(yīng)端口仍處于開(kāi)放狀態(tài),準(zhǔn)備接收后續(xù)數(shù)據(jù)。

四次揮手的原因：

這是因?yàn)榉?wù)端的LISTEN狀態(tài)下的SOCKET當(dāng)收到SYN報(bào)文的建連請(qǐng)求后，它可以把ACK和SYN（ACK起應(yīng)答作用，而SYN起同步作用）放在一個(gè)報(bào)文里來(lái)發(fā)送。但關(guān)閉連接時(shí)，當(dāng)收到對(duì)方的FIN報(bào)文通知時(shí)，它僅僅表示對(duì)方?jīng)]有數(shù)據(jù)發(fā)送給你了；但未必你所有的數(shù)據(jù)都全部發(fā)送給對(duì)方了，所以你可以未必會(huì)馬上會(huì)關(guān)閉SOCKET,也即你可能還需要發(fā)送一些數(shù)據(jù)給對(duì)方之后，再發(fā)送FIN報(bào)文給對(duì)方來(lái)表示你同意現(xiàn)在可以關(guān)閉連接了，所以它這里的ACK報(bào)文和FIN報(bào)文多數(shù)情況下都是分開(kāi)發(fā)送的。

不能兩次握手連接的原因：

3次握手完成兩個(gè)重要的功能，既要雙方做好發(fā)送數(shù)據(jù)的準(zhǔn)備工作(雙方都知道彼此已準(zhǔn)備好)，也要允許雙方就初始序列號(hào)進(jìn)行協(xié)商，這個(gè)序列號(hào)在握手過(guò)程中被發(fā)送和確認(rèn)。

現(xiàn)在把三次握手改成僅需要兩次握手，死鎖是可能發(fā)生的。作為例子，考慮計(jì)算機(jī)S和C之間的通信，假定C給S發(fā)送一個(gè)連接請(qǐng)求分組，S收到了這個(gè)分組，并發(fā)送了確認(rèn)應(yīng)答分組。按照兩次握手的協(xié)定，S認(rèn)為連接已經(jīng)成功地建立了，可以開(kāi)始發(fā)送數(shù)據(jù)分組。可是，C在S的應(yīng)答分組在傳輸中被丟失的情況下，將不知道S是否已準(zhǔn)備好，不知道S建立什么樣的序列號(hào)，C甚至懷疑S是否收到自己的連接請(qǐng)求分組。在這種情況下，C認(rèn)為連接還未建立成功，將忽略S發(fā)來(lái)的任何數(shù)據(jù)分組，只等待連接確認(rèn)應(yīng)答分組。而S在發(fā)出的分組超時(shí)后，重復(fù)發(fā)送同樣的分組。這樣就形成了死鎖。

SYN攻擊

在三次握手過(guò)程中，服務(wù)器發(fā)送SYN-ACK之后，收到客戶(hù)端的ACK之前的TCP連接稱(chēng)為半連接(half-open connect).此時(shí)服務(wù)器處于Syn_RECV狀態(tài).當(dāng)收到ACK后，服務(wù)器轉(zhuǎn)入ESTABLISHED狀態(tài).

Syn攻擊就是 攻擊客戶(hù)端 在短時(shí)間內(nèi)偽造大量不存在的IP地址，向服務(wù)器不斷地發(fā)送syn包，服務(wù)器回復(fù)確認(rèn)包，并等待客戶(hù)的確認(rèn)，由于源地址是不存在的，服務(wù)器需要不斷的重發(fā)直 至超時(shí)，這些偽造的SYN包將長(zhǎng)時(shí)間占用未連接隊(duì)列，正常的SYN請(qǐng)求被丟棄，目標(biāo)系統(tǒng)運(yùn)行緩慢，嚴(yán)重者引起網(wǎng)絡(luò)堵塞甚至系統(tǒng)癱瘓。

Syn攻擊是一個(gè)典型的DDOS攻擊。檢測(cè)SYN攻擊非常的方便，當(dāng)你在服務(wù)器上看到大量的半連接狀態(tài)時(shí)，特別是源IP地址是隨機(jī)的，基本上可以斷定這是一次SYN攻擊.在Linux下可以如下命令檢測(cè)是否被Syn攻擊

netstat -n -p TCP | grep SYN_RECV

一般較新的TCP/IP協(xié)議棧都對(duì)這一過(guò)程進(jìn)行修正來(lái)防范Syn攻擊，修改tcp協(xié)議實(shí)現(xiàn)。主要方法有SynAttackProtect保護(hù)機(jī)制、SYN cookies技術(shù)、增加最大半連接和縮短超時(shí)時(shí)間等.但是不能完全防范syn攻擊。

2MSL TIME_WAIT狀態(tài)

TIME_WAIT狀態(tài)的存在有兩個(gè)理由：（1）讓4次握手關(guān)閉流程更加可靠；4次握手的最后一個(gè)ACK是是由主動(dòng)關(guān)閉方發(fā)送出去的，若這個(gè)ACK丟失，被動(dòng)關(guān)閉方會(huì)再次發(fā)一個(gè)FIN過(guò)來(lái)。若主動(dòng)關(guān)閉方能夠保持一個(gè)2MSL的TIME_WAIT狀態(tài)，則有更大的機(jī)會(huì)讓丟失的ACK被再次發(fā)送出去。（2）防止lost duplicate對(duì)后續(xù)新建正常鏈接的傳輸造成破壞。lost duplicate在實(shí)際的網(wǎng)絡(luò)中非常常見(jiàn)，經(jīng)常是由于路由器產(chǎn)生故障，路徑無(wú)法收斂，導(dǎo)致一個(gè)packet在路由器A，B，C之間做類(lèi)似死循環(huán)的跳轉(zhuǎn)。IP頭部有個(gè)TTL，限制了一個(gè)包在網(wǎng)絡(luò)中的最大跳數(shù)，因此這個(gè)包有兩種命運(yùn)，要么最后TTL變?yōu)?，在網(wǎng)絡(luò)中消失；要么TTL在變?yōu)?之前路由器路徑收斂，它憑借剩余的TTL跳數(shù)終于到達(dá)目的地。但非常可惜的是TCP通過(guò)超時(shí)重傳機(jī)制在早些時(shí)候發(fā)送了一個(gè)跟它一模一樣的包，并先于它達(dá)到了目的地，因此它的命運(yùn)也就注定被TCP協(xié)議棧拋棄。另外一個(gè)概念叫做incarnation connection，指跟上次的socket pair一摸一樣的新連接，叫做incarnation of previous connection。lost duplicate加上incarnation connection，則會(huì)對(duì)我們的傳輸造成致命的錯(cuò)誤。大家都知道TCP是流式的，所有包到達(dá)的順序是不一致的，依靠序列號(hào)由TCP協(xié)議棧做順序的拼接；假設(shè)一個(gè)incarnation connection這時(shí)收到的seq=1000, 來(lái)了一個(gè)lost duplicate為seq=1000, len=1000, 則tcp認(rèn)為這個(gè)lost duplicate合法，并存放入了receive buffer，導(dǎo)致傳輸出現(xiàn)錯(cuò)誤。通過(guò)一個(gè)2MSL TIME_WAIT狀態(tài)，確保所有的lost duplicate都會(huì)消失掉，避免對(duì)新連接造成錯(cuò)誤。

該狀態(tài)為什么設(shè)計(jì)在主動(dòng)關(guān)閉這一方：
（1）發(fā)最后ack的是主動(dòng)關(guān)閉一方
（2）只要有一方保持TIME_WAIT狀態(tài)，就能起到避免incarnation connection在2MSL內(nèi)的重新建立，不需要兩方都有

如何正確對(duì)待2MSL TIME_WAIT

RFC要求socket pair在處于TIME_WAIT時(shí)，不能再起一個(gè)incarnation connection。但絕大部分TCP實(shí)現(xiàn)，強(qiáng)加了更為嚴(yán)格的限制。在2MSL等待期間，socket中使用的本地端口在默認(rèn)情況下不能再被使用。若A 10.234.5.5:1234和B 10.55.55.60:6666建立了連接，A主動(dòng)關(guān)閉，那么在A(yíng)端只要port為1234，無(wú)論對(duì)方的port和ip是什么，都不允許再起服務(wù)。顯而易見(jiàn)這是比RFC更為嚴(yán)格的限制，RFC僅僅是要求socket pair不一致，而實(shí)現(xiàn)當(dāng)中只要這個(gè)port處于TIME_WAIT，就不允許起連接。這個(gè)限制對(duì)主動(dòng)打開(kāi)方來(lái)說(shuō)是無(wú)所謂的，因?yàn)橐话阌玫氖桥R時(shí)端口；但對(duì)于被動(dòng)打開(kāi)方，一般是server，就悲劇了，因?yàn)閟erver一般是熟知端口。比如http，一般端口是80，不可能允許這個(gè)服務(wù)在2MSL內(nèi)不能起來(lái)。解決方案是給服務(wù)器的socket設(shè)置SO_REUSEADDR選項(xiàng)，這樣的話(huà)就算熟知端口處于TIME_WAIT狀態(tài)，在這個(gè)端口上依舊可以將服務(wù)啟動(dòng)。當(dāng)然，雖然有了SO_REUSEADDR選項(xiàng)，但sockt pair這個(gè)限制依舊存在。比如上面的例子，A通過(guò)SO_REUSEADDR選項(xiàng)依舊在1234端口上起了監(jiān)聽(tīng)，但這時(shí)我們?nèi)羰菑腂通過(guò)6666端口去連它，TCP協(xié)議會(huì)告訴我們連接失敗，原因?yàn)锳ddress already in use.

操作系統(tǒng)的內(nèi)存管理淘汰算法有哪些,請(qǐng)列出并簡(jiǎn)要說(shuō)明？(10分)

進(jìn)程運(yùn)行時(shí)，若其訪(fǎng)問(wèn)的頁(yè)面不在內(nèi)存而需將其調(diào)入，但內(nèi)存已無(wú)空閑空間時(shí)，就需要從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)，送入磁盤(pán)的兌換區(qū)。選擇調(diào)出頁(yè)面的算法就稱(chēng)為頁(yè)面置換算法。好的頁(yè)面置換算法應(yīng)有較低的頁(yè)面更換頻率。

• 最佳（OPT）置換算法是理論算法，它將不再使用的頁(yè)面換出，而實(shí)際中不能預(yù)知哪個(gè)頁(yè)面不再使用，但是這個(gè)算法是最優(yōu)算法，可以作為評(píng)測(cè)其他算法的性能。
• 先進(jìn)先出(FIFO)置換算法優(yōu)先淘汰最先進(jìn)入內(nèi)存中的頁(yè)面。該算法實(shí)現(xiàn)簡(jiǎn)單，但算法跟內(nèi)存的實(shí)際運(yùn)行規(guī)律不符，不管該頁(yè)面是否經(jīng)常使用，這樣就有可能導(dǎo)致缺頁(yè)率增加，導(dǎo)致頁(yè)面置換次數(shù)增加。
• 最近最少(LRU：least recently used)使用置換算法當(dāng)需要淘汰某頁(yè)，選擇離當(dāng)前時(shí)間最近的一段時(shí)間內(nèi)最久沒(méi)有使用過(guò)的頁(yè)先淘汰。在這里采用一個(gè)頁(yè)面集大小的棧存儲(chǔ)最近訪(fǎng)問(wèn)的頁(yè)面。頁(yè)面按時(shí)間順序壓如棧中。如果被訪(fǎng)問(wèn)的頁(yè)在棧中，則從棧中移出頁(yè)面，壓入棧頂。這樣棧底記錄離當(dāng)前時(shí)間最近的一段時(shí)間內(nèi)最久沒(méi)有使用過(guò)的頁(yè)。
• 最不經(jīng)常使用(LFU:least frequently used)置換算法 LFU在需要淘汰某一頁(yè)時(shí)，首先淘汰到當(dāng)前時(shí)間為止、被訪(fǎng)問(wèn)次數(shù)最少的那一頁(yè)。這只要在頁(yè)面集中給每一頁(yè)增設(shè)一個(gè)訪(fǎng)問(wèn)計(jì)數(shù)器即可實(shí)現(xiàn)。每當(dāng)該頁(yè)被訪(fǎng)問(wèn)時(shí)，訪(fǎng)問(wèn)計(jì)數(shù)器加1，而發(fā)生一次缺頁(yè)中斷時(shí)，則淘汰計(jì)數(shù)值最小的那一頁(yè)，并將所有的計(jì)數(shù)器清零。
• 最近最不經(jīng)常使用(NRU:not recently used)算法 NRU在需要淘汰某一頁(yè)時(shí)，從那些最近一個(gè)時(shí)期內(nèi)未被訪(fǎng)問(wèn)的頁(yè)中任選一頁(yè)淘汰。只要在頁(yè)表中增設(shè)一個(gè)訪(fǎng)問(wèn)位即可實(shí)現(xiàn)。當(dāng)某頁(yè)被訪(fǎng)問(wèn)時(shí)，訪(fǎng)問(wèn)位置1。否則，訪(fǎng)問(wèn)位置0。系統(tǒng)周期性地對(duì)所有引用位清零。當(dāng)需淘汰一頁(yè)時(shí)，從那些訪(fǎng)問(wèn)位為零的頁(yè)中選一頁(yè)進(jìn)行淘汰。如果引用位全0或全1，NRU算法退化為FIFO算法。

詳解可參照:操作系統(tǒng)內(nèi)存管理淘汰算法的實(shí)現(xiàn) 和 內(nèi)存管理的頁(yè)面置換算法有哪些

進(jìn)行數(shù)據(jù)庫(kù)設(shè)計(jì)時(shí)通常需要遵守哪些范式,請(qǐng)列舉并說(shuō)明?(10分)

設(shè)計(jì)關(guān)系數(shù)據(jù)庫(kù)時(shí)，遵從不同的規(guī)范要求，設(shè)計(jì)出合理的關(guān)系型數(shù)據(jù)庫(kù)，這些不同的規(guī)范要求被稱(chēng)為不同的范式，各種范式呈遞次規(guī)范，越高的范式數(shù)據(jù)庫(kù)冗余越小。

目前關(guān)系數(shù)據(jù)庫(kù)有六種范式：第一范式（1NF）、第二范式（2NF）、第三范式（3NF）、巴斯-科德范式（BCNF）、第四范式(4NF）和第五范式（5NF，還又稱(chēng)完美范式）。

• 第一范式 所有的域都應(yīng)該是原子性的，即數(shù)據(jù)庫(kù)表的每一列都是不可分割的原子數(shù)據(jù)項(xiàng)，而不能是集合，數(shù)組，記錄等非原子數(shù)據(jù)項(xiàng)。即實(shí)體中的某個(gè)屬性有多個(gè)值時(shí)，必須拆分為不同的屬性。在符合第一范式（1NF）表中的每個(gè)域值只能是實(shí)體的一個(gè)屬性或一個(gè)屬性的一部分。簡(jiǎn)而言之，第一范式就是無(wú)重復(fù)的域。
• 第二范式要求實(shí)體的屬性完全依賴(lài)于主關(guān)鍵字。所謂完全依賴(lài)是指不能存在僅依賴(lài)主關(guān)鍵字一部分的屬性，如果存在，那么這個(gè)屬性和主關(guān)鍵字的這一部分應(yīng)該分離出來(lái)形成一個(gè)新的實(shí)體，新實(shí)體與原實(shí)體之間是一對(duì)多的關(guān)系。為實(shí)現(xiàn)區(qū)分通常需要為表加上一個(gè)列，以存儲(chǔ)各個(gè)實(shí)例的唯一標(biāo)識(shí)。簡(jiǎn)而言之，第二范式就是在第一范式的基礎(chǔ)上屬性完全依賴(lài)于主鍵。
• 第三范式 在1NF基礎(chǔ)上，任何非主屬性不依賴(lài)于其它非主屬性[在2NF基礎(chǔ)上消除傳遞依賴(lài)]

詳細(xì)講解參見(jiàn)數(shù)據(jù)庫(kù)范式

算法與程序設(shè)計(jì)題(本題共45分)

尋找一個(gè)簡(jiǎn)單鏈表的中項(xiàng),如果存在兩個(gè)則返回前一個(gè).請(qǐng)給出算法描述并給出代碼(15分)

分析:可以借助于兩個(gè)指針，快慢指針，快指針一次走兩步，慢指針一次走一步，當(dāng)快指針走到尾端時(shí)，慢指針即指向中項(xiàng)位置。空間復(fù)雜度為0（1）時(shí)間復(fù)雜度為O(n).

struct ListNode {struct ListNode *next;int key; };ListNode* getMID(ListNode* head) {if (NULL == head)return NULL;ListNode *first = head;ListNode *second = head;while(NULL != second->next){if(NULL == second->next->next)break;first = first->next;second = second->next->next;}return first; }

拓展：借助快慢指針，可以判斷單向鏈表中是否有環(huán)，依據(jù)就是如果有環(huán)，快指針與慢指針總會(huì)相遇

在由N個(gè)正數(shù)的集合S中:找出最大元素C,滿(mǎn)足C=A+B,其中A,B都是集合S中元素.請(qǐng)給出算法描述、代碼與時(shí)間復(fù)雜度分析(15分)

算法步驟:

首先對(duì)集合進(jìn)行排序,從小到大排序,可以選擇排序算法較快的快速|(zhì)歸并|堆排序,n?log(n)復(fù)雜度

找最大滿(mǎn)足條件的元素C。兩層循環(huán)，外層循環(huán)從大到小依次尋找C。內(nèi)層循環(huán)，分別從頭尾向中間尋找元素A B,是的 C = A + B，找到后即跳出兩層循環(huán)。時(shí)間復(fù)雜度O(n2)。

程序復(fù)雜度為O(n2)

int FindSum(int A[],int n){sort(A,A+n);int left,right,sum;for(int i = n - 1;i >= 2;--i){left = 0,right = i - 1;while(left < right){sum = A[left] + A[right];if(sum == A[i]){return A[i];}else if(sum > A[i]){--right;}else{++left;}}}return -1; }

使用堆棧(Stack)來(lái)模擬隊(duì)列(FIFO)功能,要求數(shù)據(jù)必須存儲(chǔ)在堆棧內(nèi)部.需要實(shí)現(xiàn)enqueue(入棧),dequeue(出棧),isEmpty(判空)三個(gè)功能,并給出單元測(cè)試.(15分)

思路：兩個(gè)堆棧實(shí)現(xiàn)隊(duì)列
s1為入棧的，s2為出棧的
1. 入隊(duì)列：直接壓入s1即可
2. 出隊(duì)列：如果s2不為空，把s2中的棧頂元素直接彈出；否則，把s1的所有元素全部彈出壓入s2中，再?gòu)棾鰏2的棧頂元素.

stack<int> A; stack<int> B; //入隊(duì) void enqueue(int value[],int len) {for (int i = 0; i < len; i++){A.push(value[i]);}if (B.empty()){while(!A.empty()){B.push(A.top());A.pop();}} } 出隊(duì) void dequeue() {while(!B.empty()){B.pop();//其他操作} while(!A.empty()){B.push(A.top());A.pop();}while(!B.empty()){B.pop();//其他操作} } //判斷是否為空 bool isEmpty() {return (A.empty() && B.empty()); }

拓展：通過(guò)隊(duì)列實(shí)現(xiàn)棧

兩個(gè)隊(duì)列A與B，兩個(gè)隊(duì)列指針，指針qQueue指向一個(gè)非空隊(duì)列(當(dāng)然如果A、B都是空的話(huà)，指向其一），指針tmp始終指向另外一個(gè)空隊(duì)列
1. 入棧: 直接進(jìn)入qQueue指向的隊(duì)列；
2. 出棧: qQueue指向的隊(duì)列是否為空，非空時(shí)，將其指向的隊(duì)列數(shù)據(jù)移動(dòng)pop到tmp指向的隊(duì)列，獲取最后一個(gè)數(shù)據(jù)即可，交換qQueue與tmp。

詳細(xì)講解參見(jiàn)兩個(gè)棧實(shí)現(xiàn)隊(duì)列 兩個(gè)隊(duì)列實(shí)現(xiàn)棧

系統(tǒng)設(shè)計(jì)題(本題共25分)

手機(jī)推送服務(wù)設(shè)計(jì),在各個(gè)手機(jī)端應(yīng)用都有一定的云控制能力,可以再某些情況下云端發(fā)送各種數(shù)據(jù)或者命令道手機(jī)端,例如發(fā)送一個(gè)強(qiáng)制升級(jí)的命令或者手機(jī)app配置變換的數(shù)據(jù)包,以及發(fā)送一個(gè)信息給特定人群(某個(gè)地區(qū))
請(qǐng)?jiān)O(shè)計(jì)一個(gè)以長(zhǎng)鏈接為主的云端控制服務(wù),為了聚焦主要問(wèn)題,可以忽略掉低速手機(jī)網(wǎng)絡(luò)(例如:2g網(wǎng)絡(luò))手機(jī)終端等因素\用戶(hù)登錄的需求.服務(wù)需要承擔(dān)定向、定量的推送需求,在設(shè)計(jì)中要盡量高的吞吐能力和容錯(cuò)能力。
需要完成
a)基本的模塊視圖
b)鏈接管理主要設(shè)計(jì)思路。單臺(tái)機(jī)器承擔(dān)更多鏈接，但是鏈接多了后管理鏈接(鏈接中斷、鏈接查找)都會(huì)出現(xiàn)性能瓶頸，請(qǐng)嘗試給出思路。
c)嘗試給出提高容錯(cuò)能力(避免因?yàn)槟撑_(tái)物理機(jī)器或者某個(gè)機(jī)器上的程序掛掉導(dǎo)致整個(gè)系統(tǒng)不可用)的思路

后續(xù)分析…

參考：

• http://www.cnblogs.com/newpanderking/p/3972280.html
• 深入淺出TCP協(xié)議的2MSL TIME_WAIT狀態(tài)
• Linux中TCP連接過(guò)程簡(jiǎn)介

總結(jié)

以上是生活随笔為你收集整理的百度2015校园招聘软件开发笔试题及答案的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。