- 相關(guān)推薦
阿里巴巴集團校園招聘筆試題
第一部分 單選題(前10題，每題2分;后10題，每題3分。選對得滿分，選錯倒扣1分，不選得0分)
1、一次內(nèi)存訪問，SSD硬盤訪問和SATA硬盤隨機訪問的時間分別是()
A、幾微秒，幾毫秒，幾十毫秒 B、幾十納秒，幾十微秒，幾十毫秒
C、幾十納秒，幾十微秒，幾十毫秒 D、幾微秒，幾十微秒，幾十毫秒
2、8進制數(shù)256，轉(zhuǎn)化成7進制數(shù)是(B)
A、356 B、336 C、338 D、346
3、某網(wǎng)絡(luò)的IP地址空間為192.168.5.0/24，采用定長子網(wǎng)劃分，子網(wǎng)掩碼為255.255.255.248，則該網(wǎng)絡(luò)的最大子網(wǎng)個數(shù)、每個子網(wǎng)內(nèi)最大可分配地址個數(shù)各位(C)
A、8,32 B、32,8 C、32,6 D、8,30
4、以下關(guān)于鏈式存儲結(jié)構(gòu)說法錯誤的是(A)
A、查找節(jié)點時鏈式存儲比順序存儲快
B、每個節(jié)點是由數(shù)據(jù)域和指針域組成
C、比順序存儲結(jié)構(gòu)的存儲密度小
D、邏輯上不相鄰的節(jié)點物理上可能相鄰
5、假定一個二維數(shù)組的定義語句為“int a[3][4]={{3,4},{2,8,6}};”，則元素a[1][2]的值為(A)
A、6 B、4 C、2 D、8
6、下面函數(shù)的功能是(C)
int fun (char *s)
{
char *p=s;
while(*p++);
return p-s-1;
}
A、計算字符串的位(bit)數(shù) B、復(fù)制一個字符串
C、求字符串的長度 D、求字符串存放的位置
7、判斷有向圖是否存在回路，利用(A)方法最佳
A、拓撲排序 B、求最短路徑
C、求關(guān)鍵路徑 D、廣度優(yōu)先遍歷
8、依次讀入數(shù)據(jù)元素序列{a,b,c,d,e,f,g}進棧，元素進棧或出棧順序是未知的，下列序列中，不可能成為�？諘r彈出的元素構(gòu)成序列的有(D)
A、{d,e,c,f,b,g,a} B、{c,d,b,e,f,a,g} C、{e,f,d,g,c,b,a} D、{f,e,g,d,a,c,b}
9、下列有關(guān)圖的遍歷說法中，不正確的是(C)
A、有向圖和無向圖都可以進行遍歷操作
B、基本遍歷算法兩種：深度遍歷和廣度遍歷
C、圖的遍歷必須用遞歸實現(xiàn)
D、圖的遍歷算法可以執(zhí)行在有回路的圖中
10、在16位機器上跑下列foo函數(shù)的結(jié)果是(B)
void foo()
{
int i = 65536;
cout << i <<”,”;
i = 65535;
cout << i;
}
A、-1,65535 B、0,-1 C、-1,-1 D、0,65535
11、有一段年代久遠的C++代碼，內(nèi)部邏輯復(fù)雜，現(xiàn)在需要利用其實現(xiàn)一個新的需求，假定有以下可行的方案，應(yīng)當優(yōu)先選擇(D)
A、修改老代碼的接口，滿足新的需求
B、將老代碼拋棄，自己重新實現(xiàn)類似的邏輯
C、修改老代碼的內(nèi)部邏輯，滿足新的需求
D、在這段代碼之外寫一段代碼，調(diào)用該代碼的一些模塊，完成新功能需求
12、在5個頁框上使用LRU頁面替換算法，當頁框初始為空時，引用序列為0、1、7、8、6、2、3、7、2、9、8、1、0、2，系統(tǒng)將發(fā)生(C)次缺頁
A、13 B、12 C、11 D、8
分析：缺頁為：0、1、7、8、6、2、3、9、8、1、0，共11次
13、阿里巴巴有相距1500km的機房A和B，現(xiàn)有100GB數(shù)據(jù)需要通過一條FTP連接在100s的時間內(nèi)從A傳輸?shù)紹。已知FTP連接建立在TCP協(xié)議之上，而TCP協(xié)議通過ACK來確認每個數(shù)據(jù)包是否正確傳送。網(wǎng)絡(luò)信號傳輸速度2*108m/s，假設(shè)機房間帶寬足夠高，那么A節(jié)點的發(fā)送緩沖區(qū)可以設(shè)置為最小(A)
A、18M B、12M C、6M D、24M
分析：
TCP協(xié)議原理：TCP每發(fā)送一個報文段，就啟動一個定時器，如果在定時器超時之后還沒有收到ACK確認，就重傳該報文。
如圖所示，數(shù)據(jù)包由A的緩沖區(qū)發(fā)往B，B在收到數(shù)據(jù)包以后，回發(fā)一個ACK確認包給A，之后A將該數(shù)據(jù)包從緩沖區(qū)釋放。因此，該數(shù)據(jù)包會一直緩存在A的緩沖區(qū)，直到一個ACK確認為止。題目要求在100s內(nèi)發(fā)送100GB數(shù)據(jù)，網(wǎng)絡(luò)的傳輸速率至少是1G/s，某個數(shù)據(jù)包n在A中緩存的時間就是數(shù)據(jù)包n從A到B，再加上該數(shù)據(jù)包的ACK從B到A的時間：2*1500km/(2*108m/s)=1.5*10-2s，該段時間A中緩存的數(shù)據(jù)量至少是1G/s*1.5*10-2s約為15M
14、有3個節(jié)點的二叉樹可能有(A)種
A、5 B、13 C、12 D、15
15、設(shè)某文件經(jīng)內(nèi)排序后得到100個初始歸并段(初始順串)，若使用多路歸并排序算法，且要求三趟歸并完成排序，問歸并路數(shù)最少為(D)
A、8 B、7 C、6 D、5
分析：m個元素k路歸并的歸并趟數(shù)s=logk(m)，代入數(shù)據(jù)：logk(100)≦3
16、一個優(yōu)化的程序可以生成一n個元素集合的所有子集，那么該程序的時間復(fù)雜度是(B)
A、O(n!) B、O(2n) C、O(n2) D、O(n log n)
17、快速排序在已經(jīng)有序的情況下效率最差，復(fù)雜度為(B)
A、O(n log n) B、O(n2) C、O(n1.5) D、O(n2 log n)
18、從一副牌(52張，不含打小怪)里抽出兩張牌，其中一紅一黑的概率是(D)
A、25/51 B、1/3 C、1/2 D、26/51
分析：52張牌從中抽兩張，就是C522種情況，一紅一黑是C261 * C261種情況，概率P = C261 * C261 / C522 =26/51
19、有一堆石子共100枚，甲乙輪流從該堆中取石子，每次可取2、4或6枚，若取得最后的石子的玩家為贏，若甲先取，則(C)
A、誰都無法取勝 B、乙必勝 C、甲必勝 D、不確定
分析：先取的人只需要保證最后剩8枚就勝了。而要保證最后剩8枚，則必須要保證每一個回合內(nèi)取的數(shù)是一個可控的固定數(shù)，顯然這個數(shù)字是8，所以只需要保證第一次取完后，剩下的數(shù)字是8的倍數(shù)，就一定能勝。100除以8余數(shù)為4，故而，甲先取4枚，之后每一個回合所取數(shù)與上一個回合乙所取數(shù)之和為8，就能保證必勝。
20、現(xiàn)有一完全的P2P共享協(xié)議，每次兩個節(jié)點通訊后都能獲取對方已經(jīng)獲取的全部信息，現(xiàn)在使得系統(tǒng)中每個節(jié)點都知道所有節(jié)點的文件信息，共17個節(jié)點，假設(shè)只能通過多次兩個對等節(jié)點之間通訊的方式，則最少需要(C)次通訊
A、32 B、31 C、30 D、29
分析：如上圖1所示，假設(shè)有5個節(jié)點，按連線1、2、3、4通訊之后，節(jié)點4和5就掌握了所有節(jié)點的信息，之后，1、2、3節(jié)點只需跟4或5任一節(jié)點通訊一次即連線5、6、7就可保證每個節(jié)點都知道所有節(jié)點的信息，總的通訊次數(shù)是(n-1)+(n-2)=2n-3次。
如果將所有節(jié)點分成兩組，如圖2所示，兩組中的節(jié)點分別按連線1-8順序通訊之后，節(jié)點4和5就掌握了1-5所有節(jié)點的信息，節(jié)點9和0就掌握了6-0所有節(jié)點的信息，再按連線9、10通訊之后，節(jié)點4、5、9、0就掌握了1-0所有節(jié)點的信息，剩下的節(jié)點只需跟4、5、9、0任一節(jié)點通訊一次就可保證每個節(jié)點知道所有節(jié)點信息，和圖1相比，多了9和10兩次通訊，總的通訊次數(shù)是(2n1-3)+(2n2-3)+2=2n-4次(n1和n2分別表示分組中元素個數(shù))。
分3組的情況是(2n1-3)+(2n2-3)+(2n3-3)+6=2n-3次
分4組的情況是(2n1-3)+(2n2-3)+(2n3-3)+(2n4-3)+8=2n-4次
第二部分 不定項選擇(每題五分，每題有1-5個正確選項，完全正確計5分，漏選計2分不選計0分，多選、錯選計-2分)
21、2-3樹是一種特殊的樹，它滿足兩個條件：
(1)每個內(nèi)部節(jié)點有兩個或三個子節(jié)點;
(2)所有的葉節(jié)點到根的路徑長度相同;
如果一顆2-3樹有9個葉節(jié)點，下列數(shù)量個非葉節(jié)點的2-3樹可能存在的有(BE)
A、8 B、7 C、6 D、5 E、4
分析：根據(jù)條件(2)，葉節(jié)點只能在同一層，根據(jù)條件(1)，上一層的父節(jié)點只能是3個或4個，只能是如下圖所示的兩種結(jié)果
22、下列有關(guān)進程的說法中，錯誤的是(ABC)
A、進程與程序是一億對應(yīng)的 B、進程與作業(yè)時一一對應(yīng)的
C、進程是靜態(tài)的 D、進程是動態(tài)的過程
23、下列函數(shù)定義中，有語法錯誤的是(D)
A、void fun(int x, int *y){x *= *y;}
B、int * fun(int *x, int y){return x += y;}
C、void fun(int *x, int y){*x += y;}
D、void fun(int x, int *y){*x *= *y;}
24、有朋自遠方來，他乘火車，輪船，汽車，飛機來的概率分別是0.3,0.2,0.1,0.4，坐各交通工具遲到的概率分別是1/4,1/3,1/12,0，下列語句中正確的是(CD)
A、如果他準點，那么乘飛機的概率大于等于0.5
B、坐陸路(火車，汽車)交通工具準點機會比坐水路(輪船)要低
C、如果他遲到，乘火車的概率是0.5
D、如果他準點，坐輪船或汽車的概率等于坐火車的概率
第三部分 填空與問答
25、(4分)文件分配表FAT是管理磁盤空間的一種數(shù)據(jù)結(jié)構(gòu)，用在以鏈接方式存儲文件的系統(tǒng)中記錄磁盤分配和追蹤空白磁盤塊，整個磁盤僅設(shè)一張FAT表，其結(jié)構(gòu)如下所示，如果文件塊號為2，查找FAT序號為2的內(nèi)容得知物理塊2的后繼物理塊是5，再查FAT序號為5的內(nèi)容得知物理塊5的后繼物理塊是7，接著繼續(xù)查FAT序號為7的內(nèi)容為“Λ”，即該文件結(jié)束標志，
假設(shè)磁盤物理塊大小為1KB，并且FAT序號以4bits為單位向上擴充空間。請計算下列兩塊磁盤的FAT最少需要占用多大的存儲空間?
(1)一塊540MB的硬盤 (2)一塊1.2GB的硬盤
分析：(1)磁盤塊大小為1KB，540MB的硬盤可以分成540MB/1KB=5.4*105個磁盤塊，因此至少需要5.4*105<220個編號，需要20bit存儲空間
(2)同理，1.2G至少需要1.2*106<221個編號，為21bit，由于FAT序號以4bits為單位向上擴充，因此需要24bit存儲空間
26、(4分)已知如下代碼，并在兩個線程中同時執(zhí)行f1和f2，待兩個函數(shù)都返回后，a的所有可能值是哪些?
int a = 2, b = 0, c = 0;
void f1() void f2()
{ {
a = a * 2; c = a + 11;
a = b; a = c;
} }
分析：考慮四行代碼的執(zhí)行順序即可
(1)b=a*2,c=a+11,a=c,a=b a=4
(2)b=a*2,c=a+11,a=b,a=c a=13
(3)b=a*2,a=b,c=a+11,a=c a=15
(4)c=a+11,a=c,b=a*2,a=b a=26
27、(6分)設(shè)計一個最優(yōu)算法來查找一n個元素數(shù)組中的最大值和最小值，已知一種需要比較2n次的方法，請給一個更優(yōu)的算法。請?zhí)貏e注意優(yōu)化時間復(fù)雜度的常數(shù)。
給出該算法最壞情況下的比較次數(shù)和該算法的步驟描述。(不用寫代碼，不給出比較次數(shù)的不得分)
分析：已知的比較2n次的方法，顯然是將每個元素和最大值、最小值各比一次，要減少比較次數(shù)，可以有多種優(yōu)化方法：
方法一：一個元素先和最大值比較，如果比最大值大，就不用再和最小值比較(或者先和最小值比較，如果比最小值小，就不用再和最大值比較)，一般情況下，這種優(yōu)化后的比較次數(shù)一定會少于2n
方法二：將數(shù)組元素按兩個，兩個分組，組內(nèi)兩元素有序存放，之后最小值跟組內(nèi)較小的值比較，最大值只需跟組內(nèi)較大的值比較，這樣每組的比較次數(shù)是3，共n/2組，總的時間復(fù)雜度是3n/2次。
把數(shù)組兩兩一對分組，如果數(shù)組元素個數(shù)為奇數(shù)，就最后單獨分一個，然后分別對每一組的兩個數(shù)比較，把小的放在左邊，大的放在右邊，這樣遍歷下來，總共比較的次數(shù)是 N/2 次;在前面分組的基礎(chǔ)上，那么可以得到結(jié)論，最小值一定在每一組的左邊部分找，最大值一定在數(shù)組的右邊部分找，最大值和最小值的查找分別需要比較N/2 次和N/2 次;這樣就可以找到最大值和最小值了，比較的次數(shù)為
N/2 * 3 = (3N)/2 次
如圖會更加清晰：
28、(8分)已知三個升序整數(shù)數(shù)組a[l]、b[m]、c[n]，請在三個數(shù)組中各找一個元素，使得組成的三元組距離最小，三元組的距離定義是：假設(shè)a[i]、b[j]和c[k]是一個三元組，那么距離為distance=max(|a[i]-b[j]|,|a[i]-c[k]|,|b[j]-c[k]|)，請設(shè)計一求最小三元組距離的最優(yōu)算法，并分析時間復(fù)雜度。(不用寫代碼，不分析時間復(fù)雜度不得分)
解：這道題目有兩個關(guān)鍵點：
第一個關(guān)鍵點： max{|x1-x2|,|y1-y2|} =(|x1+y1-x2-y2|+|x1-y1-(x2-y2)|)/2 --公式(1)
我們假設(shè)x1=a[ i ]，x2=b[ j ]，x3=c[ k ]，則
Distance = max(|x1 – x2|, |x1 – x3|, |x2 – x3|) = max( max(|x1 – x2|, |x1 – x3|) , |x2 – x3|) --公式(2)
根據(jù)公式(1)，max(|x1 – x2|, |x1 – x3|) = 1/2 ( |2x1 – x2– x3| + |x2 – x3|)，帶入公式(2)，得到
Distance = max( 1/2 ( |2x1 – x2– x3| + |x2 – x3|) , |x2 – x3| )
=1/2 * max( |2x1 – x2– x3| , |x2 – x3| ) + 1/2*|x2 – x3| //把相同部分1/2*|x2 – x3|分離出來
=1/2 * max( |2x1 – (x2 + x3)| , |x2 – x3| ) + 1/2*|x2 – x3| //把(x2 + x3)看成一個整體，使用公式(1)
=1/2 * 1/2 *((|2x1 – 2x2| + |2x1 – 2x3|) + 1/2*|x2 – x3|
=1/2 *|x1 – x2| + 1/2 * |x1 – x3| + 1/2*|x2 – x3|
=1/2 *(|x1 – x2| + |x1 – x3| + |x2 – x3|) //求出來了等價公式，完畢!
第二個關(guān)鍵點：如何找到(|x1 – x2| + |x1 – x3| + |x2 – x3|) 的最小值，x1，x2，x3，分別是三個數(shù)組中的任意一個數(shù)，這一題，我只是做到了上面的推導(dǎo)，后面的算法設(shè)計是由csdn上的兩個朋友想出來的方法，他們的CSDN的ID分別為 “云夢澤” 和 “ shuyechengying”.
算法思想是：
用三個指針分別指向a,b,c中最小的數(shù)，計算一次他們最大距離的Distance ，然后在移動三個數(shù)中較小的數(shù)組指針，再計算一次，每次移動一個，直到其中一個數(shù)組結(jié)束為止，最慢(l+ m + n)次，復(fù)雜度為O(l+ m + n)
代碼如下：
#include
#include
#include
#define l 3
#define m 4
#define n 6
int Mymin(int a, int b, int c)
{
int Min = a < b ? a : b;
Min = Min < c ? Min : c;
return Min;
}
int Solvingviolence(int a[], int b[], int c[])
{
//暴力解法，大家都會，不用過多介紹了!
int i = 0, j = 0, k = 0;
int MinSum = (abs(a[i] - b[j]) + abs(a[i] - c[k]) + abs(b[j] - c[k])) / 2;
// int store[3] = {0};
int Sum = 0;
for(i = 0; i < l; i++)
{
for(j = 0; j < m; j++)
{
for(k = 0; k < n; k++)
{
Sum = (abs(a[i] - b[j]) + abs(a[i] - c[k]) + abs(b[j] - c[k])) / 2;
if(MinSum > Sum)
{
MinSum = Sum;
// store[0] = i;
// store[1] = j;
// store[2] = k;
}
}
}
}
// printf("the min is %d ", minABC);
// printf("the three number is %-3d%-3d%-3d ", a[store[0]], b[store[1]], c[store[2]]);
return MinSum;
}
int MinDistance(int a[], int b[], int c[])
{
int MinSum = 0; //最小的絕對值和
int Sum = 0; //計算三個絕對值的和，與最小值做比較
int MinOFabc = 0; // a[i] , b[j] ,c[k]的最小值
int cnt = 0; //循環(huán)次數(shù)統(tǒng)計，最多是l + m + n次
int i = 0, j = 0, k = 0; //a,b,c三個數(shù)組的下標索引
MinSum = (abs(a[i] - b[j]) + abs(a[i] - c[k]) + abs(b[j] - c[k])) / 2;
for(cnt = 0; cnt <= l + m + n; cnt++)
{
Sum = (abs(a[i] - b[j]) + abs(a[i] - c[k]) + abs(b[j] - c[k])) / 2;
MinSum = MinSum < Sum ? MinSum : Sum;
MinOFabc = Mymin(a[i] ,b[j] ,c[k]);//找到a[i] ,b[j] ,c[k]的最小值
//判斷哪個是最小值，做相應(yīng)的索引移動
if(MinOFabc == a[i])
{
if(++i >= l) break;
}//a[i]最小,移動i
if(MinOFabc == b[j])
{
if(++j >= m) break;
}//b[j]最小,移動j
if(MinOFabc == c[k])
{
if(++k >= n) break;
}//c[k]最小,移動k
}
return MinSum;
}
int main(void)
{
int a[l] = {5, 6, 7};
int b[m] = {13, 14, 15, 17};
int c[n] = {19, 22, 24, 29, 32, 42};
printf(" By violent solution ,the min is %d ", Solvingviolence(a, b, c));
printf(" By Optimal solution ,the min is %d ", MinDistance(a, b, c));
return 0;
}
29(8分)在黑板上寫下50個數(shù)字：1至50。在接下來的49輪的操作中，每次做如下動作：選取兩個黑板上的數(shù)字a和b檫去，在黑板上寫|b-a|。請問最后一次動作之后剩下數(shù)字可能是什么?為什么?(不用寫代碼，不寫原因不得分)
分析：50以內(nèi)的奇數(shù)都有可能
【算法工程師 附加題】請設(shè)計一個算法，在滿足質(zhì)因數(shù)僅為3,5,7或其組合的數(shù)中，找出第K大的數(shù)。比如K=1,2,3時，分別應(yīng)返回3,5,7。要求算法時間復(fù)雜度最優(yōu)。
分析：滿足質(zhì)因數(shù)僅為3,5,7或其組合的數(shù)，貌似可以表示成a(n)=3i*5j*7k，然后用基數(shù)排序，貌似方法不好使……
【阿里巴巴集團校園招聘筆試題】相關(guān)文章：
2015年阿里巴巴校園招聘筆試題08-04
阿里巴巴集團招聘產(chǎn)品經(jīng)理職位06-28
藥業(yè)集團校園招聘口號07-30
南方報業(yè)校園招聘筆試題07-09
2015迅雷校園招聘筆試題08-04
迅雷2014校園招聘筆試題07-19
2014保利校園招聘筆試題07-22
名企校園招聘筆試題08-24
58同城校園招聘筆試題07-26