2021年阿里巴巴程序員面試題

第1題：

一、單選題

-7的二進制補碼表示為：

????

A 01111000

B 01111001

C 11111000

D 11111001

答案：D

正數的補碼是自身，負數的補碼是原碼的高位不變，數值位取反加1

那么-7是負數，原碼：1000 0111，反碼：1111 1000，補碼：1111 1001

第2題：

?以下四種介質中，帶寬最大的是________。

???

A? 同軸電纜(coaxial)

B? 雙絞線(twisted pair)

C? 光纖(twisted pair)

D? 同步線(synchronous)

?答案：C

解析：雙絞線也稱為雙扭線，是最古老但又最常用的傳輸媒體。把兩根互相絕緣的銅導線并排放在一起，然后用規則的方法絞合起來（這樣做是為了減少相鄰的導線的電磁干擾）而構成雙絞線。雙絞線分為1類到5類，局域網中常用的為3類，4類和5類雙絞線。 3類線用于語音傳輸及最高傳輸速率為 10Mbps的數據傳輸；4類線用于語音傳輸和最高傳輸速率為 16Mbps的數據傳輸；5類線用于語音傳輸和最高傳輸速率為 100Mbps的數據傳輸

同軸電纜由內導體銅質芯線，絕緣層，網狀編制的外導體屏蔽層及保護塑料外層組成 ,內導體和外導體構成一組線對。由于外導體屏蔽層的作用，同軸電纜具有很好的抗干擾性。同軸電纜可以將 10Mb/S的基帶數字信號傳送1千米到 1.2千米，因此被廣泛用于局域網中

光纖通信就是利用光導纖維傳遞光脈沖來進行通信，而光導纖維是光纖通信的媒體。光纖在任何時間都只能單向傳輸，因此，要實行雙向通信，它必須成對出現，一個用于輸入，一個用于輸出，光纖兩端接到光學接口上。光纖的傳輸系統比同軸電纜大的多，一般小同軸電纜的最大傳輸帶寬為 20MHz左右，中同軸電纜的最大傳輸帶寬為 60MHz左右。單根光導纖維的數據傳輸速率能達幾Gbps，在不使用中繼器的情況下，傳輸距離能達幾十公里。

答案：C

第3題：

?進程阻塞的原因不包括________。

??

A? 時間片切換

B? 等待I/O

C? 進程sleep

D? 等待解鎖

答案：A

解析：進程有3個狀態：就緒態。執行態、阻塞態。三種狀態的轉換包含有：

就緒->執行，執行->就緒，執行->阻塞，阻塞->就緒

等待I/O、進程sleep、等待解鎖等原因都會導致進程暫停。關于"時間片切換"，當進程已經獲得了除cpu外所有的資源，這時的狀態就是就緒態，當分配到了時間片就成了執行態，當時間片用完之前一直未進入阻塞態的話，此后便繼續進入就緒態。所以進程的就緒與阻塞是完全不同的。

答案：A

第4題：

?設只含根節點的二叉樹高度為1，現有一顆高度為h(h>1)的二叉樹上只有出度為0和出度為2的結點，則此二叉樹中所包含的結點數至少為________個。

????

A? 2^h-1

B? 2h-1

C? 2h

D? 2h+1

答案：B

解析：保證樹的高度就只有最左邊的左子樹有節點能保證最少，畫出來后發現答案是B

答案：B

第5題：

?給定下列程序，那么執行printf("%d\n", foo(20, 13));的輸出結果是________。

int foo(int x, int y){

????if (x <= 0 || y <= 0)

????????return 1;

????return 3 * foo( x-6, y/2 );

}

????

A? 3

B? 9

C? 27

D? 81

答案：?D

分析：

3*6 < 20 < 4*6,遞歸 4層。

log13 < log16 = 4;

所以結果為 3^4 = 81.

第6題：

?對于以下說法，錯誤的是________。

?

A? Dijkstra算法用于求解圖中兩點間最短路徑，其時間復雜度O(n^2)

B? Floyd-Warshall算法用于求解圖中所有點對之間最短路徑，其時間復雜度為O(n^3)

C? 找出n個數字的中位數至少需要O(n*logn)的時間

D? 基于比較的排序問題的時間復雜度下界是O(n*logn)

