地點(diǎn)：杭州
職位：java研發(fā)
第一部分：計(jì)算機(jī)科學(xué)基礎(chǔ)
(注：所有職位必做)
1.(2分)最壞情況下時(shí)間復(fù)雜度為O(nlogn)的排序算法有()
A、基數(shù)排序 B、歸并排序、C、堆排序 D、快速排序
2.(2分)以下說法正確的有()
A、有m階B-樹中，所有的非終端節(jié)點(diǎn)至少包含m/2個(gè)節(jié)點(diǎn)
B、若一個(gè)葉節(jié)點(diǎn)是某二叉樹中的中序遍歷的最后一個(gè)節(jié)點(diǎn)，同時(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í)現(xiàn)的最小堆。該數(shù)組中的所有元素都緊密存儲(chǔ)，沒有空隙，請(qǐng)問，該數(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è)非連通無向圖(無自回路和多重邊)有66條邊，那么它至少有()個(gè)頂點(diǎn)
A、11 B、12 C、13 D、14
5.(2分)請(qǐng)問變量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分)通過磁盤冗余陣列(Redundant Arrays of Inexpensive Disks,RAID)能有效的提升數(shù)據(jù)存儲(chǔ)的可靠性或者訪問性能，請(qǐng)問以下哪些冗余策略能增加數(shù)據(jù)的可靠性?()
A、Raid B、Raid 1 C、Raid 5 D、Raid 6
10.(2分)在分布式系統(tǒng)的實(shí)現(xiàn)中，不問的進(jìn)程之間常常需要交換信息，請(qǐng)問分別運(yùn)行在兩臺(tái)不同主機(jī)的進(jìn)程A，B，他們之間有哪些常見的策略可以進(jìn)行通信?()
A、共享內(nèi)存 B、Unix Domain Socket C、管道 D、tcp/ip 協(xié)議 E、UDP 協(xié)議
11.(2分)可以用來檢測(cè)多個(gè)數(shù)據(jù)位出錯(cuò)的校驗(yàn)碼有：()
A、奇偶校驗(yàn)碼 B、CRC碼 C、BCD碼 5 D、海明碼
12.(2分)以下屬于對(duì)稱加密算法的有：()
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)前線程最后一次訪問時(shí)發(fā)生過變化，則返回FALSE
請(qǐng)利用該CAS操作實(shí)現(xiàn)基于鏈表的無鎖隊(duì)列，隊(duì)列長(zhǎng)度無限。寫出必要的數(shù)據(jù)結(jié)構(gòu)，和入隊(duì)/出隊(duì)的偽代碼。
