[自我管理與提升]2014騰訊校園面試

1、.2014年騰訊，百度，微軟，阿里巴巴（北京站）校園招聘筆試題（涉及C,C+,JAVA,數(shù)據(jù)結(jié)構(gòu)）騰訊2014年校園招聘筆試題 2014年阿里巴巴校招筆試題北京站（涉及C+,JAVA,數(shù)據(jù)結(jié)構(gòu)） 2014年微軟校園招聘筆試題 百度2014校園招聘-研發(fā)工程師筆試題（濟(jì)南站）一，簡(jiǎn)答題(30分)1，當(dāng)前計(jì)算機(jī)系統(tǒng)一般會(huì)采用層次結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)，請(qǐng)介紹下典型計(jì)算機(jī)存儲(chǔ)系統(tǒng)一般分為哪幾個(gè)層次，為什么采用分層存儲(chǔ)數(shù)據(jù)能有效提高程序的執(zhí)行效率？（10分）所謂存儲(chǔ)系統(tǒng)的層次結(jié)構(gòu)，就是把各種不同存儲(chǔ)容量、存取速度和價(jià)格的存儲(chǔ)器按層次結(jié)構(gòu)組成多層存儲(chǔ)器，并通過管理軟件和輔助硬件有機(jī)組合成統(tǒng)一的整體，使所存放的程序

2、和數(shù)據(jù)按層次分布在各種存儲(chǔ)器中。目前，在計(jì)算機(jī)系統(tǒng)中通常采用三級(jí)層次結(jié)構(gòu)來構(gòu)成存儲(chǔ)系統(tǒng)，主要由高速緩沖存儲(chǔ)器Cache、主存儲(chǔ)器和輔助存儲(chǔ)器組成。存儲(chǔ)系統(tǒng)多級(jí)層次結(jié)構(gòu)中，由上向下分三級(jí)，其容量逐漸增大，速度逐級(jí)降低，成本則逐次減少。整個(gè)結(jié)構(gòu)又可以看成兩個(gè)層次：它們分別是主存一輔存層次和cache一主存層次。這個(gè)層次系統(tǒng)中的每一種存儲(chǔ)器都不再是孤立的存儲(chǔ)器，而是一個(gè)有機(jī)的整體。它們?cè)谳o助硬件和計(jì)算機(jī)操作系統(tǒng)的管理下，可把主存一輔存層次作為一個(gè)存儲(chǔ)整體，形成的可尋址存儲(chǔ)空間比主存儲(chǔ)器空間大得多。由于輔存容量大，價(jià)格低，使得存儲(chǔ)系統(tǒng)的整體平均價(jià)格降低。由于Cache的存取速度可以和CPU的工作速度相

3、媲美，故cache一主存層次可以縮小主存和cPu之間的速度差距，從整體上提高存儲(chǔ)器系統(tǒng)的存取速度。盡管Cache成本高，但由于容量較小，故不會(huì)使存儲(chǔ)系統(tǒng)的整體價(jià)格增加很多。綜上所述，一個(gè)較大的存儲(chǔ)系統(tǒng)是由各種不同類型的存儲(chǔ)設(shè)備構(gòu)成，是一個(gè)具有多級(jí)層次結(jié)構(gòu)的存儲(chǔ)系統(tǒng)。該系統(tǒng)既有與CPU相近的速度，又有極大的容量，而成本又是較低的。其中高速緩存解決了存儲(chǔ)系統(tǒng)的速度問題，輔助存儲(chǔ)器則解決了存儲(chǔ)系統(tǒng)的容量問題。采用多級(jí)層次結(jié)構(gòu)的存儲(chǔ)器系統(tǒng)可以有效的解決存儲(chǔ)器的速度、容量和價(jià)格之間的矛盾。2，Unix/Linux系統(tǒng)中僵尸進(jìn)程是如何產(chǎn)生的？有什么危害？如何避免？(10分)一個(gè)進(jìn)程在調(diào)用exit命令結(jié)束自

