歷年百度校園招聘筆試題

一：簡答題（30）1：數(shù)據(jù)庫以及線程發(fā)生死鎖的原理及必要條件，如何避免死鎖（操作系統(tǒng)書上有）2：面向?qū)ο蟮娜齻€基本元素，五個基本原則（繼承，封裝，多態(tài)，基本原則沒答上）3：windows內(nèi)存管理的機(jī)制以及優(yōu)缺點(diǎn)（分頁，分段，虛擬內(nèi)存管理....）二：程序設(shè)計題（40）1：公司里面有1001個員工，現(xiàn)在要在公司里面找到最好的羽毛球選手，也就是第一名，每個人都必須參賽，問至少要比賽多少次才能夠找到最好的羽毛球員工。（含偽代碼）--------（個人覺得，兩兩比賽，分成500組剩下一人，類似于歸并排序的方式，比出冠軍后，讓冠軍之間再比，主要是要想想多余的那一個選手如何處理，必然要在第一次決出冠軍后加入比賽組）2：現(xiàn)在有100個燈泡，每個燈泡都是關(guān)著的，第一趟把所有的燈泡燈泡打開，第二趟把偶數(shù)位的燈泡制反（也就是開了的關(guān)掉，關(guān)了的打開），第三趟讓第3,6,9....的燈泡制反.......第100趟讓第100個燈泡制反，問經(jīng)過一百趟以后有多少燈泡亮著-----（覺得這個應(yīng)該是最好做的編程題了，首先定義一個數(shù)組vist[100]，初始化為0，我們假設(shè)已經(jīng)達(dá)到第i個燈泡了，要判斷第i個燈泡最后是開著還是滅了的，要要知道它被開關(guān)了多少次用temp存放，也就是說是偶數(shù)還是奇數(shù)，偶數(shù)顯然最后是關(guān)著的，奇數(shù)則開著，讓i除以比它小的數(shù)字，如果余數(shù)為0就躺temp，最后再根據(jù)temp的值確定vist[i是0還是1，最后掃描整個vist數(shù)組）3：有20個數(shù)組，每個數(shù)組有500個元素，并且是有序排列好的，現(xiàn)在在這20*500個數(shù)中找出排名前500的數(shù)（可以用歸并排序，最后找到500個元素的值，也可以這樣首先找到每個數(shù)組的最大值和最小值，然后存放在一個結(jié)構(gòu)體里面，如果一個數(shù)組里面的最小值大于某一個數(shù)組的最大值，那么某一個數(shù)組就被kill掉，然后提取剩余數(shù)組的最大值----當(dāng)然每個數(shù)組的元素放生變化了，因?yàn)槊看翁崛∽吡俗畲笾?，然后改變結(jié)構(gòu)體里面的最大值和最小值，重復(fù)以上操作，直到找到前五百個數(shù)）三：系統(tǒng)設(shè)計題（30）現(xiàn)在有一個手機(jī)，手機(jī)上的鍵盤上有這樣的對應(yīng)關(guān)系，2對應(yīng)"abc",3對應(yīng)"def".....手機(jī)里面有一個userlist用戶列表，當(dāng)我們輸入942的時候出來拼音的對應(yīng)可能是“xia”，“zha”，“xi”，“yi”等，當(dāng)我們輸入9264的時候出來是yang，可能是“樣”，“楊”，“往”等，現(xiàn)在我們輸入一個字符串?dāng)?shù)字，比如926等，要在電話簿userlist中查找出對應(yīng)的用戶名和電話號碼并返回結(jié)果。---------（個人覺得用哈希表來查找，并用鏈表來處理沖突，如a[2]依次對應(yīng)abc，可以在匹配字符的時候定義一個char（*P)[4]的指針，每個指針指向最多四個char類型的字符串，并且用遍歷的方式依次匹配）一簡答1linux/unix遠(yuǎn)程登陸都用到了ssh服務(wù)，當(dāng)網(wǎng)絡(luò)出現(xiàn)錯誤時服務(wù)會中斷，linux/unix端的程序會停止。為什么會這樣？說下ssh的原理，解釋中斷的原理。2一個最小堆，也是完全二叉樹，用按層遍歷數(shù)組表示。1.

求節(jié)點(diǎn)a[n]的子節(jié)點(diǎn)的訪問方式2.

插入一節(jié)點(diǎn)的程序voidadd_element(int*a,intsize,intval);3.

