地点：杭州

　　职位：java研发

　　第一部分：计算机科学基础

　　(注：所有职位必做)

　　1.(2分)最坏情况下时间复杂度为O(nlogn)的排序算法有()

　　A、基数排序 B、归并排序、C、堆排序 D、快速排序

　　2.(2分)以下说法正确的有()

　　A、有m阶B-树中，所有的非终端节点至少包含m/2个节点

　　B、若一个叶节点是某二叉树中的中序遍历的最后一个节点，同时它也是该二叉树前序遍历的最后一个节点

　　C、插入排序，堆排序，快速排序算法中，快速排序的速度是最快的，所需的附加空间也是最少的

　　D、n个数中已知有k个关键字hash值相同，若用线性探测法将它们存入散列表中，至少需要进行k(k+1)/2次探测

　　3.(2分)有一个长度为7的整形数组，里面存储了采用完全二叉树实现的最小堆。该数组中的所有元素都紧密存储，没有空隙，请问，该数组中可能的元素序列是：()

　　A、1 2 3 4 5 6 7

　　B、1 2 4 3 5 6 7

　　C、1 2 5 3 4 6 7

　　D、1 4 2 3 5 6 7

　　4.(2分)一个非连通无向图(无自回路和多重边)有66条边，那么它至少有()个顶点

　　A、11 B、12 C、13 D、14

　　5.(2分)请问变量t的最终结果是多少?()

　　int t=125

　　t=t&27

　　t=t^31

　　A、6 B、2015 C、7 D、26

　　6.(2分)欧几里得的《几何原本》描述了最解大公约数的算法，针对两个整型a,b(a>b>0)其伪代码如下，请估算该算法的复杂度()

　　god(a,b)

　　if b=0

　　then return god(b,a mod b)

　　A、O(lgb) B、O(ab) C、O(aa) D、O(bb)

　　7.(2分)当一个TCP连接被正常关闭时，主动关闭一方的状态变迁顺序正确的是：()

　　A、FIN_WAIT1->FIN_WAIT2->TIME_WAIT

　　B、SYNC_SENT->LAST_ACK->CLOSED

　　C、FIN_WAIT1->FIN_WAIT2->CLOSED

　　D、SYNC_SENT->LAST_ACK->TIME_WAIT

　　8.(2分)OSI七层模型中从低到高(即第一层为物理层)的第三层和第六层分别是：()

　　A、数据链路层，会话层; B、数据链路层，应用层;

　　C、网络层，传输层; D、网络层，表示层

　　9.(2分)通过磁盘冗余阵列(Redundant Arrays of Inexpensive Disks,RAID)能有效的提升数据存储的可靠性或者访问性能，请问以下哪些冗余策略能增加数据的可靠性?()

　　A、Raid B、Raid 1 C、Raid 5 D、Raid 6

　　10.(2分)在分布式系统的实现中，不问的进程之间常常需要交换信息，请问分别运行在两台不同主机的进程A，B，他们之间有哪些常见的策略可以进行通信?()

　　A、共享内存 B、Unix Domain Socket C、管道 D、tcp/ip 协议 E、UDP 协议

　　11.(2分)可以用来检测多个数据位出错的校验码有：()

　　A、奇偶校验码 B、CRC码 C、BCD码 5 D、海明码

　　12.(2分)以下属于对称加密算法的有：()

　　A、DES和DSA B、RSA和MD5 C、IDEA和RC4 D、SHA和EIGamal

　　13.(5分)使用伪代码描述勇于字符串匹配的KMP算法：计算该算法最坏情况下的时间复杂度，并给出最坏情况的字符串样式。

　　14.(5分)假设当前系统底层提供了Compare&Set操作函数

　　声明：bool CAS(typeptr,type oldval,type newval)

　　功能：当输入的oldval和ptr指针指向的当前值一致时，ptr指针指向的值将被设置为newval，并返回TRUE：否则返回FALSE.

　　特性：1.保证该函数执行的原子性

　　2.支持Safe-Memory-Reclamation特性。即，若发现ptr指向的内存和当前线程最后一次访问时发生过变化，则返回FALSE

　　请利用该CAS操作实现基于链表的无锁队列，队列长度无限。写出必要的数据结构，和入队/出队的伪代码。