4、己的生命的時(shí)候，其實(shí)它并沒有真正的被銷毀，而是留下一個(gè)稱為僵尸進(jìn)程（Zombie）的數(shù)據(jù)結(jié)構(gòu)（系統(tǒng)調(diào)用exit，它的作用是使進(jìn)程退出，但也僅僅限于將一個(gè)正常的進(jìn)程變成一個(gè)僵尸進(jìn)程，并不能將其完全銷毀）。在Linux進(jìn)程的狀態(tài)中，僵尸進(jìn)程是非常特殊的一種，它已經(jīng)放棄了幾乎所有內(nèi)存空間，沒有任何可執(zhí)行代碼，也不能被調(diào)度，僅僅在進(jìn)程列表中保留一個(gè)位置，記載該進(jìn)程的退出狀態(tài)等信息供其他進(jìn)程收集，除此之外，僵尸進(jìn)程不再占有任何內(nèi)存空間。它需要它的父進(jìn)程來為它收尸，如果他的父進(jìn)程沒安裝SIGCHLD信號(hào)處理函數(shù)調(diào)用wait或waitpid()等待子進(jìn)程結(jié)束，又沒有顯式忽略該信號(hào)，那么它就一直保持僵尸狀態(tài)，

5、如果這時(shí)父進(jìn)程結(jié)束了，那么init進(jìn)程自動(dòng)會(huì)接手這個(gè)子進(jìn)程，為它收尸，它還是能被清除的。但是如果如果父進(jìn)程是一個(gè)循環(huán)，不會(huì)結(jié)束，那么子進(jìn)程就會(huì)一直保持僵尸狀態(tài)，這就是為什么系統(tǒng)中有時(shí)會(huì)有很多的僵尸進(jìn)程。避免zombie的方法： 1)在SVR4中，如果調(diào)用signal或sigset將SIGCHLD的配置設(shè)置為忽略,則不會(huì)產(chǎn)生僵死子進(jìn)程。另外,使用SVR4版的sigaction,則可設(shè)置SA_NOCLDWAIT標(biāo)志以避免子進(jìn)程 僵死。 Linux中也可使用這個(gè)，在一個(gè)程序的開始調(diào)用這個(gè)函數(shù) signal(SIGCHLD,SIG_IGN); 2)調(diào)用fork兩次。3)用waitpid等待子進(jìn)程返回.

6、 3，簡(jiǎn)述Unix/Linux系統(tǒng)中使用socket庫編寫服務(wù)器端程序的流程，請(qǐng)分別用對(duì)應(yīng)的socket通信函數(shù)表示(10分)TCP socket通信服務(wù)器端流程如下：1.創(chuàng)建serverSocket2.初始化 serverAddr（服務(wù)器地址）3.將socket和serverAddr 綁定 bind4.開始監(jiān)聽 listen5.進(jìn)入while循環(huán)，不斷的accept接入的客戶端socket，進(jìn)行讀寫操作write和read6.關(guān)閉serverSocket客戶端流程：1.創(chuàng)建clientSocket2.初始化 serverAddr3.鏈接到服務(wù)器 connect4.利用write和read 進(jìn)

7、行讀寫操作5.關(guān)閉clientSocket 這個(gè)列表是一個(gè)Berkeley套接字API庫提供的函數(shù)或者方法的概要：socket() 創(chuàng)建一個(gè)新的確定類型的套接字，類型用一個(gè)整型數(shù)值標(biāo)識(shí)，并為它分配系統(tǒng)資源。bind() 一般用于服務(wù)器端，將一個(gè)套接字與一個(gè)套接字地址結(jié)構(gòu)相關(guān)聯(lián)，比如，一個(gè)指定的本地端口和IP地址。listen() 用于服務(wù)器端，使一個(gè)綁定的TCP套接字進(jìn)入監(jiān)聽狀態(tài)。connect() 用于客戶端，為一個(gè)套接字分配一個(gè)自由的本地端口號(hào)。 如果是TCP套接字的話，它會(huì)試圖獲得一個(gè)新的TCP連接。accept() 用于服務(wù)器端。 它接受一個(gè)從遠(yuǎn)端客戶端發(fā)出的創(chuàng)建一個(gè)新的TCP連接的接

8、入請(qǐng)求，創(chuàng)建一個(gè)新的套接字，與該連接相應(yīng)的套接字地址相關(guān)聯(lián)。send()和recv(),或者write()和read(),或者recvfrom()和sendto(), 用于往/從遠(yuǎn)程套接字發(fā)送和接受數(shù)據(jù)。close() 用于系統(tǒng)釋放分配給一個(gè)套接字的資源。 如果是TCP，連接會(huì)被中斷。gethostbyname()和gethostbyaddr() 用于解析主機(jī)名和地址。select() 用于修整有如下情況的套接字列表： 準(zhǔn)備讀，準(zhǔn)備寫或者是有錯(cuò)誤。poll() 用于檢查套接字的狀態(tài)。 套接字可以被測(cè)試，看是否可以寫入、讀取或是有錯(cuò)誤。getsockopt() 用于查詢指定的套接字一個(gè)特定的套接