刪除最小節(jié)點(diǎn)的程序。3關(guān)于hash，有表A，用100%表示，它的粒子度是0.1%，同樣的表B，兩張表組成一層。要將A均勻映射到B，B的每10%里面有1%對應(yīng)該于A的10%。另一問，如果有超過十層以上，要實(shí)現(xiàn)它們之間的這種映射，hash函數(shù)應(yīng)該怎么實(shí)現(xiàn)。二算法1有一個數(shù)，比如N=123，一共有三位，所有位的值加起來是6。我們找出另外一個數(shù)141，也是三位，所有位加起來也是6，這樣和123有同樣關(guān)系的數(shù)還有很多，我們將求一個有這種關(guān)系并且是所有數(shù)中只比基123剛剛好大的數(shù)定義為F（N）。如果不存在,則F(N)=-1.現(xiàn)在有一個數(shù)n，它的位數(shù)小于1000.它的值小于10^500.求F(F(N))=-1。不記得問什么了？是問迭代過程怎么實(shí)現(xiàn)還是問什么時候停止的。反正是一個迭代2求一個全排列函數(shù)：如p([1,2,3])輸出：[123],[132],[213],[231],[321],[323].求一個組合函數(shù)如p([1,2,3])輸出：[1],[2],[3],[1,2],[2,3],[1,3],[1,2,3]這兩問可以用偽代碼。三設(shè)計有兩個十億數(shù)據(jù)的表，表是xxID,xx,xx,xx之類的幾個項(xiàng)，存的是url之類的，只說是存到硬盤的，中間沒說內(nèi)存限制什么的。其中有一問是實(shí)現(xiàn)數(shù)據(jù)查找中的and,or,sub(與集，交集，差集)。其中要實(shí)現(xiàn)and(sub())之類的功能。還有并行實(shí)現(xiàn)…不記得了。另外一問是當(dāng)查找（比如and運(yùn)算）出前100位時，怎么讓它停下來，不要再查找了。怎么實(shí)現(xiàn)這種高效查找前100位的運(yùn)算。一、簡答

1、系統(tǒng)又很多任務(wù)，任務(wù)之間有依賴，比如B依賴于A，則A執(zhí)行完后B才能執(zhí)行

（1）不考慮系統(tǒng)并行性，設(shè)計一個函數(shù)（Task*Ptask,intTask_num）不考慮并行度，最快的方法完成所有任務(wù)。

（2）考慮并行度，怎么設(shè)計

typedefstruct{

intID;

int*child;

intchild_num;

}Task;

提供的函數(shù):

booldoTask(inttaskID);無阻塞的運(yùn)行一個任務(wù)；

intwaitTask(inttimeout);返回運(yùn)行完成的任務(wù)id，如果沒有則返回-1；

boolkillTask(inttaskID);殺死進(jìn)程

2、堆和棧的生命周期，內(nèi)存分配性能，不同處，如果一般情況下要求1KB，偶爾需要100MB的緩存空間怎么設(shè)計？

二、必答題（各種const）1、解釋下面ptr含義和不同（好像是。。。。題干了大概意思是這樣。下面應(yīng)該沒錯）double*prt=&valueconstdouble*ptr=&valuedouble*constptr=&valueconstdouble*constptr=&value2、去掉const屬性，例：constdoublevalue=0.0f;double*ptr=NULL;怎么才能讓ptr指向value？三、算法設(shè)計1、一個一維數(shù)軸上有不同的線段，求重復(fù)最長的兩個線段。例：a：1~3b:

