試題

百度試題

1編程：

用C語言實(shí)現(xiàn)一個(gè)revert函數(shù)，它的功能是將輸入的字符串在原串上倒序后返回。

2編程：

用C語言實(shí)現(xiàn)函數(shù)void*memmove(void*dest,constvoid*src,size_tn)。memmove

函數(shù)的功能是拷貝src所指的內(nèi)存內(nèi)容前n個(gè)字節(jié)到dest所指的地址上。

3英文拼寫糾錯(cuò)：

在用戶輸入英文單詞時(shí)，經(jīng)常發(fā)生錯(cuò)誤，我們需要對(duì)其進(jìn)行糾錯(cuò)。假設(shè)已經(jīng)有一個(gè)包含

了正確英文單詞的詞典，請(qǐng)你設(shè)計(jì)一個(gè)拼寫糾錯(cuò)的程序。

（1）請(qǐng)描述你解決這個(gè)問題的思路；

（2）請(qǐng)給出主要的處理流程，算法，以及算法的復(fù)雜度；

（3）請(qǐng)描述可能的改進(jìn)（改進(jìn)的方向如效果，性能等等，這是一個(gè)開放問題）。

4尋找熱門查詢：

搜索引擎會(huì)通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個(gè)查詢串的

長度為1-255字節(jié)。假設(shè)目前有一千萬個(gè)記錄，這些查詢串的重復(fù)度比較高，雖然總數(shù)是1

千萬，但如果除去重復(fù)后，不超過3百萬個(gè)。一個(gè)查詢串的重復(fù)度越高，說明查詢它的用

戶越多，也就是越熱門。請(qǐng)你統(tǒng)計(jì)最熱門的10個(gè)查詢串，要求使用的內(nèi)存不能超過1G。

（1）請(qǐng)描述你解決這個(gè)問題的思路；

（2）請(qǐng)給出主要的處理流程，算法，以及算法的復(fù)雜度。

5集合合并：

給定一個(gè)字符串的集合，格式如：{aaabbbccc}，{bbbddd}，{eeefff}，{ggg}，{ddd

hhh}要求將其中交集不為空的集合合并，要求合并完成后的集合之間無交集，例如上例應(yīng)

輸出{aaabbbcccdddhhh}，{eeefff}，{ggg}

（1）請(qǐng)描述你解決這個(gè)問題的思路；

（2）請(qǐng)給出主要的處理流程，算法，以及算法的復(fù)雜度

（3）請(qǐng)描述可能的改進(jìn)（改進(jìn)的方向如效果，性能等等，這是一個(gè)開放問題）。

////////////////////////////////

1題

char*revert(char*str)

{

intn=strlen(str);

inti=0;

charc;

for(i=0;i{

c=str;

str=str[n-i];

str[n-i]=c;

}

returnstr;

}

///////////////////////////////////

2題

void*memmove(void*dest,constvoid*src,size_tn)

{

asrt((dest!=0)&&(src!=0));

char*temp=(char*)dest;

char*ss=(char*)src;

inti=0;

for(;i{

*temp=*ss;

}

returntemp;

}

/////////////////////////////////////////////////

3題

(1)思路:字典以字母鍵樹組織，在用戶輸入同時(shí)匹配

(2)流程:

每輸入一個(gè)字母：

沿字典樹向下一層，

a）若可以順利下行，則繼續(xù)至結(jié)束，給出結(jié)果；

b)若該處不能匹配，糾錯(cuò)處理，給出拼寫建議,繼續(xù)至a）；

算法:

1.在字典中查找單詞

字典采用27叉樹組織,每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)字母,查找就是一個(gè)字母

一個(gè)字母匹配.算法時(shí)間就是單詞的長度k.

2.糾錯(cuò)算法

情況:當(dāng)輸入的最后一個(gè)字母不能匹配時(shí)就提示出錯(cuò),簡化出錯(cuò)處理，動(dòng)態(tài)提示可能處理方

法:

(a)當(dāng)前字母前缺少了一個(gè)字母：搜索樹上兩層到當(dāng)前的匹配作為建議；

(b)當(dāng)前字母拼寫錯(cuò)誤：當(dāng)前字母的鍵盤相鄰作為提示；（只是簡單的描述，可以有更多的）

根據(jù)分析字典特征和用戶單詞已輸入部分選擇(a),(b)處理

復(fù)雜性分析：影響算法的效率主要是字典的實(shí)現(xiàn)與糾錯(cuò)處理

