各大公司筆試題

各大公司筆試題資料僅供參考騰訊，百度，微軟，阿里巴巴（北京站）校園招聘筆試題（涉及C,C++,JAVA,數(shù)據(jù)結構）騰訊校園招聘筆試題

阿里巴巴校招筆試題北京站（涉及C++,JAVA,數(shù)據(jù)結構）

微軟校園招聘筆試題

百度校園招聘-研發(fā)工程師筆試題（濟南站）一，簡答題(30分)1，當前計算機系統(tǒng)一般會采用層次結構存儲數(shù)據(jù)，請介紹下典型計算機存儲系統(tǒng)一般分為哪幾個層次，為什么采用分層存儲數(shù)據(jù)能有效提高程序的執(zhí)行效率？（10分）所謂存儲系統(tǒng)的層次結構，就是把各種不同存儲容量、存取速度和價格的存儲器按層次結構組成多層存儲器，并經(jīng)過管理軟件和輔助硬件有機組合成統(tǒng)一的整體，使所存放的程序和數(shù)據(jù)按層次分布在各種存儲器中。當前，在計算機系統(tǒng)中一般采用三級層次結構來構成存儲系統(tǒng)，主要由高速緩沖存儲器Cache、主存儲器和輔助存儲器組成。

存儲系統(tǒng)多級層次結構中，由上向下分三級，其容量逐漸增大，速度逐級降低，成本則逐次減少。整個結構又能夠看成兩個層次：它們分別是主存一輔存層次和cache一主存層次。這個層次系統(tǒng)中的每一種存儲器都不再是孤立的存儲器，而是一個有機的整體。它們在輔助硬件和計算機操作系統(tǒng)的管理下，可把主存一輔存層次作為一個存儲整體，形成的可尋址存儲空間比主存儲器空間大得多。由于輔存容量大，價格低，使得存儲系統(tǒng)的整體平均價格降低。由于Cache的存取速度能夠和CPU的工作速度相媲美，故cache一主存層次能夠縮小主存和cPu之間的速度差距，從整體上提高存儲器系統(tǒng)的存取速度。盡管Cache成本高，但由于容量較小，故不會使存儲系統(tǒng)的整體價格增加很多。

綜上所述，一個較大的存儲系統(tǒng)是由各種不同類型的存儲設備構成，是一個具有多級層次結構的存儲系統(tǒng)。該系統(tǒng)既有與CPU相近的速度，又有極大的容量，而成本又是較低的。其中高速緩存解決了存儲系統(tǒng)的速度問題，輔助存儲器則解決了存儲系統(tǒng)的容量問題。采用多級層次結構的存儲器系統(tǒng)能夠有效的解決存儲器的速度、容量和價格之間的矛盾。2，Unix/Linux系統(tǒng)中僵尸進程是如何產(chǎn)生的？有什么危害？如何避免？(10分)一個進程在調(diào)用exit命令結束自己的生命的時候，其實它并沒有真正的被銷毀，而是留下一個稱為僵尸進程（Zombie）的數(shù)據(jù)結構（系統(tǒng)調(diào)用exit，它的作用是使進程退出，但也僅僅限于將一個正常的進程變成一個僵尸進程，并不能將其完全銷毀）。

在Linux進程的狀態(tài)中，僵尸進程是非常特殊的一種，它已經(jīng)放棄了幾乎所有內(nèi)存空間，沒有任何可執(zhí)行代碼，也不能被調(diào)度，僅僅在進程列表中保留一個位置，記載該進程的退出狀態(tài)等信息供其它進程收集，除此之外，僵尸進程不再占有任何內(nèi)存空間。它需要它的父進程來為它收尸，如果她的父進程沒安裝SIGCHLD信號處理函數(shù)調(diào)用wait或waitpid()等待子進程結束，又沒有顯式忽略該信號，那么它就一直保持僵尸狀態(tài)，如果這時父進程結束了，那么init進程自動會接手這個子進程，為它收尸，它還是能被清除的。可是如果如果父進程是一個循環(huán)，不會結束，那么子進程就會一直保持僵尸狀態(tài)，這就是為什么系統(tǒng)中有時會有很多的僵尸進程。避免zombie的方法：

