2006百度筆試題  

一、選擇題：15分 共10題 
1.一個含有n個頂點和e條邊的簡單無向圖，在其鄰接矩陣存儲結構中共有____個零元素。 
A．e　　　 B．2e　　　 C．n2-e　　 D．n2-2e 

2.____是面向?qū)ο蟪绦蛟O計語言中的一種機制。這種機制實現(xiàn)了方法的定義與具體的對象無關，而對方法的調(diào)用則可以關聯(lián)于具體的對象。 
A．繼承（Inhertance） B．模板（Template） 
C．對象的自身引用（Self-Reference） D．動態(tài)綁定（Dynamic Binding） 

3.應用層DNS協(xié)議主要用于實現(xiàn) 網(wǎng)絡服務功能. 
A. IP地址到網(wǎng)絡設備名字的映射 B. IP地址到網(wǎng)絡硬件地址的映射 
C. 網(wǎng)絡設備名字到IP地址的映射 D. 網(wǎng)絡硬件地址到IP地址的映射 

4.linux默認情況下，一個進程最多能打開多少文件？ 
A.64 B. 128 C. 512 D. 1024 

5.下面結構體 
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分別排序，并請指出排序過程中可能會遇到的哪些問題？如何提高效率？ 
例如：http://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[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] + strlen(str); 
} 
} 


三、編程題：30分 共1題 

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

1.內(nèi)存中有一個長數(shù)組，條目數(shù)為10萬，數(shù)組單元為結構體struct array，sizeof(struct array)為512字節(jié)。結構有一int型成員變量weight。現(xiàn)需要取得按weight值從大到小排序的前500個數(shù)組單元，請實現(xiàn)算法，要求效率盡可能高。 


四、設計題：35分 共1題 

注意：請盡可能詳細描述你的數(shù)據(jù)結構、系統(tǒng)架構、設計思路等，建議多寫一些偽代碼或者流程說明。 

1.請設計一個字典。以字符串為索引，存儲用戶定義的定長結構。要求有增、刪、查、改的功能。已經(jīng)給定一個函數(shù)，可以由字符串映射到一個簽名，每個簽名由兩個unsigned int類型組成。假設每一個字符串能夠?qū)ㄒ坏囊粋€簽名，完全沒有重復（或者重復的概率可以忽略），并且簽名分布足夠均勻。 

請描述你的數(shù)據(jù)結構？內(nèi)存如何申請？增、刪、查、改的功能如何實現(xiàn)？如果操作很頻繁，該如何優(yōu)化？