(a）字典的實(shí)現(xiàn)已有成熟的算法，改進(jìn)不大，也不會(huì)成為瓶頸；

(b)糾錯(cuò)策略要簡單有效,如前述情況，是線性復(fù)雜度；

(3)改進(jìn)

策略選擇最是重要，可以采用統(tǒng)計(jì)學(xué)習(xí)的方法改進(jìn)。

//////////////////////////////////////////////

4題

(1)思路：用哈希做

(2)首先逐次讀入查詢串，算哈希值，保存在內(nèi)存數(shù)組中，同時(shí)統(tǒng)計(jì)頻度（注意值與日志項(xiàng)

對(duì)應(yīng)關(guān)系）選出前十的頻度，取出對(duì)應(yīng)的日志串，簡單不過了。哈希

的設(shè)計(jì)是關(guān)鍵。

//////////////////////////////////////////////////

5題

（1）思路：先將集合按照大小排列后,優(yōu)先考慮小的集合是否與大的集合有交集。有就合并，

如果小集合與所有其他集合都沒有交集，則獨(dú)立。獨(dú)立的集合在下一輪的比較中不用考慮。

這樣就可以盡量減少字符串的比較次數(shù)。當(dāng)所有集合都獨(dú)立的時(shí)候，就終止。

（2）處理流程：

1.將集合按照大小排序，組成集合合并待處理列表

2.選擇最小的集合，找出與之有交集的集合，如果有，合并之；如果無，則與其它集合是獨(dú)

立集合，從待處理列表中刪除。

3.重復(fù)直到待處理列表為空

算法：1。將集合按照大小從小到大排序,組成待處理的集合列表。2。取出待處理集合列

表中最小的集合，對(duì)于集合的每個(gè)元素，依次在其他集合中搜索是否有此元素存在：

1>若存在，則將此小集合與大集合合并，并根據(jù)大小插入對(duì)應(yīng)的位置。轉(zhuǎn)3。

2>若不存在，則在該集合中取下一個(gè)元素。如果無下一個(gè)元素，即所有元素都不存在于其

他集合。則表明此集合獨(dú)立，從待處理集合列表中刪除。并加入結(jié)果集合列表。轉(zhuǎn)3。

3。如果待處理集合列表不為空，轉(zhuǎn)2。

如果待處理集合列表為空，成功退出，則結(jié)果集合列表就是最終的輸出。

算法復(fù)雜度分析：

假設(shè)集合的個(gè)數(shù)為n，最大的集合元素為m排序的時(shí)間復(fù)雜度可以達(dá)到n*log(n)然后

對(duì)于元素在其他集合中查找，最壞情況下為（n-1）*m查找一個(gè)集合是否與其他集合有交

集的最壞情況是m*m*(n-1)合并的時(shí)間復(fù)雜度不會(huì)超過查找集合有交集的最壞情況。所以

最終最壞時(shí)間復(fù)雜度為O(m*m*n*n)

需要說明的是：此算法的平均時(shí)間復(fù)雜度會(huì)很低，因?yàn)闊o論是查找還是合并，都是處于

最壞情況的概率很小，而且排序后優(yōu)先用最小集合作為判斷是否獨(dú)立的對(duì)象，優(yōu)先與最大的

集合進(jìn)行比較，這些都最大的回避了最壞情況。

(3)可能的改進(jìn)：

首先可以實(shí)現(xiàn)將每個(gè)集合里面的字符串按照字典序進(jìn)行排列，這樣就可以將查找以及合

并的效率增高。另外，可能采取恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)也可以將查找以及合并等操作的效率得到提

高。

、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、

1）此題10分

對(duì)任意輸入的正整數(shù)N，編寫C程序求N!的尾部連續(xù)0的個(gè)數(shù)，并指出計(jì)算復(fù)雜度。

如：18！＝6400，尾部連續(xù)0的個(gè)數(shù)是3。（不用考慮數(shù)值超出計(jì)算

機(jī)整數(shù)界限的問題）

2）此題10分編寫一個(gè)C語言函數(shù)，要求輸入一個(gè)url，輸出該url是首頁、目錄頁或

者其他url

如下形式叫做首頁：

/

/

/

/

/

如下形式叫做目錄頁：

/greenhous--gas-global-green-hou-warming/

/ur/tgk5ar1r/profile/

/food/yszt/chunjie/