1)在SVR4中，如果調(diào)用signal或sigset將SIGCHLD的配置設置為忽略,則不會產(chǎn)生僵死子進程。另外,使用SVR4版的sigaction,則可設置SA_NOCLDWAIT標志以避免子進程僵死。

Linux中也可使用這個，在一個程序的開始調(diào)用這個函數(shù)signal(SIGCHLD,SIG_IGN);

2)調(diào)用fork兩次。

3)用waitpid等待子進程返回.

3，簡述Unix/Linux系統(tǒng)中使用socket庫編寫服務器端程序的流程，請分別用對應的socket通信函數(shù)表示(10分)TCPsocket通信

服務器端流程如下：

1.創(chuàng)立serverSocket

2.初始化serverAddr（服務器地址）

3.將socket和serverAddr綁定bind

4.開始監(jiān)聽listen

5.進入while循環(huán)，不斷的accept接入的客戶端socket，進行讀寫操作write和read

6.關閉serverSocket

客戶端流程：

1.創(chuàng)立clientSocket

2.初始化serverAddr

3.鏈接到服務器connect

4.利用write和read進行讀寫操作

5.關閉clientSocket

這個列表是一個Berkeley套接字API庫提供的函數(shù)或者方法的概要：

socket()創(chuàng)立一個新的確定類型的套接字，類型用一個整型數(shù)值標識，并為它分配系統(tǒng)資源。

bind()一般用于服務器端，將一個套接字與一個套接字地址結構相關聯(lián)，比如，一個指定的本地端口和IP地址。

listen()用于服務器端，使一個綁定的TCP套接字進入監(jiān)聽狀態(tài)。

connect()用于客戶端，為一個套接字分配一個自由的本地端口號。如果是TCP套接字的話，它會試圖獲得一個新的TCP連接。

accept()用于服務器端。它接受一個從遠端客戶端發(fā)出的創(chuàng)立一個新的TCP連接的接入請求，創(chuàng)立一個新的套接字，與該連接相應的套接字地址相關聯(lián)。

send()和recv(),或者write()和read(),或者recvfrom()和sendto(),用于往/從遠程套接字發(fā)送和接受數(shù)據(jù)。

close()用于系統(tǒng)釋放分配給一個套接字的資源。如果是TCP，連接會被中斷。

gethostbyname()和gethostbyaddr()用于解析主機名和地址。

select()用于修整有如下情況的套接字列表：準備讀，準備寫或者是有錯誤。

poll()用于檢查套接字的狀態(tài)。套接字能夠被測試，看是否能夠寫入、讀取或是有錯誤。

getsockopt()用于查詢指定的套接字一個特定的套接字選項的當前值。

setsockopt()用于為指定的套接字設定一個特定的套接字選項。二，算法與程序設計題1，使用C/C++編寫函數(shù)，實現(xiàn)字符串反轉，要求不使用任何系統(tǒng)函數(shù)，且時間復雜度最小，函數(shù)原型：char*reverse_str(char*str)。(15分)獲取首尾指針，然后將首尾指針指向的元素交換，將首指針指向下一個，將尾指針指向前一個，交換指針指向的元素，然后重復執(zhí)行，直到首尾指針相遇。

2，給定一個如下格式的字符串(1,(2,3),(4,(5,6),7))括號內(nèi)的元素能夠是數(shù)字，也能夠是另一個括號，請實現(xiàn)一個算法消除嵌套的括號，比如把上面的表示式變成：(1,2,3,4,5,6,7)，如果表示式有誤請報錯。(15分)使用棧和隊列實現(xiàn)

阿里巴巴暑期實習招聘筆試題目及部分答案——5月5日