9、字選項(xiàng)的當(dāng)前值。setsockopt() 用于為指定的套接字設(shè)定一個(gè)特定的套接字選項(xiàng)。二，算法與程序設(shè)計(jì)題1，使用C/C+編寫函數(shù)，實(shí)現(xiàn)字符串反轉(zhuǎn)，要求不使用任何系統(tǒng)函數(shù)，且時(shí)間復(fù)雜度最小，函數(shù)原型：char* reverse_str(char* str)。(15分)獲取首尾指針，然后將首尾指針指向的元素交換，將首指針指向下一個(gè)，將尾指針指向前一個(gè)，交換指針指向的元素，然后重復(fù)執(zhí)行，直到首尾指針相遇。 2，給定一個(gè)如下格式的字符串(1,(2,3),(4,(5,6),7)括號(hào)內(nèi)的元素可以是數(shù)字，也可以是另一個(gè)括號(hào)，請(qǐng)實(shí)現(xiàn)一個(gè)算法消除嵌套的括號(hào)，比如把上面的表達(dá)式變成：(1,2,3,4,5,6,7

10、)，如果表達(dá)式有誤請(qǐng)報(bào)錯(cuò)。(15分)使用棧和隊(duì)列實(shí)現(xiàn) 2013年阿里巴巴暑期實(shí)習(xí)招聘筆試題目及部分答案5月5日 答題說明：1.答題時(shí)間90分鐘，請(qǐng)注意把握時(shí)間；2.試題分為四個(gè)部分：?jiǎn)雾?xiàng)選擇題（10題，20分）、不定向選擇題（4題，20分）、填空問答（5題，40分）、綜合體（1題，20分）；3.其他一些亂七八糟的考試說明。一、單項(xiàng)選擇題1.下列說法不正確的是：A.SATA硬盤的速度速度大約為500Mbps/sB.讀取18XDVD光盤數(shù)據(jù)的速度為1GbpsC.前兆以太網(wǎng)的數(shù)據(jù)讀取速度為1GpbsD.讀取DDR3內(nèi)存數(shù)據(jù)的速度為100Gbps2.（）不能用于Linux中的進(jìn)程通信A.共享內(nèi)存B.命

11、名管道C.信號(hào)量D.臨界區(qū)3.設(shè)在內(nèi)存中有P1,P2,P3三道程序，并按照P1,P2,P3的優(yōu)先級(jí)次序運(yùn)行，其中內(nèi)部計(jì)算和IO操作時(shí)間由下表給出（CPU計(jì)算和IO資源都只能同時(shí)由一個(gè)程序占用）：P1:計(jì)算60ms-IO 80ms-計(jì)算20msP2:計(jì)算120ms-IO 40ms-計(jì)算40msP3:計(jì)算40ms-IO 80ms-計(jì)算40ms完成三道程序比單道運(yùn)行節(jié)省的時(shí)間是（）A.80msB.120msC.160msD.200ms4.兩個(gè)等價(jià)線程并發(fā)的執(zhí)行下列程序，a為全局變量，初始為0，假設(shè)printf、+、-操作都是原子性的，則輸出不肯哪個(gè)是（）void foo() if(a = 0) a+