/Reality/

請(qǐng)注意：

a）url有可能帶http頭也有可能不帶

b）動(dòng)態(tài)url（即含有"？"的url）的一律不算目錄頁，如：

/utility/?l=/activity/details/3135/

/utility/?l=/activity/details/2449/

另：如果你會(huì)linux，請(qǐng)用linux下的grep命令實(shí)現(xiàn)第2題的功能（附加5分）。

3）此題40分

如果必須從網(wǎng)頁中區(qū)分出一部分"重要網(wǎng)頁"（例如在10億中選8億），比其他網(wǎng)頁更值

得展現(xiàn)給用戶，請(qǐng)?zhí)岢鲆环N方案。

4）此題40分

假設(shè)有10億網(wǎng)頁已經(jīng)被我們存下來，并提供如下信息：網(wǎng)頁全文（即網(wǎng)頁的源碼）、

全文長度、網(wǎng)頁正文（即網(wǎng)頁中提取的主體文字）、正文長度，以及其他網(wǎng)頁提取物等，現(xiàn)

在希望去掉其中的重復(fù)網(wǎng)頁，請(qǐng)?zhí)岢隹尚械姆桨福?jì)算出每個(gè)網(wǎng)頁對(duì)應(yīng)的重復(fù)度，你可以自

己對(duì)網(wǎng)頁重復(fù)下定義，也可以提出需要哪些更多的網(wǎng)頁提取物來實(shí)現(xiàn)更好的去重復(fù)方案。

、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、

好久沒來了。

發(fā)生了一些事情，其間的心情已不是幾行文字所能表述的了。

終于明白有些事情，并不是自己努力就一定能圓滿的；有些事情，是我控制不了的。

唉，不提也罷！

說說今天去百度筆試的經(jīng)歷吧

部門：百度搜索應(yīng)用技術(shù)部。

地點(diǎn)：海淀南路銀科大廈（海淀圖書城西臨）18層。

時(shí)間：2005/6/1510：00-11：20am

九點(diǎn)從實(shí)驗(yàn)室出發(fā)，725到知春路，轉(zhuǎn)735，到海淀橋下車，9：50到達(dá)百度。在725

的車上碰到一男士索要手機(jī)號(hào)，說自己認(rèn)識(shí)信息產(chǎn)業(yè)部的部長楊澤民先生，以居高臨下的姿

態(tài)把手機(jī)號(hào)給了他-__-!

在百度前臺(tái)見到了一直幫我安排筆試的楊韞敏jj，不是想象中的HR形象，而是一副干

練的女IT的樣子跳躍的靈魂很快，給我找了一間小會(huì)議室，只有一張桌子，兩把椅子，還

幫我開了燈，關(guān)門，走人，我開始看題。冷汗也開始流。翻了一下三頁紙的筆試題，只有很

少的傳說中的Linux題目，其他的全是C、數(shù)據(jù)結(jié)構(gòu)、算法編程的題。第一反應(yīng)：走人！但

又覺得對(duì)不起陳jj，關(guān)鍵的是我已經(jīng)在筆試題上寫了姓名和學(xué)校了，sign，總的為自己的名

字和學(xué)校負(fù)責(zé)吧，他們是無辜的。如此斗爭良久，決定堅(jiān)持下來。

題目大致是這樣的：

第一部分選擇題：有幾道網(wǎng)絡(luò)相關(guān)的題目，巨簡單，比如第一題是TCP、RIP、IP、FTP

中哪個(gè)協(xié)議是傳輸層的......。有一道linux的chown使用題目。其他的全是數(shù)據(jù)結(jié)構(gòu)的題目！

什么鏈，表，碼的，不知所云跳躍的靈魂唉，我可以沒有學(xué)過數(shù)據(jù)結(jié)構(gòu)的人吶！真殘忍！這

一部分迅速猜完！

第二部分簡答題：

1、在linux中如何編譯C程序，使之成為可執(zhí)行文件？如何調(diào)試？

答案：

1)檢查程序中.h文件所在的目錄，將其加入系統(tǒng)PATH中；

2)執(zhí)行C編譯：#gcc[源文件名]-o[目標(biāo)文件名]

執(zhí)行C++編譯：#g++[源文件名]-o[目標(biāo)文件名]

3)改變目標(biāo)文件為可執(zhí)行文件：#chmod+x[目標(biāo)文件名]

