(笔试时间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亿，请分析上述方案能否支持，如果支持请给出支持的理由;否则请给出改进的方案和技术。