12、; else a-; printf(%d, a);A.01B.10C.12D.225.給定fun函數(shù)如下，那么fun(10)的輸出結(jié)果是（）int fun(int x) return (x=1) ? 1 : (x + fun(x-1);A.0B.10C.55D.36288006.在c+程序中，如果一個(gè)整型變量頻繁使用，最好將他定義為（）A.autoB.externC.staticD.register7.長(zhǎng)為n的字符串中匹配長(zhǎng)度為m的子串的復(fù)雜度為（）A.O(N)B.O(M+N)C.O(N+LOGM)D.O(M+LOGN)8.判斷一包含n個(gè)整數(shù)a中是否存在i、j、k滿足ai + aj = ak的

13、時(shí)間復(fù)雜度為（）A.O(n) B.O(n2) C.O(nlog(n) D.O(n2log(n)9.三次射擊能中一次的概率是0.95，請(qǐng)問一次射擊能中的概率是多少？A.0.63B.0.5C.*D.0.8510.下列序排算法中最壞復(fù)雜度不是n(n-1)/2的是_A.快速序排 B.冒泡序排 C.直接插入序排 D.堆序排二、不定向選擇題1.以下哪些進(jìn)程狀態(tài)轉(zhuǎn)換是正確的()A.就緒到運(yùn)行 B.運(yùn)行到就緒 C.運(yùn)行到阻塞 D.阻塞到運(yùn)行 E.阻塞到就緒2.一個(gè)棧的入棧數(shù)列為：1、2、3、4、5、6；下列哪個(gè)是可能的出棧順序。（選項(xiàng)不記得）3.下列哪些代碼可以使得a和b交換數(shù)值。（選項(xiàng)不記得）4.A和B晚上

14、無聊就開始數(shù)星星。每次只能數(shù)K個(gè)（20=k4），每個(gè)戰(zhàn)士知道當(dāng)前的一些戰(zhàn)況，現(xiàn)在需要這n個(gè)戰(zhàn)士通過通話交流，互相傳達(dá)自己知道的戰(zhàn)況信息，每次通話，可以讓通話的雙方知道對(duì)方的所有情報(bào)，設(shè)計(jì)算法，使用最少的通話次數(shù)，是的戰(zhàn)場(chǎng)上的n個(gè)士兵知道所有的戰(zhàn)況信息，不需要寫程序代碼，得出最少的通話次數(shù)。5.有N個(gè)人，其中一個(gè)明星和n-1個(gè)群眾，群眾都認(rèn)識(shí)明星，明星不認(rèn)識(shí)任何群眾，群眾和群眾之間的認(rèn)識(shí)關(guān)系不知道，現(xiàn)在如果你是機(jī)器人R2T2，你每次問一個(gè)人是否認(rèn)識(shí)另外一個(gè)人的代價(jià)為O(1)，試設(shè)計(jì)一種算法找出明星，并給出時(shí)間復(fù)雜度（沒有復(fù)雜度不得分）。解答：這個(gè)問題等價(jià)于找未知序列數(shù)中的最小數(shù)，我們將reg這個(gè)

15、函數(shù)等價(jià)為以下過程：，如果i認(rèn)識(shí)j，記作i大于等于j,同樣j不一定大于等于i,滿足要求，i不認(rèn)識(shí)j記作ij，對(duì)明星k,他不認(rèn)識(shí)所有人，則k是其中最小的數(shù)，且滿足其余的人都認(rèn)識(shí)他，也就是其余的人都大于等于k.這樣問題就被轉(zhuǎn)換了。就拿N=5來說，首先有數(shù)組S5=A,B,C,D,E這5個(gè)變量，里邊存放著隨機(jī)數(shù)，求是否存在唯一最小數(shù)，如果存在位置在S中的哪里。（樓主這里是這個(gè)意思，按我的理解題中這個(gè)最小數(shù)一定是存在且唯一的）int finds(S,N) int flag=0;/用于判定是否有明星，即當(dāng)前最小數(shù)另外出現(xiàn)幾次 int temp=0;/存放最小數(shù)在S中的位置 for(i=1;i0) retu

16、rn -1;/表示沒有明星,例如所有的數(shù)都相等 return temp;/返回明星在S中的位置四、綜合題有一個(gè)淘寶商戶，在某城市有n個(gè)倉庫，每個(gè)倉庫的儲(chǔ)貨量不同，現(xiàn)在要通過貨物運(yùn)輸，將每次倉庫的儲(chǔ)貨量變成一致的，n個(gè)倉庫之間的運(yùn)輸線路圍城一個(gè)圈，即1-2-3-4-.-n-1-.，貨物只能通過連接的倉庫運(yùn)輸，設(shè)計(jì)最小的運(yùn)送成本（運(yùn)貨量*路程）達(dá)到淘寶商戶的要求，并寫出代碼。解答：這個(gè)題目類似的題目有：題目：有n個(gè)小朋友坐成一圈，每人有ai個(gè)糖果。每人只能給左右兩人傳遞糖果。每人每次傳遞一個(gè)糖果代價(jià)為1，求使所有人獲得均等糖果的最小代價(jià)。分析：假設(shè)a1分給an的糖果數(shù)為k，則可以得到以下的信息：a

17、1 a2 a3 an-1 an當(dāng)前數(shù)目：a1-k a2 a3 an-1 an+k所需代價(jià)：|a1-k-ave| |a1+a2-k-2*ave| |a1+a2+a3-k-3*ave|a1+.+a(n-1)-k-(n-1)*ave| |k|以sumi表示從a1加到ai減掉i*ave的和值，這以上可以化簡(jiǎn)為總代價(jià) = |s1-k|+|s2-k|+.+|s(n-1)-k|+|k|不難看出：當(dāng)k為s1.s(n-1)中的中位數(shù)的時(shí)候，所需的代價(jià)最小代碼轉(zhuǎn)載于網(wǎng)絡(luò)：#include #include #include using namespace std;const int X = 1000005;typedef long long ll;ll sumX,aX;ll n;ll Abs(ll x) return max(x,-x);int main() /freopen(s