4)如需將多個(gè)可執(zhí)行文件連續(xù)執(zhí)行，可生成批處理文件：

#vi[批處理文件名]

可執(zhí)行文件1

可執(zhí)行文件2

.........

最后將該批處理文件屬性該位可執(zhí)行。

調(diào)試：在編譯時(shí)使用-g參數(shù)，就可以使用gdb進(jìn)行調(diào)試。

2、寫出內(nèi)存分配和釋放的函數(shù)，并指出區(qū)別。

答案：

C語言的標(biāo)準(zhǔn)內(nèi)存分配函數(shù)：malloc，calloc，realloc，free等。

malloc與calloc的區(qū)別為1塊與n塊的區(qū)別：

malloc調(diào)用形式為(類型*)malloc(size)：在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)中分配一塊長度為

“size”字節(jié)的連續(xù)區(qū)域，返回該區(qū)域的首地址。

calloc調(diào)用形式為(類型*)calloc(n，size)：在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)中分配n塊長度為

“size”字節(jié)的連續(xù)區(qū)域，返回首地址。

realloc調(diào)用形式為(類型*)realloc(*ptr，size)：將ptr內(nèi)存大小增大到size。

free的調(diào)用形式為free(void*ptr)：釋放ptr所指向的一塊內(nèi)存空間。

C++中為new/delete函數(shù)。

3、寫出socket函數(shù)，并指出其功能。

socket():建立socket通信描述符；

bind()：將套接字和機(jī)器上的一定的端口關(guān)聯(lián)；

connect()：連接到遠(yuǎn)程主機(jī)；

listen()：使套接字做好連接的準(zhǔn)備，規(guī)定等待服務(wù)請(qǐng)求隊(duì)列的長度；

accept()：接受連接，一旦有客戶端發(fā)出連接，accept返回客戶地址信息和一個(gè)新的

sock；

有了這個(gè)新的sock，雙方就可以開始收發(fā)數(shù)據(jù)：

nd()和recv()：用于流式套接字或者數(shù)據(jù)套接字的通訊；

ndto()和recvfrom()：用于無連接的數(shù)據(jù)報(bào)套接字；

clo()：關(guān)閉套接字；

shutdown()：選擇性的關(guān)閉套接字，可以只允許某一方向的通訊關(guān)閉；

getpeername()：返回流式套接字時(shí)對(duì)端peer信息；

gethostname()：返回程序所運(yùn)行的機(jī)器的主機(jī)名字；

gethostbyname()：返回本機(jī)IP；

第三部分編程題：

1、從文件中讀取字符串?dāng)?shù)據(jù)，反序顯示并大小寫轉(zhuǎn)換。

2、給定26字母表以及對(duì)應(yīng)的密碼表，編程實(shí)現(xiàn)加密及解密功能。

第四部分思考題(正是傳說中的字典糾錯(cuò)題)：

用戶在輸入英文單詞時(shí)經(jīng)常出錯(cuò)，現(xiàn)對(duì)其進(jìn)行就錯(cuò)。給定一個(gè)正確的英文詞典，考慮糾

錯(cuò)實(shí)現(xiàn)。1)指出思路。2)流程、算法難易程度及可能的改進(jìn)策略。

不過陳jj沒有給我答題紙，只好拿試題的背面做了答題紙兼草稿紙-___-!說實(shí)話有些題

目是很基礎(chǔ)的，就是沒背過。不知怎么搞得，巨潦草。實(shí)驗(yàn)室參加過筆試的通同學(xué)都是憋著

勁做了兩個(gè)多小時(shí)才答完，而我只一個(gè)小時(shí)就完了，唉，正好說明肚子里只有別人一半的東

西~~看著潦草而不著邊際的答題，決定在最后給陳jj寫段話，大意就是感謝她幫我挽回了

一次筆試的機(jī)會(huì)，但我的表現(xiàn)很遺憾等等......然后交卷走人~~

沒想到交了試卷沒讓我走，等了大約30分鐘的樣子，有個(gè)很深沉的gg來看我的卷子

跳躍的靈魂-___-!我顫顫的跟他說我很長時(shí)間沒有接觸C了，當(dāng)時(shí)脖子都紅了，真覺得丟人。

gg看了一下，沒有很鄙視的樣子，問我有沒有帶簡歷。當(dāng)然木有啦~~答應(yīng)回來給他發(fā)個(gè)電

子版的，然后趕緊跑人了！

、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、

題目大致是這樣的：

