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

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

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

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

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