地點(diǎn)：杭州

　　職位：java研發(fā)

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

　　(注：所有職位必做)

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

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

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

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

　　B、若一個(gè)葉節(jié)點(diǎn)是某二叉樹(shù)中的中序遍歷的最后一個(gè)節(jié)點(diǎn)，同時(shí)它也是該二叉樹(shù)前序遍歷的最后一個(gè)節(jié)點(diǎn)

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

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

　　3.(2分)有一個(gè)長(zhǎng)度為7的整形數(shù)組，里面存儲(chǔ)了采用完全二叉樹(shù)實(shí)現(xiàn)的最小堆。該數(shù)組中的所有元素都緊密存儲(chǔ)，沒(méi)有空隙，請(qǐng)問(wèn)，該數(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分)一個(gè)非連通無(wú)向圖(無(wú)自回路和多重邊)有66條邊，那么它至少有()個(gè)頂點(diǎn)

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

　　5.(2分)請(qǐng)問(wèn)變量t的最終結(jié)果是多少?()

　　int t=125

　　t=t&27

　　t=t^31

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

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

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

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

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

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

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

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

　　11.(2分)可以用來(lái)檢測(cè)多個(gè)數(shù)據(jù)位出錯(cuò)的校驗(yàn)碼有：()

　　A、奇偶校驗(yàn)碼 B、CRC碼 C、BCD碼 5 D、海明碼

　　12.(2分)以下屬于對(duì)稱(chēng)加密算法的有：()

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

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

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

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

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

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

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

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