第一部分選擇題：

有幾道網(wǎng)絡(luò)相關(guān)的題目，巨簡單，比如第一題是TCP、RIP、IP、FTP中哪個(gè)協(xié)議是傳

輸層的......。有一道linux的chown使用題目。其他的全是數(shù)據(jù)結(jié)構(gòu)的題目！什么鏈，表，

碼的，不知所云．唉，我可以沒有學(xué)過數(shù)據(jù)結(jié)構(gòu)的人吶！真殘忍！這一部分迅速猜完！

第二部分簡答題：

1、在linux中如何編譯C程序，使之成為可執(zhí)行文件？如何調(diào)試？

答案：1)檢查程序中.h文件所在的目錄，將其加入系統(tǒng)PATH中；

2)執(zhí)行C編譯：#gcc[源文件名]-o[目標(biāo)文件名]

執(zhí)行C++編譯：#g++[源文件名]-o[目標(biāo)文件名]

3)改變目標(biāo)文件為可執(zhí)行文件：#chmod+x[目標(biāo)文件名]

4)如需將多個(gè)可執(zhí)行文件連續(xù)執(zhí)行，可生成批處理文件：

#vi[批處理文件名]

可執(zhí)行文件1

可執(zhí)行文件2

.........

最后將該批處理文件屬性該位可執(zhí)行。

調(diào)試：在編譯時(shí)使用-g參數(shù)，就可以使用gdb進(jìn)行調(diào)試。

2、寫出內(nèi)存分配和釋放的函數(shù)，并指出區(qū)別。

答案：

C語言的標(biāo)準(zhǔn)內(nèi)存分配函數(shù)：malloc，calloc，realloc，free等。

malloc與calloc的區(qū)別為1塊與n塊的區(qū)別：

malloc調(diào)用形式為(類型*)malloc(size)：在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)中分配一塊長度為

“size”字節(jié)的連續(xù)區(qū)域，返回該區(qū)域的首地址。

calloc調(diào)用形式為(類型*)calloc(n，size)：在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)中分配n塊長度為

“size”字節(jié)的連續(xù)區(qū)域，返回首地址。

realloc調(diào)用形式為(類型*)realloc(*ptr，size)：將ptr內(nèi)存大小增大到size。

free的調(diào)用形式為free(void*ptr)：釋放ptr所指向的一塊內(nèi)存空間。

C++中為new/delete函數(shù)。

3、寫出socket函數(shù)，并指出其功能。

socket():建立socket通信描述符；

bind()：將套接字和機(jī)器上的一定的端口關(guān)聯(lián)；

connect()：連接到遠(yuǎn)程主機(jī)；

listen()：使套接字做好連接的準(zhǔn)備，規(guī)定等待服務(wù)請(qǐng)求隊(duì)列的長度；

accept()：接受連接，一旦有客戶端發(fā)出連接，accept返回客戶地址信息和一個(gè)新的

sock；

有了這個(gè)新的sock，雙方就可以開始收發(fā)數(shù)據(jù)：

nd()和recv()：用于流式套接字或者數(shù)據(jù)套接字的通訊；

ndto()和recvfrom()：用于無連接的數(shù)據(jù)報(bào)套接字；

clo()：關(guān)閉套接字；

shutdown()：選擇性的關(guān)閉套接字，可以只允許某一方向的通訊關(guān)閉；

getpeername()：返回流式套接字時(shí)對(duì)端peer信息；

gethostname()：返回程序所運(yùn)行的機(jī)器的主機(jī)名字；

gethostbyname()：返回本機(jī)IP；

第三部分編程題：

1、從文件中讀取字符串?dāng)?shù)據(jù)，反序顯示并大小寫轉(zhuǎn)換。

2、給定26字母表以及對(duì)應(yīng)的密碼表，編程實(shí)現(xiàn)加密及解密功能。

第四部分思考題(正是傳說中的字典糾錯(cuò)題)：

用戶在輸入英文單詞時(shí)經(jīng)常出錯(cuò)，現(xiàn)對(duì)其進(jìn)行就錯(cuò)。給定一個(gè)正確的英文詞典，考慮糾

錯(cuò)實(shí)現(xiàn)。1)指出思路。2)流程、算法難易程度及可能的改進(jìn)策略。

一道算法題目答案

intReplace(Stringtype&S,StringtypeT,StringtypeV);//將串S中所有子串T替換為V,并返

