简单题（本题共30分）请简述Tcp-ip的3次握手以及4次挥手过程？并解释为何关闭连接需要4次挥手(10分)
详细答案参见TCP/IP协议三次握手与四次握手流程解析 1. 三次握手过程：
Created with Raphal 2.1.2主动方主动方被动方被动方SYN=1,seq=JSYN=1,ACK=1,ack=J+1,seq=KACK=1,ack=K+1,seq=Z
2 . 四次挥手过程：
3 . 四次挥手的原因：
这是因为服务端的LISTEN状态下的SOCKET当收到SYN报文的建连请求后，它可以把ACK和SYN（ACK起应答作用，而SYN起同步作用）放在一个报文里来发送。但关闭连接时，当收到对方的FIN报文通知时，它仅仅表示对方没有数据发送给你了；但未必你所有的数据都全部发送给对方了，所以你可以未必会马上会关闭SOCKET,也即你可能还需要发送一些数据给对方之后，再发送FIN报文给对方来表示你同意现在可以关闭连接了，所以它这里的ACK报文和FIN报文多数情况下都是分开发送的。
4 . 不能两次握手连接的原因：
3次握手完成两个重要的功能，既要双方做好发送数据的准备工作(双方都知道彼此已准备好)，也要允许双方就初始序列号进行协商，这个序列号在握手过程中被发送和确认。
现在把三次握手改成仅需要两次握手，死锁是可能发生的。作为例子，考虑计算机S和C之间的通信，假定C给S发送一个连接请求分组，S收到了这个分组，并发送了确认应答分组。按照两次握手的协定，S认为连接已经成功地建立了，可以开始发送数据分组。可是，C在S的应答分组在传输中被丢失的情况下，将不知道S是否已准备好，不知道S建立什么样的序列号，C甚至怀疑S是否收到自己的连接请求分组。在这种情况下，C认为连接还未建立成功，将忽略S发来的任何数据分组，只等待连接确认应答分组。而S在发出的分组超时后，重复发送同样的分组。这样就形成了死锁。
操作系统的内存管理淘汰算法有哪些,请列出并简要说明？(10分)
进程运行时，若其访问的页面不在内存而需将其调入，但内存已无空闲空间时，就需要从内存中调出一页程序或数据，送入磁盘的兑换区。选择调出页面的算法就称为页面置换算法。好的页面置换算法应有较低的页面更换频率。
详解可参照:操作系统内存管理淘汰算法的实现 和 内存管理的页面置换算法有哪些
进行数据库设计时通常需要遵守哪些范式,请列举并说明?(10分)
设计关系数据库时，遵从不同的规范要求，设计出合理的关系型数据库，这些不同的规范要求被称为不同的范式，各种范式呈递次规范，越高的范式数据库冗余越小。
目前关系数据库有六种范式：第一范式（1NF）、第二范式（2NF）、第三范式（3NF）、巴斯-科德范式（BCNF）、第四范式(4NF）和第五范式（5NF，还又称完美范式）。
详细讲解参见数据库范式
算法与程序设计题(本题共45分)寻找一个简单链表的中项,如果存在两个则返回前一个.请给出算法描述并给出代码(15分)
分析:可以借助于两个指针，快慢指针，快指针一次走两步，慢指针一次走一步，当快指针走到尾端时，慢指针即指向中项位置。空间复杂度为0（1）时间复杂度为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;}
拓展：借助快慢指针，可以判断单向链表中是否有环，依据就是如果有环，，快指针与慢指针总会相遇
在由N个正数的集合S中:找出最大元素C,满足C=A+B,其中A,B都是集合S中元素.请给出算法描述、代码与时间复杂度分析(15分)
算法步骤:
首先对集合进行排序,从小到大排序,可以选择排序算法较快的快速|归并|堆排序,复杂度找最大满足条件的元素C。两层循环，外层循环从大到小依次寻找C。内层循环，分别从头尾向中间寻找元素A B,是的 C = A + B，找到后即跳出两层循环。时间复杂度。
程序复杂度为
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)来模拟队列(FIFO)功能,要求数据必须存储在堆栈内部.需要实现enqueue(入栈),dequeue(出栈),isEmpty(判空)三个功能,并给出单元测试.(15分)
思路：两个堆栈实现队列 s1为入栈的，s2为出栈的 1. 入队列：直接压入s1即可 2. 出队列：如果s2不为空，把s2中的栈顶元素直接弹出；否则，把s1的所有元素全部弹出压入s2中，再弹出s2的栈顶元素.
stack<int> A;stack<int> B;//入队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();}}}出队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());}
拓展：通过队列实现栈
没有什么可凭仗，只有他的好身体，没有地方可去，只想到处流浪。