2~7c：2~8最長重復(fù)是b和c2、有向帶權(quán)圖最短路徑四、系統(tǒng)設(shè)計大概意思是：百度內(nèi)部有一個類似cs系統(tǒng)的計算系統(tǒng)，由于大并發(fā)計算很耗資源，所有要設(shè)計一個緩存系統(tǒng)。c做緩存，配置2.66MHZ,3G內(nèi)存，大概有1000w個查詢，唯一的查詢大概有500w。要緩存24小時。設(shè)計這個緩存系統(tǒng)的運(yùn)行機(jī)制，算法等等東西。。。。。記不太清了。。。2007年百度校園招聘會筆試題1選錯的基類public成員在派生類中仍是public基類protected成員在派生類中仍是protected基類private成員在派生類中是隱藏回去想的，我忘了錯的怎么說的來著2邊長為n的正方形可以分成多個邊長為1的正方形，如邊長為2的正方形有2×2個邊長為1的正方形和1個邊長為2的正方形；問邊長為5的正方形有幾個正方形；3publicclassPerson{publicvoidprintValue(inti,intj){"111111111111}publicvoidprintValue(inti){"22222222222}}publicclassTeacherextendsPerson{publicvoidprintValue(){System.out.println("333333333");}publicvoidprintValue(inti){"4444444444}publicstaticvoidmain(String[]args){Persont=newTeacher();t.printValue(10);}}輸出結(jié)果是：44444444444.找錯誤inttolower(constchar*str){if(NULL==str)

return0;inti=0,iCount=0;for(;i<strlen(str);i){if(str[i]<='Z'||str[i]>='A'){str[i]='z'-'Z';iCount;}}一、選擇題：15分共10題1.一個含有n個頂點(diǎn)和e條邊的簡單無向圖，在其鄰接矩陣存儲結(jié)構(gòu)中共有____個零元素。A．e

B．2e

C．n2-e

D．n2-2e2.____是面向?qū)ο蟪绦蛟O(shè)計語言中的一種機(jī)制。這種機(jī)制實(shí)現(xiàn)了方法的定義與具體的對象無關(guān)，而對方法的調(diào)用則可以關(guān)聯(lián)于具體的對象。A．繼承（Inhertance）B．模板（Template）C．對象的自身引用（Self-Reference）D．動態(tài)綁定（DynamicBinding）3.應(yīng)用層DNS協(xié)議主要用于實(shí)現(xiàn)網(wǎng)絡(luò)服務(wù)功能.A.IP地址到網(wǎng)絡(luò)設(shè)備名字的映射B.IP地址到網(wǎng)絡(luò)硬件地址的映射C.網(wǎng)絡(luò)設(shè)備名字到IP地址的映射D.網(wǎng)絡(luò)硬件地址到IP地址的映射4.linux默認(rèn)情況下，一個進(jìn)程最多能打開多少文件？A.64B.128C.512D.10245.下面結(jié)構(gòu)體structs1{charch,*ptr;union{shorta,b;unsignedintc:2,d:1;}structs1*next;};的大小是_____：A.12字節(jié)B.16字節(jié)C.20字節(jié)D.24字節(jié)6.任何一個基于"比較"的內(nèi)部排序的算法，若對6個元素進(jìn)行排序，則在最壞情況下所需的比較次數(shù)至少為____。A．10B．11C．21D．367.以下不是進(jìn)程間通訊的是___A共享內(nèi)存B信號量C線程局部存儲D消息隊列8.下面程序，求count的值intfunc(x){intcount=0;x=9999;while(x){Count;x=x&(x-1);}returncount;}A8；B10；C5；D119.使用malloc系統(tǒng)調(diào)用分配的內(nèi)存是在____上分配的？A棧；Bbss；C物理內(nèi)存；D堆10.最壞情況下，合并兩個大小為n的已排序數(shù)組所需要的比較次數(shù)_____A.2nB.2n-1C.2n1D.2n-2二、簡答題：20分，共3題1.（5分）下面這段代碼是把中英文混合字符串(漢字用兩個字節(jié)表示，特點(diǎn)是第一個字節(jié)的最高位為1)中的大寫字母轉(zhuǎn)化為小寫字母，請找出其中的bug，注意各種異常情況。for(char*piterator=szWord;*piterator!=0;piterator){if(*piterator&0x80!=0){piterator;}elseif(*piterator>='A'&&*piterator<='Z')piterator=32;}2.（5分）對給定的上億條無序的url，請按照domain、site以及path分別排序，并請指出排序過程中可能會遇到的哪些問題？如何提高效率？例如：，domain、site以及path的定義分別如下：Domain:Site:Path:/path3.（10分）某型CPU的一級數(shù)據(jù)緩存大小為16K字節(jié)，cache塊大小為64字節(jié)；二級緩存大小為256K字節(jié)，cache塊大小為4K字節(jié)，采用二路組相聯(lián)。經(jīng)測試，下面兩段代碼運(yùn)行時效率差別很大，請分析哪段代碼更好，以及可能的原因。為了進(jìn)一步提高效率，你還可以采取什么辦法？A段代碼intmatrix[1023][15];constchar*str="thisisastr";inti,j,tmp,sum=0;tmp=strlen(str);for(i=0;i<1023;i){for(j=0;j<15;j){sum=matrix[j]tmp;}}B段代碼intmatrix[1025][17];constchar*str="thisisastr";inti,j,sum=0;for(i=0;i<17;i){for(j=0;j<1025;j){sum=matrix[j]strlen(str);}}三、編程題：30分共1題注意：要求盡可能提供完整代碼，如果可以編譯運(yùn)行酌情加分。1.內(nèi)存中有一個長數(shù)組，條目數(shù)為10萬，數(shù)組單元為結(jié)構(gòu)體structarray，sizeof(structarray)為512字節(jié)。結(jié)構(gòu)有一int型成員變量weight?，F(xiàn)需要取得按weig