回置換次數(shù)

{

for(n=0,i=1;i〈=Strlen(S)-Strlen(T)+1;i++)//注意i的取值范圍

if(!StrCompare(SubString(S,i,Strlen(T)),T))//找到了與T匹配的子串

{//分別把T的前面和后面部分保存為head和tail

StrAssign(head,SubString(S,1,i-1));

StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1));

StrAssign(S,Concat(head,V));

StrAssign(S,Concat(S,tail));//把head,V,tail連接為新串

i+=Strlen(V);//當(dāng)前指針跳到插入串以后

n++;

}//if

returnn;

}//Replace

分析:i+=Strlen(V);這一句是必需的,也是容易忽略的.如省掉這一句,則在某些情況下,會(huì)引起

不希望的后果,雖然在大多數(shù)情況下沒有影響.請(qǐng)思考:設(shè)S='place',T='ace',V='face',則省掉

i+=Strlen(V);運(yùn)行時(shí)會(huì)出現(xiàn)什么結(jié)果?（無限遞歸face）

百度2005年的筆試題

1.實(shí)現(xiàn)voiddelete_char(char*str,charch);

把str中所有的ch刪掉

2.把字符串S中所有A子串換成B,這個(gè)沒給函數(shù)原型

3.搜索引擎的日志要記錄所有查詢串,有一千萬條查詢,不重復(fù)的不超過三百萬

要統(tǒng)計(jì)最熱門的10條查詢串.內(nèi)存<1G.字符串長0-255

(1)主要解決思路//具體用詞和原題不大一樣

(2)算法及其復(fù)雜度分析

4.有字典,設(shè)計(jì)一個(gè)英文拼寫糾正算法(1)思想(2)算法及復(fù)雜度(3)改進(jìn)

5.{aaa,bb,ccc,dd},{bbb,ff},{gg}等一些字符串的集合

要求把交集不為空的集合并起來,如上例會(huì)得到{aaa,bb,ccc,dd,ff},{gg}

(1)思想(2)算法及復(fù)雜度(3)改進(jìn)

、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、

一、選擇題：15分共10題

1.一個(gè)含有n個(gè)頂點(diǎn)和e條邊的簡單無向圖，在其鄰接矩陣存儲(chǔ)結(jié)構(gòu)中共有____個(gè)零元素。

A．eB．2eC．n2-eD．n2-2e

2.____是面向?qū)ο蟪绦蛟O(shè)計(jì)語言中的一種機(jī)制。這種機(jī)制實(shí)現(xiàn)了方法的定義與具體的對(duì)象

無關(guān)，而對(duì)方法的調(diào)用則可以關(guān)聯(lián)于具體的對(duì)象。

A．繼承（Inhertance）B．模板（Template）

C．對(duì)象的自身引用（Self-Reference）D．動(dòng)態(tài)綁定（DynamicBinding）

3.應(yīng)用層DNS協(xié)議主要用于實(shí)現(xiàn)網(wǎng)絡(luò)服務(wù)功能.

地址到網(wǎng)絡(luò)設(shè)備名字的映射地址到網(wǎng)絡(luò)硬件地址的映射

C.網(wǎng)絡(luò)設(shè)備名字到IP地址的映射D.網(wǎng)絡(luò)硬件地址到IP地址的映射

默認(rèn)情況下，一個(gè)進(jìn)程最多能打開多少文件？

A.64B.128C.512D.1024