答案：C

解析：AB正確，考察基本算法。D正確，基于比較的話，怎么樣都至少需要O(n*logn)的時間。找一個數是否是中位數，可以利用快排的過程（而不是快排），就和O(N)第K數一樣。

答案：C

第7題：

?一個包里有5個黑球，10個紅球和17個白球。每次可以從中取兩個球出來，放置在外面。那么至少取________次以后，一定出現過取出一對顏色一樣的球。?

A? 16

B? 9

C? 4

D? 1

答案：A

題目要求是一定出現，是必然情況，本題可以認為是鴿巢問題。

考慮最壞情況

黑球用B表示

紅球用R表示

白球用W表示

前面15次取球情況

（B,W）（B,W） ? （B,W） ? （B,W） ? （B,W）

（R,W）（R,W） ? （R,W） ? （R,W） ? （R,W） ? （R,W） ? （R,W） ? （R,W） ? （R,W） ? （R,W）

最后只剩下兩個白球了（W,W）

所以至少16次，才一定出現。

第8題：

?某地電信局要對業務號碼進行梳理，需要檢測開通的市話號碼是否存在某一個是另一個的前綴的情況，以簡化電話交換機的邏輯。例如：某用戶號碼是“11001100”，但與"110"報警電話產生前綴配對。已知市話號碼最長8位，最短3位，并且所有3位的電話號碼都以1開頭。由于市話號碼眾多，長度也未必一直，高效的算法可以用O(n)的時間復雜度完成檢測（n為開通市話號碼個數，數量是千萬級的）。那么，該算法最壞情況下需要耗費大約________內存空間。

?????

A? 5GB

B? 500MB

C? 50MB

D? 5MB

答案：?C

解析：千萬級，也就是10,000,000。市話最長8位，也就是一個字節的空間，那么全部存下這些號碼所耗費的空間為：1B*1000*1000*10 ?= 10MB（不必糾結1000還是1024，只要代表了千萬級的數量就行了）。所以是兩位數的級別。

答案：C

第9題：

?騎士只說真話，騙子只說假話。下列場景中能確定一個騎士、一個騙子的有________。

??????????

A? 甲說：“我們中至少有一個人說真話”，乙什么也沒說。

B? 甲說："我們兩個都是騙子"，乙什么也沒說。

C? 甲說：“我是個騙子或者乙是個騎士”，乙什么也沒說。

D? 甲和乙都說：“我是個騎士”。

E? 甲說：“乙是個騎士”，乙說：“我們倆一個是騎士一個是騙子”。

答案：?B

如果甲是騎士，那么騎士說真話，就不會是騙子，而他說他們兩個都是騙子，那么甲必然是騙子，說的是假話，所以二個人中至少有一個是騎士，那么就只有乙是騎士了。

第10題：

?給定一個m行n列的整數矩陣（如圖），每行從左到右和每列從上到下都是有序的。判斷一個整數k是否在矩陣中出現的最優算法，在最壞情況下的時間復雜度是________。

? 1?? 5?? 7?? 9

?4?? 6??10 15

?8? 11?12 19

14 16 18 21

????

A? O(m*n)

B? O(m+n)

C? O(log(m*n))

D? O(log(m+n))

?答案：B ?

楊氏矩陣查找算法

?????

????

