《百度試題及面試》

1編程：

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

序后返回。

2編程：

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

n)0memmove函數(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è)查詢串的長度為『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},{dddhhh)要求將其中交集不為空的集合合并，要求合并完成后的集

合之間無交集，例如上例應(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)

I

intn=strlen(str)；

inti=0；

charc；

for(i=0；i{

c=str；

str=str[n-i]；

str[n-i]=c；

)

returnstr；

}

MMdur

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

2題

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

(

assert((dost!=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),⑹處理

復(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)系)my.chinahrlab.com選出前十的頻度，取出對(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ì)于元素在其他集合中查找，最壞情況下為(nT)*m查找一

個(gè)集合是否與其他集合有交集的最壞情況是m*m*(n-l)合并的時(shí)間復(fù)雜度不

會(huì)超過查找集合有交集的最壞情況。所以最終最壞時(shí)間復(fù)雜度為0(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!=6402373705728000,尾部連續(xù)0的個(gè)數(shù)是3。（不

用考慮數(shù)值超出計(jì)算機(jī)整數(shù)界限的問題）

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

首頁、目錄頁或者其他url

如下形式叫做首頁：

militia,info/

www.apcnc.com.cn/

http：//www.cyjzs.comwww.greena888.com/

www.800cool.net/

http：//hgh-products.my-age.net/

如下形式叫做目錄頁：

thursdaythree.net/greenhouses--gas-g1oba1-green-house-warming/

http：//ww.mw.net.tw/user/tgk5arlr/profile/

http：〃www.szeasy.com/food/yszt/chunjie/

www.fuckingJapanese.com/Reality/

請(qǐng)注意:

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

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

www.buddhismcity,net/utility/mailit.php?l=/activity/details/3135/

www.buddhismcity,net/utility/mailit.php?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í)行文件：ftchmod+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通信描述符；

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

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

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

accept()：接受連接，一旦有客戶端發(fā)出連接，accept返回客戶地址

信息和一個(gè)新的sock；

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

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

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

close()：關(guān)閉套接字;

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

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

gethostname0：返回程序所運(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é)議是傳輸層的.....o有一道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í)行文件：ttchmod+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ī)；

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

accept()：接受連接，一旦有客戶端發(fā)出連接，accept返回客戶地址信

息和一個(gè)新的sock；

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

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

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

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

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

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

gethostnameO：返回程序所運(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=l；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-l))；

StrAssign(tai1,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ù)功能.

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)情況下，一個(gè)進(jìn)程最多能打開多少文件？

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

5.下面結(jié)構(gòu)體

structsi{

charch,*ptr；

union{

shorta,b；

unsignedintc：2,d：1；

)

structsi*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-l)；

}

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_lC.2n+lD.2n-2

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

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

是第一個(gè)字節(jié)的最高位為1)中的大寫字母轉(zhuǎn)化為小寫字母，請(qǐng)找出其中的

bug,注意各種異常情況。

for(char*piteratorszWord；*piterator!=0；piterator++)

if(*piterator&0x80!=0)

piterator++；

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

piterator+=32；

}

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

排序，并請(qǐng)指出排序過程中可能會(huì)遇到的哪些問題？如何提高效率？

例如：http：//\vww.baidu.com/path/about,html,domain,site以及path

的定義分別如下：

Domain：baidu.com

Site：www.baidu.com

Path：www.baidu.com/path

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

節(jié)；二級(jí)緩存大小為256K字節(jié)，cache塊大小為4K字節(jié)，采用二路組相聯(lián)。

經(jīng)測(cè)試，下面兩段代碼運(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+=matrixEj][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í)基本上就放棄了百度?？墒谴蟾?0多天以后，我投遞的第一份簡歷

有消息了一一通知我在線筆試。經(jīng)過精心準(zhǔn)備，筆試題答得還湊合。過了幾

天給我來了封郵件告知我筆試通過，會(huì)找時(shí)間安排電話面試。又過了好幾天,

我正在剃頭的時(shí)候接到百度電話，約了第二天下午三點(diǎn)電話面試。心情異常