5.下面結(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.任何一個(gè)基于"比較"的內(nèi)部排序的算法，若對(duì)6個(gè)元素進(jìn)行排序，則在最壞情況下所需的

比較次數(shù)至少為____。

A．10B．11C．21D．36

7.以下不是進(jìn)程間通訊的是___

A共享內(nèi)存B信號(hào)量C線程局部存儲(chǔ)D消息隊(duì)列

8.下面程序，求count的值

intfunc(x)

{

intcount=0;

x=9999;

while(x)

{

Count++;

x=x&(x-1);

}

returncount;

}

A8；B10；C5；D11

9.使用malloc系統(tǒng)調(diào)用分配的內(nèi)存是在____上分配的？

A棧；Bbss；C物理內(nèi)存；D堆

10.最壞情況下，合并兩個(gè)大小為n的已排序數(shù)組所需要的比較次數(shù)_____

A.2nB.2n-1C.2n+1D.2n-2

二、簡答題：20分，共3題

1.（5分）下面這段代碼是把中英文混合字符串(漢字用兩個(gè)字節(jié)表示，特點(diǎn)是第一個(gè)字節(jié)的

最高位為1)中的大寫字母轉(zhuǎn)化為小寫字母，請(qǐng)找出其中的bug，注意各種異常情況。

for(char*piterator=szWord;*piterator!=0;piterator++)

{

if(*piterator&0x80!=0)

{

piterator++;

}

elif(*piterator>='A'&&*piterator<='Z')

piterator+=32;

}

2.（5分）對(duì)給定的上億條無序的url，請(qǐng)按照domain、site以及path分別排序，并請(qǐng)指出

排序過程中可能會(huì)遇到的哪些問題？如何提高效率？

例如：/path/，domain、site以及path的定義分別如下：

Domain:

Site:

Path:/path

3.（10分）某型CPU的一級(jí)數(shù)據(jù)緩存大小為16K字節(jié)，cache塊大小為64字節(jié)；二級(jí)緩

存大小為256K字節(jié)，cache塊大小為4K字節(jié)，采用二路組相聯(lián)。經(jīng)測試，下面兩段代碼

運(yùn)行時(shí)效率差別很大，請(qǐng)分析哪段代碼更好，以及可能的原因。

為了進(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[i][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][i]+strlen(str);

}

}

三、編程題：30分共1題

注意：要求盡可能提供完整代碼，如果可以編譯運(yùn)行酌情加分。

1.內(nèi)存中有一個(gè)長數(shù)組，條目數(shù)為10萬，數(shù)組單元為結(jié)構(gòu)體structarray，sizeof(structarray)

為512字節(jié)。結(jié)構(gòu)有一int型成員變量weight。現(xiàn)需要取得按weight值從大到小排序的前

500個(gè)數(shù)組單元，請(qǐng)實(shí)現(xiàn)算法，要求效率盡可能高。

四、設(shè)計(jì)題：35分共1題

注意：請(qǐng)盡可能詳細(xì)描述你的數(shù)據(jù)結(jié)構(gòu)、系統(tǒng)架構(gòu)、設(shè)計(jì)思路等，建議多寫一些偽代碼或者

流程說明。

1.請(qǐng)?jiān)O(shè)計(jì)一個(gè)字典。以字符串為索引，存儲(chǔ)用戶定義的定長結(jié)構(gòu)。要求有增、刪、查、改的

功能。已經(jīng)給定一個(gè)函數(shù)，可以由字符串映射到一個(gè)簽名，每個(gè)簽名由兩個(gè)unsignedint

類型組成。假設(shè)每一個(gè)字符串能夠?qū)?yīng)唯一的一個(gè)簽名，完全沒有重復(fù)（或者重復(fù)的概率可

以忽略），并且簽名分布足夠均勻。

請(qǐng)描述你的數(shù)據(jù)結(jié)構(gòu)？內(nèi)存如何申請(qǐng)？增、刪、查、改的功能如何實(shí)現(xiàn)？如果操作很頻繁，

該如何優(yōu)化？

、、、、、、、、、、、、、、、、、、、、、、、、、、

經(jīng)過在線筆試、兩輪電話面試，今天上午收到了百度的拒信，我的百度求職算是告一段落

了……

從百度校園招聘開始，我就投了一份簡歷。在別人都有在線筆試機(jī)會(huì)的時(shí)候，我卻沒有

任何消息。

聽說師兄可以給推薦，我就又通過內(nèi)部推薦的方式投遞了一次，這次很快就有消息了

——拒信。

那時(shí)基本上就放棄了百度。可是大概20多天以后，我投遞的第一份簡歷有消息了——

通知我在線筆試。經(jīng)過精心準(zhǔn)備，筆試題答得還湊合。過了幾天給我來了封郵件告知我筆試

通過，會(huì)找時(shí)間安排電話面試。又過了好幾天，我正在剃頭的時(shí)候接到百度電話，約了第二

天下午三點(diǎn)電話面試。心情異常興奮，回到寢室拼命復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)并收集百度面試題型……

臨陣磨槍呵呵。

百度的面試氛圍很是輕松，讓你很快就覺得是在聊天而不是面試。第一輪主要是在針對(duì)

我的在線筆試的題目進(jìn)行提問和分析，主要講的是做題的思路和改進(jìn)的方法。面試時(shí)間大概

有半個(gè)小時(shí)，覺得應(yīng)該有下一輪。