答題說明：1.答題時間90分鐘，請注意把握時間；2.試題分為四個部分：單項選擇題（10題，20分）、不定向選擇題（4題，20分）、填空問答（5題，40分）、綜合體（1題，20分）；3.其它一些亂七八糟的考試說明。一、單項選擇題1.下列說法不正確的是：A.SATA硬盤的速度速度大約為500Mbps/sB.讀取18XDVD光盤數(shù)據(jù)的速度為1GbpsC.前兆以太網(wǎng)的數(shù)據(jù)讀取速度為1GpbsD.讀取DDR3內(nèi)存數(shù)據(jù)的速度為100Gbps2.（）不能用于Linux中的進程通信A.共享內(nèi)存B.命名管道C.信號量D.臨界區(qū)3.設在內(nèi)存中有P1,P2,P3三道程序，并按照P1,P2,P3的優(yōu)先級次序運行，其中內(nèi)部計算和IO操作時間由下表給出（CPU計算和IO資源都只能同時由一個程序占用）：P1:計算60ms---》IO80ms---》計算20msP2:計算120ms---》IO40ms---》計算40msP3:計算40ms---》IO80ms---》計算40ms完成三道程序比單道運行節(jié)省的時間是（）A.80msB.120msC.160msD.200ms4.兩個等價線程并發(fā)的執(zhí)行下列程序，a為全局變量，初始為0，假設printf、++、--操作都是原子性的，則輸出不肯哪個是（）void

foo()

{

if(a

<=

0)

{

a++;

}

else

{

a--;

}

printf("%d",

a);}A.01B.10C.12D.225.給定fun函數(shù)如下，那么fun(10)的輸出結果是（）int

fun(int

x)

{

return

(x==1)

?

1

:

(x

+

fun(x-1));}A.0B.10C.55D.36288006.在c++程序中，如果一個整型變量頻繁使用，最好將她定義為（）A.autoB.externC.staticD.register7.長為n的字符串中匹配長度為m的子串的復雜度為（）A.O(N)B.O(M+N)C.O(N+LOGM)D.O(M+LOGN)8.判斷一包含n個整數(shù)a[]中是否存在i、j、k滿足a[i]+a[j]=a[k]的時間復雜度為（）A.O(n)B.O(n^2)C.O(nlog(n))D.O(n^2log(n))9.三次射擊能中一次的概率是0.95，請問一次射擊能中的概率是多少？

