阿里巴巴集團校園招聘筆試題

　　第一部分 單選題(前10題，每題2分;后10題，每題3分。選對得滿(mǎn)分，選錯倒扣1分，不選得0分)

　　1、一次內存訪(fǎng)問(wèn)，SSD硬盤(pán)訪(fǎng)問(wèn)和SATA硬盤(pán)隨機訪(fǎng)問(wèn)的時(shí)間分別是()

　　A、幾微秒，幾毫秒，幾十毫秒 B、幾十納秒，幾十微秒，幾十毫秒

　　C、幾十納秒，幾十微秒，幾十毫秒 D、幾微秒，幾十微秒，幾十毫秒

　　2、8進(jìn)制數256，轉化成7進(jìn)制數是(B)

　　A、356 B、336 C、338 D、346

　　3、某網(wǎng)絡(luò )的IP地址空間為192.168.5.0/24，采用定長(cháng)子網(wǎng)劃分，子網(wǎng)掩碼為255.255.255.248，則該網(wǎng)絡(luò )的最大子網(wǎng)個(gè)數、每個(gè)子網(wǎng)內最大可分配地址個(gè)數各位(C)

　　A、8,32 B、32,8 C、32,6 D、8,30

　　4、以下關(guān)于鏈式存儲結構說(shuō)法錯誤的是(A)

　　A、查找節點(diǎn)時(shí)鏈式存儲比順序存儲快

　　B、每個(gè)節點(diǎn)是由數據域和指針域組成

　　C、比順序存儲結構的存儲密度小

　　D、邏輯上不相鄰的節點(diǎn)物理上可能相鄰

　　5、假定一個(gè)二維數組的定義語(yǔ)句為“int a[3][4]={{3,4},{2,8,6}};”，則元素a[1][2]的值為(A)

　　A、6 B、4 C、2 D、8

　　6、下面函數的功能是(C)

　　int fun (char *s)

　　{

　　char *p=s;

　　while(*p++);

　　return p-s-1;

　　}

　　A、計算字符串的位(bit)數 B、復制一個(gè)字符串

　　C、求字符串的長(cháng)度 D、求字符串存放的位置

　　7、判斷有向圖是否存在回路，利用(A)方法最佳

　　A、拓撲排序 B、求最短路徑

　　C、求關(guān)鍵路徑 D、廣度優(yōu)先遍歷

　　8、依次讀入數據元素序列{a,b,c,d,e,f,g}進(jìn)棧，元素進(jìn)�；虺鰲ｍ樞蚴俏粗�的，下列序列中，不可能成為�？諘r(shí)彈出的元素構成序列的有(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)圖的遍歷說(shuō)法中，不正確的是(C)

　　A、有向圖和無(wú)向圖都可以進(jìn)行遍歷操作

　　B、基本遍歷算法兩種：深度遍歷和廣度遍歷

　　C、圖的遍歷必須用遞歸實(shí)現

　　D、圖的遍歷算法可以執行在有回路的圖中