果然上個(gè)星期五晚上接到了百度技術(shù)經(jīng)理的電話，自稱姓劉。在前一天我同學(xué)也是這個(gè)

時(shí)候接到百度第二面電話，看來是同一個(gè)人，后來的面試內(nèi)容證實(shí)了是同一個(gè)人。面試過程

大概如下：

1、介紹一下項(xiàng)目。

2、提了一個(gè)問題：上千萬條記錄，統(tǒng)計(jì)出重復(fù)記錄最多的前N條。

3、一個(gè)概率題：54張撲克牌，除去兩張大小王剩下52張撲克牌。問紅桃A和黑桃A同時(shí)

被一個(gè)人拿到的概率是多少？

4、多個(gè)線程訪問共享內(nèi)存時(shí)因該怎么辦？

5、在寫程序遇到問題的時(shí)候，通常采用什么調(diào)試方法？

6、一個(gè)client/rver的協(xié)議問題

7、剩下就是隨便聊聊，比如有缺點(diǎn)、期望工作的性質(zhì)、職業(yè)規(guī)劃等

總結(jié)一下教訓(xùn)：

1、介紹項(xiàng)目的時(shí)候不能一味的按照事前想好的模板說，應(yīng)該根據(jù)所申請(qǐng)的工作的性質(zhì)，多

說一些和自己申請(qǐng)的工作內(nèi)內(nèi)容相近的東西說。我在介紹我的項(xiàng)目的時(shí)候，說了很多硬件的

東西，而相關(guān)的Linux下的C編程卻沒有提到多少，一大失敗之處。

2、對(duì)于他提的第二個(gè)問題，當(dāng)時(shí)因?yàn)榫o張沒有想出來，掛了電話以后才有了思路。

3、這個(gè)概率題以前碰到過，而且和同學(xué)們討論過，答案很早就知道了。但是遇到面試的時(shí)

候，不能馬上就說出答案，因?yàn)檫@樣擺明了高訴人家你以前就見過這道題，這樣就失去了作

為考題的意義。所以，如果事前知道答案也不要馬上說出來，裝作考慮中，然后慢慢說出答

案。我就是很快就說出了答案，失敗！

4、在問項(xiàng)目的時(shí)候，他問我代碼行大概有多少？我說大概有5.6K行左右。在回答第四個(gè)

問題的時(shí)候，我?guī)缀跏菍纤v過的東西背了一遍給他，雖然答案是正確的，但是我估計(jì)

他一聽就聽出來是在背書了，所以這也會(huì)減分不少。，而且百度強(qiáng)調(diào)創(chuàng)新，其實(shí)就算你不知

道答案也可以按照自己的思路說一下的，只要邏輯清晰、合理都會(huì)比我背書強(qiáng)……

5、我的回答是有時(shí)候用gdb，有時(shí)候用輸出日志的形式。以我之前給他講的項(xiàng)目經(jīng)驗(yàn)是不

大可能會(huì)涉及這么多的知識(shí)的，所以估計(jì)他又聽出我是在背書了……繼續(xù)減分

6、后來我發(fā)現(xiàn)這個(gè)問題其實(shí)他不是在考我問題的答案，是考我解決問題的能力和考慮問題

的思路。這點(diǎn)是我比較差的地方，沒辦法……減分

我前面表現(xiàn)那么失敗，基本上已經(jīng)沒有什么希望了，后面的談話已經(jīng)沒有意義了，只不過是

禮貌性的結(jié)束這次面試了。

上面的總結(jié)是我收到拒信以后才總結(jié)出來的，還以為能被錄取呢……

面試官太和藹了，而且氣氛及其融洽，根本沒有任何不好的征兆，面試官好厲害！

至此，我的百度求職過程到此告一段落……生活還在繼續(xù)，工作還得繼續(xù)努力去找，加油！

百度電話面試題目：

1.談?wù)勀銓?duì)數(shù)據(jù)庫中索引的理解

2.現(xiàn)在普通關(guān)系數(shù)據(jù)庫用得數(shù)據(jù)結(jié)構(gòu)是什么類型的數(shù)據(jù)結(jié)構(gòu)

3.索引的優(yōu)點(diǎn)和缺點(diǎn)

n和cache的區(qū)別是什么

5.如果有幾千個(gè)ssion，怎么提高效率

n是存儲(chǔ)在什么地方，以什么形式存儲(chǔ)的。