1. ????????bool?stepWise(int?mat[][N_MAX],?int?N,?int?target,??

   ?????

   ?

   ?????

   ??????????????????????int?&row,?int?&col)?{??

   ?????

   ?

   ????

2. ??????????if?(target??mat[N-1][N-1])?return?false;??

   ?????

   ?

   ?????

   ??????????row?=?0;??

   ?????

   ?

   ????

3. ??????????col?=?N-1;??

   ?????

   ?

   ?????

   ??????????while?(row?<=?N-1?&&?col?>=?0)?{??

   ?????

   ?

   ????

4. ????????????if?(mat[row][col]?

   ?????

   ?

   ?????

   ??????????????row++;??

   ?????

   ?

   ????

5. ????????????else?if?(mat[row][col]?>?target)??

   ?????

   ?

   ?????

   ??????????????col--;??

   ?????

   ?

   ????

6. ????????????else??

   ?????

   ?

   ?????

   ??????????????return?true;??

   ?????

   ?

   ????

7. ??????????}??

   ?????

   ?

   ?????

   ??????????return?false;??

   ?????

   ?

   ????

8. ????????} ?

   ?????

   ?

   ?

第11題：

?二、不定項選擇

某服務請求經負載均衡設備分配到集群A、B、C、D進行處理響應的概率分別是10%、20%、30%和40%。已知測試集群所得的穩定性指標分別是90%、95%、99%和99.9%?，F在該服務器請求處理失敗，且已排除穩定性以外的問題，那么最有可能在處理該服務請求的集群是________。

??????

A、A

B、B

C、C

D、D

?

答案：?A B

解析：選中該集群，并且處理失敗了的概率為：10%*10%、20%*5%、30%*1%、40%*0.1%。A與B的概率最高。

答案：A、B

?

第12題：

?甲乙兩人撿到一個價值10元的購物卡。協商后打算通過這樣的拍賣規則來確定歸屬：兩人單獨出價（可以出0元），出價高者得到購物卡同時將與出價相同數量的前給對方。如果兩人出價相同，則通過擲硬幣來決定購物卡的歸屬。例如：甲和乙都出價1元，他們通過擲硬幣來決定購物卡的歸屬。此時，得到購物卡的人賺9元，另一人賺1元。兩人都同意用手頭的現金來進行出價。甲和乙都知道甲有6元、乙有8元，兩人都期望自己盡可能多賺。那么________。

??????????

A? 乙最終賺的比甲多

B??甲最終賺的比乙多

C? 甲乙兩人中可能有一人會有損失

D? 甲乙兩人賺的一樣多

?答案：D

首先甲乙都不會出5塊錢以上的，因為那樣自己會虧。但出5塊錢以下，比如4塊，對方可以出5塊，這樣自己就輸了，所以也不會出5塊錢以下的。 最后博弈后雙贏的結果就是一方出五塊，一方出0塊，然后各得5塊

第13題：

?以下________狀態為TCP連接關閉過程中的出現的狀態。

?

A? LISTEN

B? TIME-WAIT

C? LAST-ACK

D? SYN-RECEIVED

?答案：B C

主要部分，四次握手： ? ? ? ? ? ? ? ? ? ? ? ? ? ?

斷開連接其實從我的角度看不區分客戶端和服務器端，任何一方都可以調用close(or closesocket)之類的函數開始主動終止一個連接。這里先暫時說正常情況。當調用close函數斷開一個連接時，主動斷開的一方發送FIN(finish報文給對方。有了之前的經驗，我想你應該明白我說的FIN報文時什么東西。也就是一個設置了FIN標志位的報文段。FIN報文也可能附加用戶數據，如果這一方還有數據要發送時，將數據附加到這個FIN報文時完全正常的。之后你會看到，這種附加報文還會有很多，例如ACK報文。我們所要把握的原則是，TCP肯定會力所能及地達到最大效率，所以你能夠想到的優化方法，我想TCP都會想到。 ? ? ? ? ? ? ? ?? ? ? ? ? ? ? 當被動關閉的一方收到FIN報文時，它會發送ACK確認報文(對于ACK這個東西你應該很熟悉了)。這有個 ? ? ? ? ? ? ? 東西要注意，因為TCP是雙工的，也就是說，你可以想象一對TCP連接上有兩條數據通路。當發送FIN報文 ? ? ? ? ? ? ? 時，意思是說，發送FIN的一端就不能發送數據，也就是關閉了其中一條數據通路。被動關閉的一端發送 ? ? ? ? ? ? ? 了ACK后，應用層通常就會檢測到這個連接即將斷開，然后被動斷開的應用層調用close關閉連接。

第14題：

?如果在一個排序算法的執行過程中，沒有一對元素被比較過兩次或以上，則稱該排序算法為節儉排序算法，以下算法中是節儉排序算法的有________。

?

A? 插入排序

B? 選擇排序

C? 堆排序

D? 歸并排序

?答案：AD

【解析】

A每個未排序的元素只會與 已經有序的元素進行至多一次比較

D每個有序列表內的元素不進行比較；列表之間的元素比較一次之后就進入了同一個列表

第15題：

?三、填空題

請補全下面的快速排序代碼，答案中請不要包含空格。

void qsort(int *array, int len)
{
? ? int value, start, end;
? ? if (len <= 1)?
? ? ? ? return;?
? ? value = array[0];?
? ? start = 0;?
? ? end = len - 1;?
? ? while (start < end) {?
? ? ? ? for (; start < end; --end) {?
? ? ? ? ? ? if (array[end] < value) {?
?????????????????? ?_______???????????????????????????????
???????????????? break;?
? ? ? ? ? ? }?
? ? ? ? }?
? ? ? ? for (; start < end; ++start) {?
? ? ? ? ? ? if (array[start] > value)
? ? ? ? ? ? {
????????????? ???_________???????????????????????????????
???????????????? break;
? ? ? ? ? ? }
? ? ? ? }
? ? }
?? ???____________?? ????????
???? qsort(array,? ?_________? );
? ? qsort(?_________?,?___________?);
}

?

?array[start++]=array[end];

array[end--]=array[start];

array[start]=value;

start

array+start+1

len-start-1

第16題：

?四、解答題

某公司有這么一個規定：只要有一個員工過生日，當天所有員工全部放假一天。但在其余時候，所有員工都沒有假期，必須正常上班。假設一年有365天，每個員工的生日都概率均等地分布在這365天里。那么，這個公司需要雇用多少員工，才能讓公司一年內所有員工的總工作時間期望值最大？

?你的第一感覺或許是，公司應該雇用 100 多人，或者 200 多人吧。答案或許會讓你大吃一驚：公司應該雇用 365 個人。注意，雇用 365 個人并不意味著全體員工全年的總工作時間為 0 ，因為 365 個人的生日都是隨機的，恰好每天都有一個人過生日的概率極小極小。下面我們就來證明，這個問題的最優解就是 365 人。

由于期望值滿足線性關系（即對于隨機變量 X 和 Y 有 E(X) + E(Y) = E(X+Y) ），因此我們只需要讓每一天員工總工作時間的期望值最大就可以了。假設公司里有 n 個人，那么在特定的一天里，沒有人過生日的概率是 (364/365)n 。因此，這一天的期望總工作時間就是 n · (364/365)n 個工作日。為了考察函數 n · (364/365)n 的增減性，我們來看一下 ((n+1) · (364/365)n+1) / (n · (364/365)n) 的值，它等于 (364 · (n+1)) / (365 · n) 。如果分子比分母小，解得 n > 364 ?？梢?，要到 n = 365 以后，函數才是遞減的。

答案：365

第17題：

?給定一個排好升序的數組A[1]、A[2]、……、A[n]，其元素的值都兩兩不相等。請設計一高效的算法找出中間所有A[i] = i的下標。并分析其復雜度。（不分析復雜度不得分）

?解析：首先分析一下這個數組，假設其中某個位置的A[i] = i，那么可以肯定的值，之前的A[x] > x，之后的A[x] < x。還有一個顯而易見的性質就是中間的A[i]=i一定是連續存在的，不可能跨區域存在，因為這個數組是升序的。

我給出的方法是二分查找，具體的做法是：我們假設一個新數組B，其元素是A[i] - i的值，這樣的話，B[i] = 0的時候A[i] = i，而且把B數組劃分成了三個部分，左邊的小于零的區域，中間的等于零的區域，右邊的大于零的區域。

我第一次的想法是：二分搜索這個想象中的新數組，找到值為零的下標，但是這個下標不一定是最左邊的滿足條件的下標，所以我們還需要寫一個while來往左移動這個下標，直到找到最左邊的符合條件的下標，如下代碼（假設已經通過二分查找找到了符合條件的一個下標idx）：

while(A[idx-1] == (idx-1))

?????idx--;

這樣的話其時間復雜度就是O(logn) + O(n)，還是屬于On)的范疇。

后來我想到，為什么只去隨機命中一個目標下標呢！如果二分查找這個數據的邊界的話，就能直接得到最左邊符合條件的下標了！其實二分查找不僅僅適用于對一個元素的搜索，也可以用于兩個、三個特定相對位置元素的搜索。每次查找的時候，假設當前位置是mid，那么只要判斷當前A[mid] - mid是否小于零，以及后一個元素A[mid+1] - (mid+1) == 0就行了。

#include? ?

using namespace std;?

???

int BinarySearch(int cc[], int len)?

{?

???int l = 0, r = len, mid;?

???while (l <= r)?

???{?

??????mid = l + ((r-l) >> 1);?

??????if(mid == 0 && cc[mid] == mid)?? // 若數組一開始就符合條件?

?????????return 0;?

??????// 若滿足條件的下標不是從0開始，則邊界是前一個<0，且后一個=0?

??????if (cc[mid]-mid < 0 && cc[mid+1]-(mid+1) == 0)?

?????????return mid+1;?

??????// 二分查找邊界：前一個<0，且后一個=0?

??????if (cc[mid] - mid >= 0)?

?????????r = mid-1;?

??????else?

?????????l = mid+1;?

???}?

???return -1;?

}?

???

int main()?

{?

???// int cc[] = {0, 1};?

???// int cc[] = {0, 1, 2, 3, 4, 5, 6, 7};?

???// int cc[] = {-9, -8, -4, -2, 4, 5, 9};?

???// int cc[] = {-5, -4, -3, 5, 6, 7};?

???int len = sizeof(cc)/sizeof(int);?

???int idx = BinarySearch(cc, len);?

???if(idx != -1)?

???{?

??????while(cc[idx] == idx)?

??????{?

?????????printf("%d ", idx);?

?????????idx++;?

??????}?

???}?

???else?

???{?

??????printf("Not found\n");?

???}?

???

???getchar();?

???return 0;?

}?

?

OK! 由于程序是原生的二分查找，所以時間復雜度為O(logn)，沒有占用額外的空間。并且不需要區分正整數還是負整數，數據類型也可以改成double沒問題。

第18題：

?某怪物被海水沖上一個孤島。醒來時他發現自己處于險境。周圍有N條鱷魚都虎視眈眈的盯著他。每條鱷魚看上去都餓得足以把他吞下去。不過，事情也未必真的那么糟糕。鱷魚吞下他是要花費體力的。這些鱷魚現在的體力都相當，由于獵食需要花費體力，所以吞下怪物的鱷魚會由于體力下降而可能被周圍的某條鱷魚吞了。類似的，吞鱷魚的這條鱷魚也可能被其他鱷魚吞了。因此，雖然有食物可獵，但他們自己并不想成為其他鱷魚的獵食對象。正所謂，螳螂捕蟬，黃雀在后。所以鱷魚們在確保自己生命安全的情況下才會發動進攻。那么，怪物到底安全么？為什么？

?如果只有一條鱷魚，怪物顯然是危險的；

兩條鱷魚的時候，先下手的鱷魚會成為另外一條鱷魚的食物，所以怪物顯然很安全；

三條鱷魚的時候，把先下手的鱷魚當做怪物，就會回到兩條鱷魚的狀態，此時先下手的鱷魚非常安全，也就是說怪物顯然很危險；

四條鱷魚的時候，先下手的鱷魚會面臨三條鱷魚的狀態，此時也就沒有鱷魚準備先下手，所以怪物很安全；

我們很容易發現，吞吃過怪物的鱷魚會成為下一個怪物，成為N-1條鱷魚的獵物，也就是說，如果N-1的時候安全，則N的時候危險；

綜上所述，奇數條鱷魚怪物不安全，偶數條鱷魚怪物安全。

第19題：

?當你在瀏覽器輸入一個網址，如http://www.taobao.com，按回車之后發生了什么？請從技術的角度描述，如瀏覽器、網絡（UDP、TCP、HTTP等），以及服務器等各種參與對象上由此引發的一系列活動，請盡可能的涉及到所有的關鍵技術點。

?首先是查找瀏覽器緩存，瀏覽器會保存一段時間你之前訪問過的一些網址的DNS信息，不同瀏覽器保存的時常不等。

如果沒有找到對應的記錄，這個時候瀏覽器會嘗試調用系統緩存來繼續查找這個網址的對應DNS信息。

如果還是沒找到對應的IP，那么接著會發送一個請求到路由器上，然后路由器在自己的路由器緩存上查找記錄，路由器一般也存有DNS信息。

如果還是沒有，這個請求就會被發送到ISP（注：Internet Service ? ?Provider，互聯網服務提供商，就是那些拉網線到你家里的運營商，中國電信中國移動什么的），ISP也會有相應的ISP ?DNS服務器，一聽中國電信就知道這個DNS服務器的規?？隙ú粫?，所以基本上都能在這里找得到。題外話：會跑到這里進行查詢是因為你沒有改動過"網絡中心"的"ipv4"的DNS地址，萬惡的電信聯通可以改動了這個DNS服務器，換句話說他們可以讓你的瀏覽器跳轉到他們設定的頁面上，這也就是人盡皆知的DNS和HTTP劫持，ISP們還美名曰“免費推送服務”。強烈鄙視這種霸王行為。我們也可以自行修改DNS服務器來防止DNS被ISP污染。

如果還是沒有的話， 你的ISP的DNS服務器會將請求發向根域名服務器進行搜索。根域名服務器就是面向全球的頂級DNS服務器，共有13臺邏輯上的服務器，從A到M命名，真正的實體服務器則有幾百臺，分布于全球各大洲。所以這些服務器有真正完整的DNS數據庫。如果到了這里還是找不到域名的對應信息，那只能說明一個問題：這個域名本來就不存在，它沒有在網上正式注冊過?；蛘哔u域名的把它回收掉了（通常是因為欠費）。

這也就是為什么打開一個新頁面會有點慢，因為本地沒什么緩存，要這樣遞歸地查詢下去。

多說一句，例如"mp3.baidu.com"，域名先是解析出這是個.com的域名，然后跑到管理.com域名的服務器上進行進一步查詢，然后是.baidu，最后是mp3，

所以域名結構為：三級域名.二級域名.一級域名。

瀏覽器終于得到了IP以后，瀏覽器接著給這個IP的服務器發送了一個http請求，方式為get，例如訪問nbut.cn

這個get請求包含了主機（host）、用戶代理(User-Agent)，用戶代理就是自己的瀏覽器，它是你的"代理人"，Connection（連接屬性）中的keep-alive表示瀏覽器告訴對方服務器在傳輸完現在請求的內容后不要斷開連接，不斷開的話下次繼續連接速度就很快了。其他的顧名思義就行了。還有一個重點是Cookies，Cookies保存了用戶的登陸信息，在每次向服務器發送請求的時候會重復發送給服務器。Corome上的F12與Firefox上的firebug(快捷鍵shift+F5)均可查看這些信息。

發送完請求接下來就是等待回應了，

當然了，服務器收到瀏覽器的請求以后（其實是WEB服務器接收到了這個請求，WEB服務器有iis、apache等），它會解析這個請求（讀請求頭），然后生成一個響應頭和具體響應內容。接著服務器會傳回來一個響應頭和一個響應，響應頭告訴了瀏覽器一些必要的信息，例如重要的Status ?Code，2開頭如200表示一切正常，3開頭表示重定向，4開頭，如404，呵呵。響應就是具體的頁面編碼，就是那個......，瀏覽器先讀了關于這個響應的說明書（響應頭），然后開始解析這個響應并在頁面上顯示出來。在下一次CF的時候（不是穿越火線，是http://codeforces.com/），由于經常難以承受幾千人的同時訪問，所以CF頁面經常會出現崩潰頁面，到時候可以點開火狐的firebug或是Chrome的F12看看狀態，不過這時候一般都急著看題和提交代碼，似乎根本就沒心情理會這個狀態吧-.-。

如果是個靜態頁面，那么基本上到這一步就沒了，但是如今的網站幾乎沒有靜態的了吧，基本全是動態的。所以這時候事情還沒完，根據我們的經驗，瀏覽器打開一個網址的時候會慢慢加載這個頁面，一部分一部分的顯示，直到完全顯示，最后標簽欄上的圈圈就不轉了。

這是因為，主頁（index）頁面框架傳送過來以后，瀏覽器還要繼續向服務器發送請求，請求的內容是主頁里面包含的一些資源，如圖片，視頻，css樣式等等。這些"非靜態"的東西要一點點地請求過來，所以標簽欄轉啊轉，內容刷啊刷，最后全部請求并加載好了就終于好了。需要說明的是，對于靜態的頁面內容，瀏覽器通常會進行緩存，而對于動態的內容，瀏覽器通常不會進行緩存。緩存的內容通常也不會保存很久，因為難保網站不會被改動。