阿里巴巴招聘研發工程師筆試題和面試題答案(二)

　　11.在一臺主流配置的PC機上，調用f(35)所用的時間大概是 。

　　A. 幾毫秒 B. 幾秒 C.幾分鐘 D.幾小時

　　12.在一棵度為4的樹T中，有20個度為4的節點，10個度為3的節點，1個度為2的節點，10個度為1的節點，則樹T的葉子個數為 。

　　A.41 B. 82 C. 113 D.122

　　13.有堆棧S，按順序ABCD進棧，則出棧順序不可能存在的是 。

　　A. DCBA B. BACD C. BADC D. CABD

　　14. 使用二分查找在有序數組a[n]中查找一個元素x的時間復雜度 。

　　A. O(n) B. O(n2) C. O(log n) D. O(n logn)

　　15. 圖中標出了每條有向公路最大流量，請問從S到T最大流量是 。

　　A.46 B. 47 C. 54 D.77

　　16. 一天，有為年輕人來到張老板的店里花80元買了件原價為160元的紀念品。這件禮物的成本是65元。結賬時，年輕人掏出一張100元，張老板當時沒有零錢，就用那100元向隔壁店家換了零錢，找給年輕人20元。但是隔壁店家后來發現那100元是假鈔，張老板無奈還了100元。那么，張老板在這次交易中實際損失了 元錢。

　　A. 65 B. 85 C. 100 D.185

　　17. 2^100 mod 7 = 。

　　A. 2 B. 3 C. 4 D.5

　　18. 某公司在華東和華南兩大區域開展業務，年底匯總業績的時候發現，兩大區域的月度客戶轉化率(=成為會員的客戶數/訪問店鋪的客戶數)分別提高了10%和5%，以下描述中正確的是 。

　　A.盡管各自的月度轉化率都有提高，但公司的整體月度轉化率仍有可能降低

　　B.市場對業務認可度提高，越來越多訪問店鋪的客戶成為會員

　　C.華東區的客戶更容易被轉化，該公司應該把業務重點放在這個區域

　　D.華南區的客戶更需要提高轉化，該公司應該把業務重點放在這個區域

　　19. 一次有8個人參加的網球比賽，根據選手的實力，分別編號為1至8，1號最強，8號最弱，而實力差距小于等于2才有可能出現爆冷。8人進行1/4決賽，勝出的4人繼續半決賽，直到冠軍產生，問有可能獲得冠軍的編號最大的選手是 。

　　A. 4 B. 6 C. 7 D. 8

　　20. 某國家非常重男輕女，若一戶人家生了一個女孩，便再要一個，直到生下男孩為止，假設生男生女概率相等，請問平均每戶人家有 個女孩。

　　A. 0.5 B. 2/3 C. 1 D. 4/3

　　二、不定向選擇(4題，每題5分，每題有1-5個正確選項，完全正確計5分，漏選記2分，不選記0分，多選、錯選記-2分)

　　21. 以下有關C語言的說法中，錯誤的是 。

　　A.內存泄露一般是只程序申請了一塊內存，使用完后，沒有及時將這塊內存釋放，從而導致程序占用大量內存。

　　B.無法通過malloc(size_t)函數調用申請超過該機器物理內存大小的內存塊。

　　C. 無法通過內存釋放函數free(void )直接將某塊已經使用完的物理內存直接歸還給操作系統

　　D. 可以通過內存分配函數malloc(size_t)直接申請物理內存。

　　22.下面關于二叉搜索樹正確的說法包括 。

　　A.待刪除節點有左子樹和右子樹，只能使用左子樹的最大值節點替換待刪除節點

　　B. 給定一棵二叉搜索樹的前序和后序遍歷結果，無法確定這棵二叉搜索樹

　　C. 給定一棵二叉搜索樹，根據節點值大小排序所需時間復雜度是線性的

　　D. 給定一棵二叉搜索樹，可以在線性時間復雜度內轉化為平衡二叉搜索樹

　　23. 被稱為中國與人的周瑋，僅僅使用1分鐘的時間就可以對16位數字開14次方。那么以下數字中， 不可能稱為其候選答案。

　　A. 11.0 B. 12.0 C. 13.0 D. 14.0 E. 15.0

　　24. 有3個包，每個包里各放了兩個球。包A里的球都是白球，包B里的球都是黑球，包C里的球一黑一白。現隨機取一個包，并從中隨機取一個球，發現該球是白色的，那么這個包里剩下的球也是白色的概率是 。

　　A. 0 B. 0.33 C. 0.5 D. 0.66 E. 1

　　三、填空與問答(5題，共30分)

　　25. (4分)某電子眼鏡的分辨率為640×360;相當于在距離2.5米左右觀看一個25英寸大小的屏幕，其長寬比為16:9。已知藍牙4.0技術工作在2.4GHz頻帶，理論最大帶寬為24Mbps，請問該眼鏡是否可以通過該技術將每秒50幀真彩(24bits，每8個bit用于傳輸三原色中一種顏色)畫面傳輸至其他屏幕上?如果是，請說明原因。如果否，請說明理論上大約多久才能傳送一幀真彩畫面。

　　26.(4分)將N條長度均為M的有序鏈表進行合并，合并以后的鏈表也保持有序，時間復雜度為 。

　　27.(6分)有ABCD四人，要在夜里過一座橋。他們通過這座橋分別耗時1、2、5、10分鐘，只有一只手電，并且同時最多只能兩個人一起過橋，請你安排過橋方案，能夠使這四個人都過橋，且總共花的時間最短。需要給出所花費的時間以及具體方案。

　　28. (8分)下列代碼是實現有序證書數組的二分查找(也稱為折半查找)，請指出其中的bug。

　　int binary_search( int array, int length, int key){

　　int start = 0, end = length – 1;

　　while(end > start){

　　int middle = (start + end) / 2;

　　int tmp = array[middle];

　　if(tmp < key){

　　start = middle;

　　}else if(tmp > key){

　　end = middle;

　　}else{

　　return middle;

　　}

　　}

　　return -1;

　　}

　　29.(8分)有種數據結構叫做跳躍列表(Skip List)，它是基于并聯的鏈表隨機化數據結構，其效率可比擬于二叉查找樹(對于大多數操作需要O(n logn)平均時間)。它是按層建造的，底層是一個普通的有序鏈表，每個更高層都充當下面列表的“快速跑道”，這里在層i中的元素按概率1/p出現在層i+1中。平均起來，每個元素都在p/(p-1)個列表中出現，而最高層的元素(通常是在跳躍列表前端的一個特殊的頭元素)在O(logpn)個列表中出現，調節p的大小可以在內存消耗和時間消耗上進行折中。試分析在該數據結構中查找一個元素的平均時間復雜度。