地點：杭州

　　職位：java研發(fā)

　　第一部分：計算機科學(xué)基礎(chǔ)

　　(注：所有職位必做)

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

　　A、基數(shù)排序 B、歸并排序、C、堆排序 D、快速排序

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

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

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

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

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

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

　　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的最終結(jié)果是多少?()

　　int t=125

　　t=t&27

　　t=t^31

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

　　6.(2分)歐幾里得的《幾何原本》描述了最解大公約數(shù)的算法，針對兩個整型a,b(a>b>0)其偽代碼如下，請估算該算法的復(fù)雜度()

　　god(a,b)

　　if b=0

　　then return god(b,a mod b)

　　A、O(lgb) B、O(a*b) C、O(a*a) D、O(b*b)

　　7.(2分)當(dāng)一個TCP連接被正常關(guān)閉時，主動關(guān)閉一方的狀態(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、數(shù)據(jù)鏈路層，會話層; B、數(shù)據(jù)鏈路層，應(yīng)用層;

　　C、網(wǎng)絡(luò)層，傳輸層; D、網(wǎng)絡(luò)層，表示層

　　9.(2分)通過磁盤冗余陣列(Redundant Arrays of Inexpensive Disks,RAID)能有效的提升數(shù)據(jù)存儲的可靠性或者訪問性能，請問以下哪些冗余策略能增加數(shù)據(jù)的可靠性?()

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

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

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

　　11.(2分)可以用來檢測多個數(shù)據(jù)位出錯的校驗碼有：()

　　A、奇偶校驗碼 B、CRC碼 C、BCD碼 5 D、海明碼

　　12.(2分)以下屬于對稱加密算法的有：()

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

　　13.(5分)使用偽代碼描述勇于字符串匹配的KMP算法：計算該算法最壞情況下的時間復(fù)雜度，并給出最壞情況的字符串樣式。

　　14.(5分)假設(shè)當(dāng)前系統(tǒng)底層提供了Compare&Set操作函數(shù)

　　聲明：bool CAS(type*ptr,type oldval,type newval)

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

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

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

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