2014-阿里巴巴算法工程師筆試真題

1、一、選擇題1.計算機一次內存、SSD 硬盤、SATA 硬盤的時間大概分別是多少？A、幾微秒，幾毫秒，幾十毫秒B、幾十納秒，幾十微秒，幾十毫秒C、幾十納秒，幾十微秒，幾十毫秒D、幾微秒，幾十微秒，幾十毫秒2.八進制的 256 用七進制表示是多少？A、356B、336C、338D、3463.若進程在內存中占 3 頁（開始時內存為空），若采用先進先出（LRU）頁面淘汰算法，當執(zhí)行如下頁號序列后 0，1，7，8，6, 2，3，7，2，9，8，1，0, 2會發(fā)生多少缺頁？A、8,32B、32,8C、32,6D、8,304.以下關于鏈式結構說法錯誤的是（）A、查找節(jié)點時鏈式比順序快B、每個節(jié)點是由數(shù)據(jù)域和

2、指針域組成C、比順序結構的密度小D、邏輯上不相鄰的節(jié)點物理上可能相鄰2014 校招阿里算法工程師（筆試）5.假定一個二維數(shù)組的定義語句為“a34=3,4,2,8,6;”，則元素 a12的值為（）A、6B、4C、2D、86.下面函數(shù)的功能是（）fun (char *s)char *p=s;while(*p+);return p-s-1;A、計算字符串的位(bit)數(shù)B、一個字符串C、求字符串的長度D、求字符串存放的位置7.判斷有向圖是否存在回路，利用（）方法最佳A、拓撲排序B、求最短路徑C、求關鍵路徑D、廣度優(yōu)先遍歷8.依次讀入數(shù)據(jù)元素序列a,b,c,d,e,f,g進棧，元素進?；虺鰲ｍ樞蚴俏粗?/p>

3、的，下列序列中，不可能成為?？諘r彈出的元素序列的有（）A、d,e,c,f,b,g,aB、c,d,b,e,f,a,gC、e,f,d,g,c,b,aD、f,e,g,d,a,c,b9.下列有關圖的遍歷說法中，不正確的是（）A、有向圖和無向圖都可以進行遍歷操作B、基本遍歷算法兩種：深度遍歷和廣度遍歷C、圖的遍歷必須用遞歸實現(xiàn)D、圖的遍歷算法可以執(zhí)行在有回路的圖中10.在 16 位機器上跑下列 foo 函數(shù)的結果是（）void foo()i = 65536;cout i ”,”;i = 65535;cout i;A、-1,65535B、0,-1C、-1,-1D、0,6553511.有一段年代久遠的C+代

4、碼，邏輯復雜，現(xiàn)在需要利用其實現(xiàn)一個新的需求，假定有以下可行的方案，應當優(yōu)先選擇（）A、修改老代碼的接口，滿足新的需求B、將老代碼拋棄，自己重新實現(xiàn)類似的邏輯C、修改老代碼的邏輯，滿足新的需求D、在這段代碼之外寫一段代碼，調用該代碼的一些模塊，完成新功能需求12.在 5 個頁框上使用 LRU 頁面替換算法，當頁框初始為空時，序列為0、1、7、8、6、2、3、7、2、9、8、1、0、2，系統(tǒng)將發(fā)生（）次缺頁A、13B、12C、11D、813.阿里巴巴有相距 1500km 的機房 A 和 B，現(xiàn)有 100GB 數(shù)據(jù)需要通過一條FTP 連接在 100s 的時間內從 A 傳輸?shù)?B。已知 FTP 連接

5、建立在 TCP 協(xié)議之上，而TCP 協(xié)議通過 ACK 來確認每個數(shù)據(jù)包是否正確傳送。網(wǎng)絡信號傳輸速度 2*108m/s，假設機房間帶寬足夠高，那么 A 節(jié)點的發(fā)送緩沖區(qū)可以設置為最?。ǎ〢、18MB、12MC、6MD、24M14.有三個結點的，可以多少個種叉樹？A、5B、13C、12D、1515.一副牌 52 張(去掉大小王)，從中抽取兩張牌，一紅一黑的概率是多少？A、25/51B、1/3C、1/2D、26/5116.設某文件經(jīng)內排序后得到 100 個初始歸并段（初始順串），若使用多路歸并排序算法，且要求三趟歸并完成排序，問歸并路數(shù)最少為（）A、8B、7C、6D、517.一個優(yōu)化的程序可以生成

6、一 n 個元素集合的所有子集，那么該程序的時間復雜度是（）A、O(n!)B、O(2n)C、O(n2)D、O(n log n)18.快速排序在已經(jīng)有序的情況下效率，復雜度為（）A、O(n log n)B、O(n2)C、O(n1.5)D、O(n2 log n)19.有一堆石子共 100 枚，甲乙輪流從該堆中取石子，每次可取 2、4 或 6 枚，若取得最后的石子的玩家為贏，若甲先取，則（）A、誰都無法取勝B、乙必勝C、甲必勝D、不確定20.現(xiàn)有一完全的 P2P 共享協(xié)議，每次兩個節(jié)點通訊后都能獲取對方已經(jīng)獲取的全部信息，現(xiàn)在使得系統(tǒng)中每個節(jié)點都知道所有節(jié)點的文件信息，共 17 個節(jié)點，假設只能通過多