A.0.63B.0.5C.**D.0.8510.下列序排算法中最壞復雜度不是n(n-1)/2的是_A.快速序排B.冒泡序排C.直接插入序排D.堆序排二、不定向選擇題1.以下哪些進程狀態(tài)轉換是正確的()A.就緒到運行B.運行到就緒C.運行到阻塞D.阻塞到運行E.阻塞到就緒2.一個棧的入棧數(shù)列為：1、2、3、4、5、6；下列哪個是可能的出棧順序。（選項不記得）3.下列哪些代碼能夠使得a和b交換數(shù)值。（選項不記得）4.A和B晚上無聊就開始數(shù)星星。每次只能數(shù)K個（20<=k<=30）A和B輪流數(shù)。最后誰把星星數(shù)完誰就獲勝，那么當星星數(shù)量為多少時候A必勝？（選項不記得）三、填空問答題1.給你一個整型數(shù)組A[N]，完成一個小程序代碼（20行之內(nèi)），使得A[N]逆向，即原數(shù)組為1，2，3，4，逆向之后為4，3，2，1voidrevense(int*a,intn){}2.自選調(diào)度方面的問題，題目很長，就是給你三個線程，分別采用先來先分配的策略和最短執(zhí)行之間的調(diào)度策略，然后計算每個線程從提交到執(zhí)行完成的時間。題目實在太長，還有幾個表格?？疾斓氖遣僮飨到y(tǒng)里面作業(yè)調(diào)度算法先進先出和最短作業(yè)優(yōu)先。3.有個苦逼的上班族，她每天忘記定鬧鐘的概率為0.2，上班堵車的概率為0.5，如果她既沒定鬧鐘上班又堵車那她遲到的概率為1.0，如果她定了鬧鐘可是上班堵車那她遲到的概率為0.9，如果她沒定鬧鐘可是上班不堵車她遲到的概率為0.8，如果她既定了鬧鐘上班又不堵車那她遲到的概率為0.0，那么求出她在60天里上班遲到的期望。4.戰(zhàn)報交流：戰(zhàn)場上不同的位置有N個戰(zhàn)士（n>4），每個戰(zhàn)士知道當前的一些戰(zhàn)況，現(xiàn)在需要這n個戰(zhàn)士經(jīng)過通話交流，互相傳達自己知道的戰(zhàn)況信息，每次通話，能夠讓通話的雙方知道對方的所有情報，設計算法，使用最少的通話次數(shù)，是的戰(zhàn)場上的n個士兵知道所有的戰(zhàn)況信息，不需要寫程序代碼，得出最少的通話次數(shù)。5.有N個人，其中一個明星和n-1個群眾，群眾都認識明星，明星不認識任何群眾，群眾和群眾之間的認識關系不知道，現(xiàn)在如果你是機器人R2T2，你每次問一個人是否認識另外一個人的代價為O(1)，試設計一種算法找出明星，并給出時間復雜度（沒有復雜度不得分）。解答：這個問題等價于找未知序列數(shù)中的最小數(shù)，我們將reg這個函數(shù)等價為以下過程：，如果i認識j，記作i大于等于j,同樣j不一定大于等于i,滿足要求，i不認識j記作i<j，對明星k,她不認識所有人，則k是其中最小的數(shù)，且滿足其余的人都認識她，也就是其余的人都大于等于k.這樣問題就被轉換了。就拿N=5來說，首先有數(shù)組S[5]={A,B,C,D,E}這5個變量，里邊存放著隨機數(shù)，求是否存在唯一最小數(shù)，如果存在位置在S中的哪里。（樓主這里是這個意思，按我的理解題中這個最小數(shù)一定是存在且唯一的）int

finds(S,N){

int

flag=0;//用于判定是否有明星，即當前最小數(shù)另外出現(xiàn)幾次

int

temp=0;//存放最小數(shù)在S中的位置

for(i=1;i<N;i++)

｛

if(!reg(S[i],S[temp])//如果temp標號的數(shù)小于i標號的數(shù)

｛

temp=i;

flag=0;//更換懷疑對象（最小數(shù)）時，標記清零

｝

elseif(reg(S[temp]，S[i])//如果temp里存放的確實是唯一最小數(shù)是不會跑進這里來的

{

flag++;`

}

｝

if(flag>0)

return

-1;//表示沒有明星,例如所有的數(shù)都相等

return

temp;//返回明星在S中的位置}四、綜合題有一個淘寶商戶，在某城市有n個倉庫，每個倉庫的儲貨量不同，現(xiàn)在要經(jīng)過貨物運輸，將每次倉庫的儲貨量變成一致的，n個倉庫之間的運輸線路圍城一個圈，即1->2->3->4->...->n->1->...，貨物只能經(jīng)過連接的倉庫運輸，設計最小的運送成本（運貨量*路程）達到淘寶商戶的要求，并寫出代碼。解答：這個題目類似的題目有：題目：

有n個小朋友坐成一圈，每人有ai個糖果。每人只能給左右兩人傳遞糖果。每人每次傳

遞一個糖果代價為1，求使所有人獲得均等糖果的最小代價。

分析：

假設a1分給an的糖果數(shù)為k，則能夠得到以下的信息：

a1a2a3an-1an

當前數(shù)目：a1-ka2a3an-1an+k

所需代價：|a1-k-ave||a1+a2-k-2*ave||a1+a2+a3-k-3*ave||a1+..+a(n-1)-k-(n-1)*ave||k|

以sum[i]表示從a1加到ai減掉i*ave的和值，這以上能夠化簡為

總代價=|s1-k|+|s2-k|+...+|s(n-1)-k|+|k|

不難看出：當k為s1...s(n-1)中的中位數(shù)的時候，所需的代價最小代碼轉載于網(wǎng)絡：#include

<cstring>#include

<iostream>#include

<algorithm>