(筆試時間120分鐘)
一、簡答題(本題共30分)
1.請描述資料結構中棧和佇列的差別，以及至少三種棧和佇列的基本操作介面?(10分)
2.在物件導向設計中，什麼是多型，說明一種C++中多型的實現方法，並編寫一個簡單的例子來說明多型?(10分)
3.請描述TCP協議中四次揮手的過程，以及TIM_WAIT狀態產生的原因和存在的理由?(10分)
二、演算法與程式設計題(本題共45)
1.使用C/C++語言寫一個函式，實現一篇文章中所有單詞逆置，即第一個單詞出現在文末，最後一個單詞出現在第一個的位置。要求不能用任何庫函式和系統呼叫，且空間複雜度最小，函式原型是：char*reverse_word(char*str)。(15分)
2.一個序列有n個數：A[1],A[2],...,A[n]，求出最長非降子序列的長度。
例如序列：5,3,4,8,6,7
輸出：4(最長非降子序列為3,4,6,7)(15分)
3.請設計一個有限狀態機，用於提取一個C語言檔案中的所有註釋。(15分)
三、系統設計題(本題共25分)
考慮設計一個基於社交網路的遊戲排名系統，需求如下：
1.使用者能夠看到其所有好友的'遊戲分數與排名(朋友圈內的所用人的排名)
2.使用者能看到自己在遊戲伺服器上的總排名(如第9527名)
問題如下：
1.請設計遊戲客戶端與伺服器分數和排名的互動、儲存的方式與結構，描述如何實現分數的實時更新，排名的高效查詢。
2.考慮如果線上使用者超過1億，請分析上述方案能否支援，如果支援請給出支援的理由;否則請給出改進的方案和技術。