7、次兩個對等節(jié)點之間通訊的方式，則最少需要（）次通訊A、32B、31C、30D、29二、解答題21.設計一個最優(yōu)算法，查找 n 個元素數(shù)組的最大值和最小值，要比較 2n 次；請寫一個最高效的算法，并說明他要比較的次數(shù)。請注意復雜度的常數(shù)(不用寫代碼，說驟和過程即可，要定出比較的次數(shù)，沒寫不給分)22.已知三個升序整數(shù)數(shù)組 al, bm和 cn。請在三個數(shù)組中各找一個元素，是的組成的三元組距離最元組的距離定義是：假設 ai、bj和 ck是一個三元組，那么距離為:Distance = max(|a I b j |, |a I c k |, |b j c k |)請設計一個求最元組距離的最優(yōu)算法，并分

8、析時間復雜度。23.請設計一個算法，在滿足質因數(shù)僅為 3,5,7 或其組合的數(shù)中，找出第 K 大的數(shù)。比如 K=1,2,3 時，分別應返回 3,5,7。要求算法時間復雜度最優(yōu)。24.在黑板上寫下 50 個數(shù)字：1 至 50。在接下來的 49作中，每次做如下動作：選取兩個黑板上的數(shù)字 a 和 b 檫去，在黑板上寫|b-a|。請問最后一次動作之后剩下數(shù)字可能是什么？為什么？（不用寫代碼，不寫原因不得分）三、14 解：5 種（部分題目）21 解：兩兩一對分組，如果數(shù)組元素個數(shù)為奇數(shù)，就最后單獨分一個，然后分別對每一組的兩個數(shù)比較，把小的放在左邊，大的放在右邊，這樣遍歷下來，總共比較的次數(shù)是 N/2

9、次；面分組的基礎上，那么可以得到結論，最小值一定在每一組的左邊部分找，最大值一定在數(shù)組的右邊部分找，最大值和最小值的查找分別需要比較N/2 次和 N/2 次；這樣就可以找到最大值和最小值了，比較的次數(shù)為：N/2 * 3 = (3N)/2 次代碼實現(xiàn)：#include #include #define N 7main()arrN = 4, 1, 5, 9, 9, 7, 10;iter = 0;cnt = 0;for(iter = 0; iter arriter + 1 )temp = arriter;arriter = arriter + 1;arriter + 1 = temp;myMin =

10、 arr0;for(iter = 2; iter N iter += 2)if(t & arriter myMin)myMin = arriter;myMax = arr1;for(iter = 3; iter myMax)myMax = arriter;if(N % 2 != 0 &t & myMax arrN - 1) myMax = arrN - 1;prf(min is %dn, myMin);prf(max is %dn, myMax);prf(compare times is %d, cnt);return 0;22 解：第一個關鍵點： max|x1-x2|,|y1-y2| =（|

11、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）根據(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|

12、 , |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|) /求出來了等價公式，完畢！第二個關鍵點：如何找到(|x1 x2| + |x1 x3| + |

13、x2 x3|) 的最小值，x1，x2，x3，分別是三個數(shù)組中的任意一個數(shù)，算法是：用三個指針分別指向 a,b,c 中最小的數(shù)，計算一次他們最大距離的 Distance ，然后在移動三個數(shù)中較小的數(shù)組指針，再計算一次，每次移動一個，直到其中一個數(shù)組結束為止，最慢(l+ m + n)次，復雜度為O(l+ m + n)代碼如下：#include #include #include #define l 3#define m 4#define n 6Mymin(a,b,c)Min = a b ? a : b;Min = Min c ? Min : c;return Min;Solving(a,b,c)/

14、解法，大家都會，不用過多介紹了！i = 0, j = 0, k = 0;MinSum = (abs(ai - bj) + abs(ai - ck) +abs(bj - ck) / 2;/store3 = 0;Sum = 0;for(i = 0; i l; i+)for(j = 0; j m; j+)for(k = 0; k Sum)MinSum = Sum;/store0 = i;/store1 = j;/store2 = k;/prf(the min is %dn, minABC);/prf(the three number is %-3d%-3d%-3dn, astore0,bstore1

15、, cstore2);return MinSum;MinDistance(a,b,c)MinSum = 0; /最小的絕對值和Sum = 0; /計算三個絕對值的和，與最小值做比較MinOFabc = 0; / ai , bj ,ck的最小值cnt = 0; /循環(huán)次數(shù)統(tǒng)計，最多是 l + m + n 次i = 0, j = 0, k = 0; /a,b,c 三個數(shù)組的下標索引MinSum = (abs(ai - bj) + abs(ai - ck) + abs(bj - ck) / 2;for(cnt = 0; cnt = l + m + n; cnt+)Sum = (abs(ai - bj) + abs(ai - ck) + abs(bj - ck) / 2;MinSum = MinSum = l) break;/ai最小,移動 iif(MinOFabc = bj)if(+j = m) break;/bj最小,移動 jif(MinOFabc = ck)if(+k = n) break;/ck最小,移動 kreturn MinSum;