阿里巴巴2013實習筆試

1、13-5-5阿里巴巴實習生部分筆試題單選題：20分下列說法錯誤的是_A.B.C.千兆網(wǎng)卡的讀寫速度是1Gb/s.D.DDR3內(nèi)存的速度是100Gb/s下面不能用作linux進程間通信的是_A.共享內(nèi)存B.管道名C.信號量D.臨界區(qū)管道(Pipe):管道可用于具有親緣關系進程間的通信，允許一個進程和另一個與它有 共同祖先的進程之間進行通信。命名管道(named pipe):命名管道克服了管道沒有名字的限制，因此，除具有管道所 具有的功能外，它還允許無親緣關系進程間的通信。命名管道在文件系統(tǒng)中有對應的文 件名。命名管道通過命令mkfifo或系統(tǒng)調(diào)用mkfifo來創(chuàng)建。信號(Signal)：信號是比

2、較復雜的通信方式，用于通知接受進程有某種事件發(fā)生，除 了用于進程間通信外，進程還可以發(fā)送信號給進程本身；linux除了支持Unix早期信號 語義函數(shù)sigal外，還支持語義符合Posix.1標準的信號函數(shù)sigaction(實際上，該函數(shù) 是基于BSD的，BSD為了實現(xiàn)可靠信號機制，又能夠統(tǒng)一對外接口，用sigaction函數(shù) 重新實現(xiàn)了 signal函數(shù))。消息(Message)隊列：消息隊列是消息的鏈接表，包括Posix消息隊列system V消息 隊列。有足夠權(quán)限的進程可以向隊列中添加消息，被賦予讀權(quán)限的進程則可以讀走隊列 中的消息。消息隊列克服了信號承載信息量少，管道只能承載無格式字節(jié)

3、流以及緩沖區(qū) 大小受限等缺共享內(nèi)存：使得多個進程可以訪問同一塊內(nèi)存空間，是最快的可用IPC形式。是針對 其他通信機制運行效率較低而設計的。往往與其它通信機制，如信號量結(jié)合使用，來達 到進程間的同步及互斥。內(nèi)存映射(mapped memory)：內(nèi)存映射允許任何多個進程間通信，每一個使用該機制 的進程通過把一個共享的文件映射到自己的進程地址空間來實現(xiàn)它。信號量(semaphore)：主要作為進程間以及同一進程不同線程之間的同步手段。套接口(Socket)：更為一般的進程間通信機制；CPU和I/0 一次只能處理一個程序，現(xiàn)有P1:計算 40ms I/o80ms 計算 40msP2:計算 120ms

4、 I/o20ms 計算 40msp3:計算 60ms I/o40ms 計算 60ms求并行處理節(jié)約的時間兩個進程同時執(zhí)行一個函數(shù),a是全局變量，初始a=0： printf，+，-是原子操作，void f()if(a=0)a+;elsea-;printf(%d”,a);問結(jié)果可能值不可能是_A.01B.10 C.12 D.225、長度為n的字符串匹配子串長度為m的字符串，求算法的復雜度最小為A.O（n） B.O（n+m） C.O（n+logm） D.O（m+logn）6、下列排序算法中最壞復雜度不是n（n-1）/2的是_A.快速排序B.冒泡排序C.直接插入排序D.堆排序7、遞歸，求函數(shù)輸出值8、

5、c+中，一個頻繁使用的整型變量，設為什么類型？auto、 static、 register、extern9、數(shù)組an中找到i、j、k使ai+aj = ak,時間復雜度？10、概率題目：一個人進行三次射擊，射中的概率為0.95，求一次射擊射中的概率？A 0.63 B 0.5 CD不定項選擇題：20分1、進程狀態(tài)圖：就緒態(tài)、運行態(tài)、阻塞態(tài)的轉(zhuǎn)換關系：2、棧的輸入序列是1、2、3、4、5、6,選出可能的輸出序列：3、選出下面把a、b的值進行交換了的選項：有或運算4、數(shù)星星，一次只能數(shù)20=k4）個戰(zhàn)士，每個人情報不同，兩兩交換之后最后要使每個人知 道所有人的情報，請設計算法，不要求寫代碼，并求出最小的交流數(shù)目。5、N-1個群眾，1個明星，所有群眾都認識明星，而明星不認識所有群眾，群眾之間的認 識情況不知道，有一個機器人，能夠詢問一個人是否認識另外一個人，求最優(yōu)算法，通 過該機器人找到明星，并分析時間復雜度。（算法描述就行）6、N個倉庫，構(gòu)成首尾相連的圓環(huán)，每個倉庫有一個儲存量，想要使所有倉庫的儲存量都 弄為一樣，相鄰的兩個