地點：杭州

職位：java研發(fā)

第一部分：計算機科學基礎

(注：所有職位必做)

1.(2分)最壞情況下時間復雜度為O(nlogn)的排序算法有()

A、基數排序 B、歸并排序、C、堆排序 D、快速排序

2.(2分)以下說法正確的有()

A、有m階B-樹中，所有的非終端節(jié)點至少包含m/2個節(jié)點

B、若一個葉節(jié)點是某二叉樹中的中序遍歷的最后一個節(jié)點，同時它也是該二叉樹前序遍歷的最后一個節(jié)點

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

D、n個數中已知有k個關鍵字hash值相同，若用線性探測法將它們存入散列表中，至少需要進行k(k+1)/2次探測

3.(2分)有一個長度為7的整形數組，里面存儲了采用完全二叉樹實現(xiàn)的最小堆。該數組中的所有元素都緊密存儲，沒有空隙，請問，該數組中可能的元素序列是：()

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連接被正常關閉時，主動關閉一方的狀態(tài)變遷順序正確的是：()

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分)在分布式系統(tǒng)的實現(xiàn)中，不問的進程之間常常需要交換信息，請問分別運行在兩臺不同主機的進程A，B，他們之間有哪些常見的策略可以進行通信?()

A、共享內存 B、Unix Domain Socket C、管道 D、tcp/ip 協(xié)議 E、UDP 協(xié)議

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分)假設當前系統(tǒng)底層提供了Compare&Set操作函數

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

功能：當輸入的oldval和ptr指針指向的當前值一致時，ptr指針指向的值將被設置為newval，并返回TRUE：否則返回FALSE.

特性：1.保證該函數執(zhí)行的原子性

2.支持Safe-Memory-Reclamation特性。即，若發(fā)現(xiàn)ptr指向的內存和當前線程最后一次訪問時發(fā)生過變化，則返回FALSE

請利用該CAS操作實現(xiàn)基于鏈表的無鎖隊列，隊列長度無限。寫出必要的數據結構，和入隊/出隊的偽代碼。