（一）
以下這些百度筆試題目由YJBYS整理介紹
1.英文題目的連線題，N個排成方隊的圈，圈里有數(shù)字，外面有突起，請你按數(shù)字要求連線，要求：將這些圈連成整體，每個圈可外接線的數(shù)目要與圈里數(shù)字一致，且線不能相交
2.如果你盯著一張紅色的海報，然后再看白色的墻，那么你看到的墻的外圍是神馬顏色的~（那時，我多么希望這教室里剛好掛著一面國旗~）
選項有：綠色，紅色，紫色，藍色
3.圖形題~
4.有四個箱子，里面分別是 金，銀，銅，鐵，有100個人來猜，這四個箱子里分別是什么，有23個人猜對了0個，58個人猜對了1個，14個人猜對了2個，
求！有幾個人猜對了3個，幾個人猜對了4個（誰會做��！我就Orz）
5.人照鏡子的時候，會覺得左右是相反的，但上下不是相反的，你動左手，就覺得鏡子里是右手在動，你動上牙齒，還是看見上牙齒在動，這是什么原因？寫出你的理解
6.有一種質(zhì)地不均勻的繩子，燒完整根剛好是一個小時，假設(shè)有無數(shù)根這樣的繩子，那么怎樣可以用燒繩子的方法計算出正好1個小時15分鐘~（出考場后，經(jīng)一中科院的牛人點撥，才大徹大悟！只可惜，俺當(dāng)時沒想出來啊~先不告你，你自己看，一會兒再上答案）
7.三個看不見里面的箱子，一個上面寫著“蘋果”一個寫著“橘子”，一個寫著“蘋果&橘子”，已知這三個標(biāo)簽都錯誤，現(xiàn)在請你挑一個箱子拿出一個水果，你能說出這三個箱子里分別是什么么？寫出步驟~
（二）以下是參加考試的人的經(jīng)驗之談
1 編程：
用C語言實現(xiàn)一個revert函數(shù)，它的功能是將輸入的字符串在原串上倒序后返回。
2 編程：
用C語言實現(xiàn)函數(shù)void * memmove(void *dest,const void *src,size_t n)。memmove函數(shù)的功能是拷貝src所指的內(nèi)存內(nèi)容前n個字節(jié)到dest所指的地址上。
3 英文拼寫糾錯：
在用戶輸入英文單詞時，經(jīng)常發(fā)生錯誤，我們需要對其進行糾錯。假設(shè)已經(jīng)有一個包含了正確英文單詞的詞典，請你設(shè)計一個拼寫糾錯的程序。
（1）請描述你解決這個問題的思路；
（2）請給出主要的處理流程，算法，以及算法的復(fù)雜度；
（3）請描述可能的改進（改進的方向如效果，性能等等，這是一個開放問題）。
4 尋找熱門查詢：
搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個查詢串的長度為1-255字節(jié)。假設(shè)目前有一千萬個記錄，這些查詢串的重復(fù)度比較高，雖然總數(shù)是1千萬，但如果除去重復(fù)后，不超過3百萬個。一個查詢串的重復(fù)度越高，說明查詢它的用戶越多，也就是越熱門。請你統(tǒng)計最熱門的10個查詢串，要求使用的內(nèi)存不能超過1G。
（1）請描述你解決這個問題的思路；
（2）請給出主要的處理流程，算法，以及算法的復(fù)雜度。
5 集合合并：
給定一個字符串的集合，格式如： {aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh} 要求將其中交集不為空的集合合并，要求合并完成后的集合之間無交集，例如上例應(yīng)輸出 {aaa bbb ccc ddd hhh}，{eee fff}， {ggg}
（1）請描述你解決這個問題的思路；
（2）請給出主要的處理流程，算法，以及算法的復(fù)雜度
（3）請描述可能的改進（改進的方向如效果，性能等等，這是一個開放問題）。
////////////////////////////////
1 題
char *revert(char * str)
{
int n=strlen(str);
int i=0;
char c;
for(i=0;i {
c=str;
str=str[n-i];
str[n-i]=c;
}
return str;
}
///////////////////////////////////
2 題
void * memmove(void *dest,const void *src,size_t n)
{
assert((dest!=0)&&(src!=0));
char * temp=(char * )dest;
char * ss=(char * )src;
int i=0;
for(;i {
*temp =*ss ;
}
return temp;
}
/////////////////////////////////////////////////
3 題
(1)思路: 字典以字母鍵樹組織，在用戶輸入同時匹配
(2) 流程:
每輸入一個字母：
沿字典樹向下一層，
a）若可以順利下行，則繼續(xù)至結(jié)束，給出結(jié)果；
b)若該處不能匹配，糾錯處理，給出拼寫建議,繼續(xù)至a）；
算法:
1.在字典中查找單詞
字典采用27叉樹組織,每個節(jié)點對應(yīng)一個字母,查找就是一個字母
一個字母匹配.算法時間就是單詞的長度k.
2.糾錯算法
情況:當(dāng)輸入的最后一個字母不能匹配時就提示出錯,簡化出錯處理，動態(tài)提示可能 處理方法:
(a)當(dāng)前字母前缺少了一個字母：搜索樹上兩層到當(dāng)前的匹配作為建議；
(b)當(dāng)前字母拼寫錯誤：當(dāng)前字母的鍵盤相鄰作為提示；（只是簡單的描述，可 以有更多的）
根據(jù)分析字典特征和用戶單詞已輸入部分選擇(a),(b)處理
復(fù)雜性分析：影響算法的效率主要是字典的實現(xiàn)與糾錯處理
(a）字典的實現(xiàn)已有成熟的算法，改進不大，也不會成為瓶頸；
(b)糾錯策略要簡單有效 ,如前述情況，是線性復(fù)雜度；
(3)改進
策略選擇最是重要，可以采用統(tǒng)計學(xué)習(xí)的方法改進。
//////////////////////////////////////////////
4 題
(1)思路：用哈希做
(2) 首先逐次讀入查詢串，算哈希值，保存在內(nèi)存數(shù)組中，同時統(tǒng)計頻度（注意值與日志項對應(yīng)關(guān)系） my.chinahrlab.com 選出前十的頻度，取出對應(yīng)的日志串，簡單不過了。哈希的設(shè)計是關(guān)鍵。
//////////////////////////////////////////////////
5 題
（1）思路：先將集合按照大小排列后,優(yōu)先考慮小的集合是否與大的集合有交集。有就合并，如果小集合與所有其他集合都沒有交集，則獨立。獨立的集合在下一輪的比較中不用考慮。這樣就可以盡量減少字符串的比較次數(shù)。當(dāng)所有集合都獨立的時候，就終止。
（2）處理流程：
1.將集合按照大小排序，組成集合合并待處理列表
2.選擇最小的集合，找出與之有交集的集合，如果有，合并之；如果無，則與其它集合是獨立集合，從待處理列表 中刪除。
3.重復(fù)直到待處理列表為空
算法： 1。將集合按照大小從小到大排序,組成待處理的集合列表。 2。取出待處理集合列表中最小的集合，對于集合的每個元素，依次在其他集合中搜索是否有此元素存在：
1>若存在，則將此小集合與大集合合并，并根據(jù)大小插入對應(yīng)的位置 。轉(zhuǎn)3。
2>若不存在，則在該集合中取下一個元素。如果無下一個元素，即所有元素都不存在于其他集合。則表明此集合獨立，從待處理集合列表中刪除。并加入結(jié)果集合列表。轉(zhuǎn)3。
3。如果待處理集合列表不為空，轉(zhuǎn)2。
如果待處理集合列表為空，成功退出，則結(jié)果集合列表就是最終的輸出。
算法復(fù)雜度分析：
假設(shè)集合的個數(shù)為n，最大的集合元素為m 排序的時間復(fù)雜度可以達到n*log(n) 然后對于元素在其他集合中查找，最壞情況下為（n-1）*m 查找一個集合是否與其他集合有交集的最壞情況是m*m*(n-1) 合并的時間復(fù)雜度不會超過查找集合有交集的最壞情況。所以最終最壞時間復(fù)雜度為O(m*m*n*n)
需要說明的是：此算法的平均時間復(fù)雜度會很低，因為無論是查找還是合并，都是處于最壞情況的概率很小，而且排序后優(yōu)先用最小集合作為判斷是否獨立的對象，優(yōu)先與最大的集合進行比較，這些都最大的回避了最壞情況。
(3)可能的改進：
首先可以實現(xiàn)將每個集合里面的字符串按照字典序進行排列，這樣就可以將查找以及合并的效率增高。另外，可能采取恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)也可以將查找以及合并等操作的效率得到提高。
、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、
1）此題10分
對任意輸入的正整數(shù)N，編寫C程序求N!的尾部連續(xù)0的個數(shù)，并指出計算復(fù)雜度。如：18�。�6402373705728000，尾部連續(xù)0的個數(shù)是3。 �。ú挥每紤]數(shù)值超出計算機整數(shù)界限的問題）
2）此題10分 編寫一個C語言函數(shù)，要求輸入一個url，輸出該url是首頁、目錄頁或者其他url
如下形式叫做首頁：
militia.info/
www.apcnc.com.cn/
https://www.cyjzs.comwww.greena888.com/
www.800cool.net/
https://hgh-products.my-age.net/
如下形式叫做目錄頁：
thursdaythree.net/greenhouses--gas-global-green-house-warming/
https://www.mw.net.tw/user/tgk5ar1r/profile/
https://www.szeasy.com/food/yszt/chunjie/
www.fuckingjapanese.com/Reality/
請注意：
a） url有可能帶http頭也有可能不帶
b）動態(tài)url（即含有"？"的url）的一律不算目錄頁，如：
www.buddhismcity.net/utility/mailit.php?l=/activity/details/3135/
www.buddhismcity.net/utility/mailit.php?l=/activity/details/2449/
另：如果你會linux，請用linux下的grep命令實現(xiàn)第2題的功能（附加5分）。
3）此題40分
如果必須從網(wǎng)頁中區(qū)分出一部分"重要網(wǎng)頁"（例如在10億中選8億），比其他網(wǎng)頁更值得展現(xiàn)給用戶，請?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)頁，請?zhí)岢隹尚械姆桨福嬎愠雒總�網(wǎng)頁對應(yīng)的重復(fù)度，你可以自己對網(wǎng)頁重復(fù)下定義，也可以提出需要哪些更多的網(wǎng)頁提取物來實現(xiàn)更好的去重復(fù)方案。
、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、
好久沒來了。
發(fā)生了一些事情，其間的心情已不是幾行文字所能表述的了。
終于明白有些事情，并不是自己努力就一定能圓滿的；有些事情，是我控制不了的。
唉，不提也罷！
說說今天去百度筆試的經(jīng)歷吧
部門：百度搜索應(yīng)用技術(shù)部。
地點：海淀南路銀科大廈（海淀圖書城西臨）18層。
時間：2005/6/15 10：00-11：20 am
九點從實驗室出發(fā)，725到知春路，轉(zhuǎn)735，到海淀橋下車，9：50到達百度。在725的車上碰到一男士索要手機號，說自己認識信息產(chǎn)業(yè)部的部長楊澤民先生，以居高臨下的姿態(tài)把手機號給了他-__-!
在百度前臺見到了一直幫我安排筆試的楊韞敏jj，不是想象中的HR形象，而是一副干練的女IT的樣子跳躍的靈魂很快，給我找了一間小會議室，只有一張桌子，兩把椅子，還幫我開了燈，關(guān)門，走人，我開始看題。冷汗也開始流。翻了一下三頁紙的筆試題，只有很少的傳說中的Linux題目，其他的全是C、數(shù)據(jù)結(jié)構(gòu)、算法編程的題。第一反應(yīng)：走人！但又覺得對不起陳jj，關(guān)鍵的是我已經(jīng)在筆試題上寫了姓名和學(xué)校了，sign，總的為自己的名字和學(xué)校負責(zé)吧，他們是無辜的。如此斗爭良久，決定堅持下來。
題目大致是這樣的：
第一部分選擇題：有幾道網(wǎng)絡(luò)相關(guān)的題目，巨簡單，比如第一題是TCP、RIP、IP、FTP中哪個協(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)如需將多個可執(zhí)行文件連續(xù)執(zhí)行，可生成批處理文件：
#vi [批處理文件名]
可執(zhí)行文件1
可執(zhí)行文件2
.........
最后將該批處理文件屬性該位可執(zhí)行。
調(diào)試：在編譯時使用-g參數(shù)，就可以使用gdb進行調(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)存的動態(tài)存儲區(qū)中分配一塊長度為“size”字節(jié)的連續(xù)區(qū)域，返回該區(qū)域的首地址。
calloc調(diào)用形式為(類型*)calloc(n，size)：在內(nèi)存的動態(tài)存儲區(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()：將套接字和機器上的一定的端口關(guān)聯(lián)；
connect()：連接到遠程主機；
listen()：使套接字做好連接的準(zhǔn)備，規(guī)定等待服務(wù)請求隊列的長度；
accept()：接受連接，一旦有客戶端發(fā)出連接，accept返回客戶地址信息和一個新的sock；
有了這個新的sock，雙方就可以開始收發(fā)數(shù)據(jù)：
send()和recv()：用于流式套接字或者數(shù)據(jù)套接字的通訊；
sendto()和recvfrom()：用于無連接的數(shù)據(jù)報套接字；
close()：關(guān)閉套接字；
shutdown()：選擇性的關(guān)閉套接字，可以只允許某一方向的通訊關(guān)閉；
getpeername()：返回流式套接字時對端peer信息；
gethostname()：返回程序所運行的機器的主機名字；
gethostbyname()：返回本機IP；
第三部分編程題：
1、從文件中讀取字符串?dāng)?shù)據(jù)，反序顯示并大小寫轉(zhuǎn)換。
2、給定26字母表以及對應(yīng)的密碼表，編程實現(xiàn)加密及解密功能。
第四部分思考題(正是傳說中的字典糾錯題)：
用戶在輸入英文單詞時經(jīng)常出錯，現(xiàn)對其進行就錯。給定一個正確的英文詞典，考慮糾錯實現(xiàn)。1)指出思路。2)流程、算法難易程度及可能的改進策略。
不過陳jj沒有給我答題紙，只好拿試題的背面做了答題紙兼草稿紙-___-!說實話有些題目是很基礎(chǔ)的，就是沒背過。不知怎么搞得，巨潦草。實驗室參加過筆試的通同學(xué)都是憋著勁做了兩個多小時才答完，而我只一個小時就完了，唉，正好說明肚子里只有別人一半的東西~~看著潦草而不著邊際的答題，決定在最后給陳jj寫段話，大意就是感謝她幫我挽回了一次筆試的機會，但我的表現(xiàn)很遺憾等等......然后交卷走人~~
沒想到交了試卷沒讓我走，等了大約30分鐘的樣子，有個很深沉的gg來看我的卷子跳躍的靈魂-___-!我顫顫的跟他說我很長時間沒有接觸C了，當(dāng)時脖子都紅了，真覺得丟人。gg看了一下，沒有很鄙視的樣子，問我有沒有帶簡歷。當(dāng)然木有啦~~答應(yīng)回來給他發(fā)個電子版的，然后趕緊跑人了！
題目大致是這樣的：
第一部分選擇題：
有幾道網(wǎng)絡(luò)相關(guān)的題目，巨簡單，比如第一題是TCP、RIP、IP、FTP中哪個協(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)如需將多個可執(zhí)行文件連續(xù)執(zhí)行，可生成批處理文件：
#vi [批處理文件名]
可執(zhí)行文件1
可執(zhí)行文件2
.........
最后將該批處理文件屬性該位可執(zhí)行。
調(diào)試：在編譯時使用-g參數(shù)，就可以使用gdb進行調(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)存的動態(tài)存儲區(qū)中分配一塊長度為“size”字節(jié)的連續(xù)區(qū)域，返回該區(qū)域的首地址。
calloc調(diào)用形式為(類型*)calloc(n，size)：在內(nèi)存的動態(tài)存儲區(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()：將套接字和機器上的一定的端口關(guān)聯(lián)；
connect()：連接到遠程主機；
listen()：使套接字做好連接的準(zhǔn)備，規(guī)定等待服務(wù)請求隊列的長度；
accept()：接受連接，一旦有客戶端發(fā)出連接，accept返回客戶地址信息和一個新的sock；
有了這個新的sock，雙方就可以開始收發(fā)數(shù)據(jù)：
send()和recv()：用于流式套接字或者數(shù)據(jù)套接字的通訊；
sendto()和recvfrom()：用于無連接的數(shù)據(jù)報套接字；
close()：關(guān)閉套接字；
shutdown()：選擇性的關(guān)閉套接字，可以只允許某一方向的通訊關(guān)閉；
getpeername()：返回流式套接字時對端peer信息；
gethostname()：返回程序所運行的機器的主機名字；
gethostbyname()：返回本機IP；
第三部分編程題：
1、從文件中讀取字符串?dāng)?shù)據(jù)，反序顯示并大小寫轉(zhuǎn)換。
2、給定26字母表以及對應(yīng)的密碼表，編程實現(xiàn)加密及解密功能。
第四部分思考題(正是傳說中的字典糾錯題)：
用戶在輸入英文單詞時經(jīng)常出錯，現(xiàn)對其進行就錯。給定一個正確的英文詞典，考慮糾錯實現(xiàn)。1)指出思路。2)流程、算法難易程度及可能的改進策略。
一道算法題目答案
int Replace(Stringtype &S,Stringtype T,Stringtype V);//將串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
return n;
}//Replace
分析:i+=Strlen(V);這一句是必需的,也是容易忽略的.如省掉這一句,則在某些情況下,會引起不希望的后果,雖然在大多數(shù)情況下沒有影響.請思考:設(shè)S='place', T='ace', V='face',則省掉i+=Strlen(V);運行時會出現(xiàn)什么結(jié)果? （無限遞歸face）
百度2005年的筆試題
1.實現(xiàn) void delete_char(char * str, char ch);
把str中所有的ch刪掉
2.把字符串S中所有A子串換成B,這個沒給函數(shù)原型
3.搜索引擎的日志要記錄所有查詢串,有一千萬條查詢,不重復(fù)的不超過三百萬
要統(tǒng)計最熱門的10條查詢串. 內(nèi)存<1G. 字符串長 0-255
(1) 主要解決思路 //具體用詞和原題不大一樣
(2) 算法及其復(fù)雜度分析
4.有字典,設(shè)計一個英文拼寫糾正算法 (1) 思想 (2) 算法及復(fù)雜度 (3) 改進
5. { aaa, bb, ccc, dd }, { bbb, ff }, { gg } 等一些字符串的集合
要求把交集不為空的集合并起來,如上例會得到 { aaa, bb, ccc, dd, ff }, {gg}
(1) 思想 (2) 算法及復(fù)雜度 (3) 改進
、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、
一、選擇題：15分 共10題
1.一個含有n個頂點和e條邊的簡單無向圖，在其鄰接矩陣存儲結(jié)構(gòu)中共有____個零元素。
A．e B．2e C．n2-e D．n2-2e
2.____是面向?qū)ο蟪绦蛟O(shè)計語言中的一種機制。這種機制實現(xiàn)了方法的定義與具體的對象無關(guān)，而對方法的調(diào)用則可以關(guān)聯(lián)于具體的對象。
A．繼承（Inhertance） B．模板（Template）
C．對象的自身引用（Self-Reference） D．動態(tài)綁定（Dynamic Binding）
3.應(yīng)用層DNS協(xié)議主要用于實現(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默認情況下，一個進程最多能打開多少文件？
A.64 B. 128 C. 512 D. 1024
5.下面結(jié)構(gòu)體
struct s1 {
char ch, *ptr;
union {
short a, b;
unsigned int c:2, d:1;
}
struct s1 *next;
};
的大小是_____：
A. 12字節(jié) B.16字節(jié) C.20字節(jié) D. 24字節(jié)
6.任何一個基于"比較"的內(nèi)部排序的算法，若對6個元素進行排序，則在最壞情況下所需的比較次數(shù)至少為____。
A．10 B．11 C．21 D．36
7.以下不是進程間通訊的是___
A 共享內(nèi)存 B 信號量 C線程局部存儲 D 消息隊列
8.下面程序，求count的值
int func(x)
{
int count= 0;
x=9999;
while(x)
{
Count ++;
x = x&(x-1);
}
return count;
}
A 8； B 10； C 5； D 11
9.使用malloc系統(tǒng)調(diào)用分配的內(nèi)存是在____ 上分配的？
A 棧； B bss； C 物理內(nèi)存； D 堆
10.最壞情況下，合并兩個大小為n的已排序數(shù)組所需要的比較次數(shù)_____
A.2n B.2n-1 C.2n+1 D.2n-2
二、簡答題：20分，共3題
1.（5分）下面這段代碼是把中英文混合字符串(漢字用兩個字節(jié)表示，特點是第一個字節(jié)的最高位為1)中的大寫字母轉(zhuǎn)化為小寫字母，請找出其中的bug，注意各種異常情況。
for (char *piterator = szWord; *piterator != 0; piterator++)
{
if (*piterator & 0x80 != 0)
{
piterator++;
}
else if (*piterator >= 'A' && *piterator <= 'Z')
piterator += 32;
}
2.（5分）對給定的上億條無序的url，請按照domain、site以及path分別排序，并請指出排序過程中可能會遇到的哪些問題？如何提高效率？
例如：https://www.baidu.com/path/about.html，domain、site以及path的定義分別如下：
Domain:baidu.com
Site:www.baidu.com
Path: www.baidu.com/path
3.（10分）某型CPU的一級數(shù)據(jù)緩存大小為16K字節(jié)，cache塊大小為64字節(jié)；二級緩存大小為256K字節(jié)，cache塊大小為4K字節(jié)，采用二路組相聯(lián)。經(jīng)測試，下面兩段代碼運行時效率差別很大，請分析哪段代碼更好，以及可能的原因。
為了進一步提高效率，你還可以采取什么辦法？
A段代碼
int matrix[1023][15];
const char *str = "this is a str";
int i, 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段代碼
int matrix[1025][17];
const char *str = "this is a str";
int i, j, sum = 0;
for(i = 0; i < 17; i++) {
for(j = 0; j < 1025; j++) {
sum += matrix[j][i] + strlen(str);
}
}
三、編程題：30分 共1題
注意：要求盡可能提供完整代碼，如果可以編譯運行酌情加分。
1.內(nèi)存中有一個長數(shù)組，條目數(shù)為10萬，數(shù)組單元為結(jié)構(gòu)體struct array，sizeof(struct array)為512字節(jié)。結(jié)構(gòu)有一int型成員變量weight�，F(xiàn)需要取得按weight值從大到小排序的前500個數(shù)組單元，請實現(xiàn)算法，要求效率盡可能高。
四、設(shè)計題：35分 共1題
注意：請盡可能詳細描述你的數(shù)據(jù)結(jié)構(gòu)、系統(tǒng)架構(gòu)、設(shè)計思路等，建議多寫一些偽代碼或者流程說明。
1.請設(shè)計一個字典。以字符串為索引，存儲用戶定義的定長結(jié)構(gòu)。要求有增、刪、查、改的功能。已經(jīng)給定一個函數(shù)，可以由字符串映射到一個簽名，每個簽名由兩個unsigned int類型組成。假設(shè)每一個字符串能夠?qū)?yīng)唯一的一個簽名，完全沒有重復(fù)（或者重復(fù)的概率可以忽略），并且簽名分布足夠均勻。
請描述你的數(shù)據(jù)結(jié)構(gòu)？內(nèi)存如何申請？增、刪、查、改的功能如何實現(xiàn)？如果操作很頻繁，該如何優(yōu)化？
、、、、、、、、、、、、、、、、、、、、、、、、、、
經(jīng)過在線筆試、兩輪電話面試，今天上午收到了百度的拒信，我的百度求職算是告一段落了……
從百度校園招聘開始，我就投了一份簡歷。在別人都有在線筆試機會的時候，我卻沒有任何消息。
聽說師兄可以給推薦，我就又通過內(nèi)部推薦的方式投遞了一次，這次很快就有消息了——拒信。
那時基本上就放棄了百度。可是大概20多天以后，我投遞的第一份簡歷有消息了——通知我在線筆試。經(jīng)過精心準(zhǔn)備，筆試題答得還湊合。過了幾天給我來了封郵件告知我筆試通過，會找時間安排電話面試。又過了好幾天，我正在剃頭的時候接到百度電話，約了第二天下午三點電話面試。心情異常興奮，回到寢室拼命復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)并收集百度面試題型……臨陣磨槍 呵呵。
百度的面試氛圍很是輕松，讓你很快就覺得是在聊天而不是面試。第一輪主要是在針對我的在線筆試的題目進行提問和分析，主要講的是做題的思路和改進的方法。面試時間大概有半個小時，覺得應(yīng)該有下一輪。
果然上個星期五晚上接到了百度技術(shù)經(jīng)理的電話，自稱姓劉。在前一天我同學(xué)也是這個時候接到百度第二面電話，看來是同一個人，后來的面試內(nèi)容證實了是同一個人。面試過程大概如下：
1、介紹一下項目。
2、提了一個問題：上千萬條記錄，統(tǒng)計出重復(fù)記錄最多的前N條。
3、一個概率題：54張撲克牌，除去兩張大小王剩下52張撲克牌。問紅桃A和黑桃A同時被一個人拿到的概率是多少？
4、多個線程訪問共享內(nèi)存時因該怎么辦？
5、在寫程序遇到問題的時候，通常采用什么調(diào)試方法？
6、一個client/server的協(xié)議問題
7、剩下就是隨便聊聊，比如有缺點、期望工作的性質(zhì)、職業(yè)規(guī)劃等
總結(jié)一下教訓(xùn)：
1、介紹項目的時候不能一味的按照事前想好的模板說，應(yīng)該根據(jù)所申請的工作的性質(zhì)，多說一些和自己申請的工作內(nèi)內(nèi)容相近的東西說。我在介紹我的項目的時候，說了很多硬件的東西，而相關(guān)的Linux下的C編程卻沒有提到多少，一大失敗之處。
2、對于他提的第二個問題，當(dāng)時因為緊張沒有想出來，掛了電話以后才有了思路。
3、這個概率題以前碰到過，而且和同學(xué)們討論過，答案很早就知道了。但是遇到面試的時候，不能馬上就說出答案，因為這樣擺明了高訴人家你以前就見過這道題，這樣就失去了作為考題的意義。所以，如果事前知道答案也不要馬上說出來，裝作考慮中，然后慢慢說出答案。我就是很快就說出了答案，失�。�
4、在問項目的時候，他問我代碼行大概有多少？我說大概有5.6K行左右。在回答第四個問題的時候，我?guī)缀跏菍纤v過的東西背了一遍給他，雖然答案是正確的，但是我估計他一聽就聽出來是在背書了，所以這也會減分不少。，而且百度強調(diào)創(chuàng)新，其實就算你不知道答案也可以按照自己的思路說一下的，只要邏輯清晰、合理都會比我背書強……
5、我的回答是有時候用gdb，有時候用輸出日志的形式。以我之前給他講的項目經(jīng)驗是不大可能會涉及這么多的知識的，所以估計他又聽出我是在背書了……繼續(xù)減分
6、后來我發(fā)現(xiàn)這個問題其實他不是在考我問題的答案，是考我解決問題的能力和考慮問題的思路。這點是我比較差的地方，沒辦法……減分
我前面表現(xiàn)那么失敗，基本上已經(jīng)沒有什么希望了，后面的談話已經(jīng)沒有意義了，只不過是禮貌性的結(jié)束這次面試了。
上面的總結(jié)是我收到拒信以后才總結(jié)出來的，還以為能被錄取呢……
面試官太和藹了，而且氣氛及其融洽，根本沒有任何不好的征兆，面試官好厲害！
至此，我的百度求職過程到此告一段落……生活還在繼續(xù)，工作還得繼續(xù)努力去找，加油！
百度電話面試題目：
1.談?wù)勀銓?shù)據(jù)庫中索引的理解
2.現(xiàn)在普通關(guān)系數(shù)據(jù)庫用得數(shù)據(jù)結(jié)構(gòu)是什么類型的數(shù)據(jù)結(jié)構(gòu)
3.索引的優(yōu)點和缺點
4.session和cache的區(qū)別是什么
5.如果有幾千個session，怎么提高效率