　　10、在16位機器上跑下列foo函數的結果是(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++代碼，內部邏輯復雜，現在需要利用其實(shí)現一個(gè)新的需求，假定有以下可行的方案，應當優(yōu)先選擇(D)

　　A、修改老代碼的接口，滿(mǎn)足新的需求

　　B、將老代碼拋棄，自己重新實(shí)現類(lèi)似的邏輯

　　C、修改老代碼的內部邏輯，滿(mǎn)足新的需求

　　D、在這段代碼之外寫(xiě)一段代碼，調用該代碼的一些模塊，完成新功能需求

　　12、在5個(gè)頁(yè)框上使用LRU頁(yè)面替換算法，當頁(yè)框初始為空時(shí)，引用序列為0、1、7、8、6、2、3、7、2、9、8、1、0、2，系統將發(fā)生(C)次缺頁(yè)

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

　　分析：缺頁(yè)為：0、1、7、8、6、2、3、9、8、1、0，共11次

　　13、阿里巴巴有相距1500km的機房A和B，現有100GB數據需要通過(guò)一條FTP連接在100s的時(shí)間內從A傳輸到B。已知FTP連接建立在TCP協(xié)議之上，而TCP協(xié)議通過(guò)ACK來(lái)確認每個(gè)數據包是否正確傳送。網(wǎng)絡(luò )信號傳輸速度2*108m/s，假設機房間帶寬足夠高，那么A節點(diǎn)的發(fā)送緩沖區可以設置為最小(A)

　　A、18M B、12M C、6M D、24M

　　分析：

　　TCP協(xié)議原理：TCP每發(fā)送一個(gè)報文段，就啟動(dòng)一個(gè)定時(shí)器，如果在定時(shí)器超時(shí)之后還沒(méi)有收到ACK確認，就重傳該報文。

　　如圖所示，數據包由A的緩沖區發(fā)往B，B在收到數據包以后，回發(fā)一個(gè)ACK確認包給A，之后A將該數據包從緩沖區釋放。因此，該數據包會(huì )一直緩存在A(yíng)的緩沖區，直到一個(gè)ACK確認為止。題目要求在100s內發(fā)送100GB數據，網(wǎng)絡(luò )的傳輸速率至少是1G/s，某個(gè)數據包n在A(yíng)中緩存的時(shí)間就是數據包n從A到B，再加上該數據包的ACK從B到A的時(shí)間：2*1500km/(2*108m/s)=1.5*10-2s，該段時(shí)間A中緩存的數據量至少是1G/s*1.5*10-2s約為15M

　　14、有3個(gè)節點(diǎn)的二叉樹(shù)可能有(A)種

　　A、5 B、13 C、12 D、15

　　15、設某文件經(jīng)內排序后得到100個(gè)初始歸并段(初始順串)，若使用多路歸并排序算法，且要求三趟歸并完成排序，問(wèn)歸并路數最少為(D)

　　A、8 B、7 C、6 D、5

　　分析：m個(gè)元素k路歸并的歸并趟數s=logk(m)，代入數據：logk(100)≦3

　　16、一個(gè)優(yōu)化的程序可以生成一n個(gè)元素集合的所有子集，那么該程序的時(shí)間復雜度是(B)

　　A、O(n!) B、O(2n) C、O(n2) D、O(n log n)

　　17、快速排序在已經(jīng)有序的情況下效率最差，復雜度為(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枚，若取得最后的石子的玩家為贏(yíng)，若甲先取，則(C)

　　A、誰(shuí)都無(wú)法取勝 B、乙必勝 C、甲必勝 D、不確定

　　分析：先取的人只需要保證最后剩8枚就勝了。而要保證最后剩8枚，則必須要保證每一個(gè)回合內取的數是一個(gè)可控的固定數，顯然這個(gè)數字是8，所以只需要保證第一次取完后，剩下的數字是8的倍數，就一定能勝。100除以8余數為4，故而，甲先取4枚，之后每一個(gè)回合所取數與上一個(gè)回合乙所取數之和為8，就能保證必勝。

　　20、現有一完全的P2P共享協(xié)議，每次兩個(gè)節點(diǎn)通訊后都能獲取對方已經(jīng)獲取的全部信息，現在使得系統中每個(gè)節點(diǎn)都知道所有節點(diǎn)的文件信息，共17個(gè)節點(diǎn)，假設只能通過(guò)多次兩個(gè)對等節點(diǎn)之間通訊的方式，則最少需要(C)次通訊

　　A、32 B、31 C、30 D、29

　　分析：如上圖1所示，假設有5個(gè)節點(diǎn)，按連線(xiàn)1、2、3、4通訊之后，節點(diǎn)4和5就掌握了所有節點(diǎn)的信息，之后，1、2、3節點(diǎn)只需跟4或5任一節點(diǎn)通訊一次即連線(xiàn)5、6、7就可保證每個(gè)節點(diǎn)都知道所有節點(diǎn)的信息，總的通訊次數是(n-1)+(n-2)=2n-3次。

　　如果將所有節點(diǎn)分成兩組，如圖2所示，兩組中的節點(diǎn)分別按連線(xiàn)1-8順序通訊之后，節點(diǎn)4和5就掌握了1-5所有節點(diǎn)的信息，節點(diǎn)9和0就掌握了6-0所有節點(diǎn)的信息，再按連線(xiàn)9、10通訊之后，節點(diǎn)4、5、9、0就掌握了1-0所有節點(diǎn)的信息，剩下的節點(diǎn)只需跟4、5、9、0任一節點(diǎn)通訊一次就可保證每個(gè)節點(diǎn)知道所有節點(diǎn)信息，和圖1相比，多了9和10兩次通訊，總的通訊次數是(2n1-3)+(2n2-3)+2=2n-4次(n1和n2分別表示分組中元素個(gè)數)。

　　分3組的情況是(2n1-3)+(2n2-3)+(2n3-3)+6=2n-3次

　　分4組的情況是(2n1-3)+(2n2-3)+(2n3-3)+(2n4-3)+8=2n-4次

　　第二部分 不定項選擇(每題五分，每題有1-5個(gè)正確選項，完全正確計5分，漏選計2分不選計0分，多選、錯選計-2分)

　　21、2-3樹(shù)是一種特殊的樹(shù)，它滿(mǎn)足兩個(gè)條件：

　　(1)每個(gè)內部節點(diǎn)有兩個(gè)或三個(gè)子節點(diǎn);

　　(2)所有的葉節點(diǎn)到根的路徑長(cháng)度相同;

　　如果一顆2-3樹(shù)有9個(gè)葉節點(diǎn)，下列數量個(gè)非葉節點(diǎn)的2-3樹(shù)可能存在的有(BE)

　　A、8 B、7 C、6 D、5 E、4

　　分析：根據條件(2)，葉節點(diǎn)只能在同一層，根據條件(1)，上一層的父節點(diǎn)只能是3個(gè)或4個(gè)，只能是如下圖所示的兩種結果

　　22、下列有關(guān)進(jìn)程的說(shuō)法中，錯誤的是(ABC)

　　A、進(jìn)程與程序是一億對應的 B、進(jìn)程與作業(yè)時(shí)一一對應的

　　C、進(jìn)程是靜態(tài)的 D、進(jìn)程是動(dòng)態(tài)的過(guò)程

　　23、下列函數定義中，有語(yǔ)法錯誤的是(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、有朋自遠方來(lái)，他乘火車(chē)，輪船，汽車(chē)，飛機來(lái)的概率分別是0.3,0.2,0.1,0.4，坐各交通工具遲到的概率分別是1/4,1/3,1/12,0，下列語(yǔ)句中正確的是(CD)

　　A、如果他準點(diǎn)，那么乘飛機的概率大于等于0.5

　　B、坐陸路(火車(chē)，汽車(chē))交通工具準點(diǎn)機會(huì )比坐水路(輪船)要低

　　C、如果他遲到，乘火車(chē)的概率是0.5

　　D、如果他準點(diǎn)，坐輪船或汽車(chē)的概率等于坐火車(chē)的概率

　　第三部分 填空與問(wèn)答

　　25、(4分)文件分配表FAT是管理磁盤(pán)空間的一種數據結構，用在以鏈接方式存儲文件的系統中記錄磁盤(pán)分配和追蹤空白磁盤(pán)塊，整個(gè)磁盤(pán)僅設一張FAT表，其結構如下所示，如果文件塊號為2，查找FAT序號為2的內容得知物理塊2的后繼物理塊是5，再查FAT序號為5的內容得知物理塊5的后繼物理塊是7，接著(zhù)繼續查FAT序號為7的內容為“Λ”，即該文件結束標志，

　　假設磁盤(pán)物理塊大小為1KB，并且FAT序號以4bits為單位向上擴充空間。請計算下列兩塊磁盤(pán)的FAT最少需要占用多大的存儲空間?

　　(1)一塊540MB的硬盤(pán) (2)一塊1.2GB的硬盤(pán)

　　分析：(1)磁盤(pán)塊大小為1KB，540MB的硬盤(pán)可以分成540MB/1KB=5.4*105個(gè)磁盤(pán)塊，因此至少需要5.4*105<220個(gè)編號，需要20bit存儲空間

　　(2)同理，1.2G至少需要1.2*106<221個(gè)編號，為21bit，由于FAT序號以4bits為單位向上擴充，因此需要24bit存儲空間

　　26、(4分)已知如下代碼，并在兩個(gè)線(xiàn)程中同時(shí)執行f1和f2，待兩個(gè)函數都返回后，a的所有可能值是哪些?

　　int a = 2, b = 0, c = 0;

　　void f1() void f2()

　　{ {

　　a = a * 2; c = a + 11;

　　a = b; a = c;

　　} }

　　分析：考慮四行代碼的執行順序即可

　　(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分)設計一個(gè)最優(yōu)算法來(lái)查找一n個(gè)元素數組中的最大值和最小值，已知一種需要比較2n次的方法，請給一個(gè)更優(yōu)的算法。請特別注意優(yōu)化時(shí)間復雜度的常數。

　　給出該算法最壞情況下的比較次數和該算法的步驟描述。(不用寫(xiě)代碼，不給出比較次數的不得分)

　　分析：已知的比較2n次的方法，顯然是將每個(gè)元素和最大值、最小值各比一次，要減少比較次數，可以有多種優(yōu)化方法：

　　方法一：一個(gè)元素先和最大值比較，如果比最大值大，就不用再和最小值比較(或者先和最小值比較，如果比最小值小，就不用再和最大值比較)，一般情況下，這種優(yōu)化后的比較次數一定會(huì )少于2n

　　方法二：將數組元素按兩個(gè)，兩個(gè)分組，組內兩元素有序存放，之后最小值跟組內較小的值比較，最大值只需跟組內較大的值比較，這樣每組的比較次數是3，共n/2組，總的時(shí)間復雜度是3n/2次。

　　把數組兩兩一對分組，如果數組元素個(gè)數為奇數，就最后單獨分一個(gè)，然后分別對每一組的兩個(gè)數比較，把小的放在左邊，大的放在右邊，這樣遍歷下來(lái)，總共比較的次數是 N/2 次;在前面分組的基礎上，那么可以得到結論，最小值一定在每一組的左邊部分找，最大值一定在數組的右邊部分找，最大值和最小值的查找分別需要比較N/2 次和N/2 次;這樣就可以找到最大值和最小值了，比較的次數為

　　N/2 * 3 = (3N)/2 次

　　如圖會(huì )更加清晰：

　　28、(8分)已知三個(gè)升序整數數組a[l]、b[m]、c[n]，請在三個(gè)數組中各找一個(gè)元素，使得組成的三元組距離最小，三元組的距離定義是：假設a[i]、b[j]和c[k]是一個(gè)三元組，那么距離為distance=max(|a[i]-b[j]|,|a[i]-c[k]|,|b[j]-c[k]|)，請設計一求最小三元組距離的最優(yōu)算法，并分析時(shí)間復雜度。(不用寫(xiě)代碼，不分析時(shí)間復雜度不得分)

　　解：這道題目有兩個(gè)關(guān)鍵點(diǎn)：

　　第一個(gè)關(guān)鍵點(diǎn)： max{|x1-x2|,|y1-y2|} =(|x1+y1-x2-y2|+|x1-y1-(x2-y2)|)/2 --公式(1)

　　我們假設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)

　　根據公式(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|分離出來(lái)

　　=1/2 * max( |2x1 – (x2 + x3)| , |x2 – x3| ) + 1/2*|x2 – x3| //把(x2 + x3)看成一個(gè)整體，使用公式(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|) //求出來(lái)了等價(jià)公式，完畢!

　　第二個(gè)關(guān)鍵點(diǎn)：如何找到(|x1 – x2| + |x1 – x3| + |x2 – x3|) 的最小值，x1，x2，x3，分別是三個(gè)數組中的任意一個(gè)數，這一題，我只是做到了上面的推導，后面的算法設計是由csdn上的兩個(gè)朋友想出來(lái)的方法，他們的CSDN的ID分別為 “云夢(mèng)澤” 和 “ shuyechengying”.

　　算法思想是：

　　用三個(gè)指針?lè )謩e指向a,b,c中最小的數，計算一次他們最大距離的Distance ，然后在移動(dòng)三個(gè)數中較小的數組指針，再計算一次，每次移動(dòng)一個(gè)，直到其中一個(gè)數組結束為止，最慢(l+ m + n)次，復雜度為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[])

　　{

　　//暴力解法，大家都會(huì )，不用過(guò)多介紹了!

　　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; //計算三個(gè)絕對值的和，與最小值做比較

　　int MinOFabc = 0; // a[i] , b[j] ,c[k]的最小值

　　int cnt = 0; //循環(huán)次數統計，最多是l + m + n次

　　int i = 0, j = 0, k = 0; //a,b,c三個(gè)數組的下標索引

　　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]的最小值

　　//判斷哪個(gè)是最小值，做相應的索引移動(dòng)

　　if(MinOFabc == a[i])

　　{

　　if(++i >= l) break;

　　}//a[i]最小,移動(dòng)i

　　if(MinOFabc == b[j])

　　{

　　if(++j >= m) break;

　　}//b[j]最小,移動(dòng)j

　　if(MinOFabc == c[k])

　　{

　　if(++k >= n) break;

　　}//c[k]最小,移動(dòng)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分)在黑板上寫(xiě)下50個(gè)數字：1至50。在接下來(lái)的49輪的操作中，每次做如下動(dòng)作：選取兩個(gè)黑板上的數字a和b檫去，在黑板上寫(xiě)|b-a|。請問(wèn)最后一次動(dòng)作之后剩下數字可能是什么?為什么?(不用寫(xiě)代碼，不寫(xiě)原因不得分)

　　分析：50以?xún)鹊钠鏀刀加锌赡?/p>

　　【算法工程師 附加題】請設計一個(gè)算法，在滿(mǎn)足質(zhì)因數僅為3,5,7或其組合的數中，找出第K大的數。比如K=1,2,3時(shí)，分別應返回3,5,7。要求算法時(shí)間復雜度最優(yōu)。

　　分析：滿(mǎn)足質(zhì)因數僅為3,5,7或其組合的數，貌似可以表示成a(n)=3i*5j*7k，然后用基數排序，貌似方法不好使……

【阿里巴巴集團校園招聘筆試題】相關(guān)文章：

2015年阿里巴巴校園招聘筆試題08-04

阿里巴巴集團招聘產(chǎn)品經(jīng)理職位06-28

阿里巴巴非技術(shù)類(lèi)筆經(jīng)及試題08-13

藥業(yè)集團校園招聘口號07-30

南方報業(yè)校園招聘筆試題07-09

2015迅雷校園招聘筆試題08-04

迅雷2014校園招聘筆試題07-19

2014保利校園招聘筆試題07-22

名企校園招聘筆試題08-24

58同城校園招聘筆試題07-26