2006百度筆試題

欄目: 面試筆試 / 發佈於: / 人氣:2.89W

一、選擇題：15分共10題

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

2.____是面向對象程序設計語言中的一種機制。這種機制實現了方法的定義與具體的對象無關，而對方法的調用則可以關聯於具體的對象。
A．繼承（Inhertance） B．模板（Template）
C．對象的自身引用（Self-Reference） D．動態綁定（Dynamic Binding）

3.應用層DNS協議主要用於實現網絡服務功能.
A. IP地址到網絡設備名字的映射 B. IP地址到網絡硬件地址的映射
C. 網絡設備名字到IP地址的映射 D. 網絡硬件地址到IP地址的映射

x默認情況下，一個進程最多能打開多少文件？
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字節 B.16字節 C.20字節 D. 24字節

6.任何一個基於"比較"的內部排序的算法，若對6個元素進行排序，則在最壞情況下所需的比較次數至少為____。
A．10 B．11 C．21 D．36

7.以下不是進程間通訊的是___
A 共享內存 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系統調用分配的內存是在____ 上分配的？
A 棧； B bss； C 物理內存； D 堆

10.最壞情況下，合併兩個大小為n的已排序數組所需要的比較次數_____
A.2n B.2n-1 C.2n+1 D.2n-2

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

1.（5分）下面這段代碼是把中英文混合字符串(漢字用兩個字節表示，特點是第一個字節的最高位為1)中的大寫字母轉化為小寫字母，請找出其中的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分別排序，並請指出排序過程中可能會遇到的哪些問題？如何提高效率？
例如：，domain、site以及path的定義分別如下：
Domain:
Site:
Path:

3.（10分）某型CPU的一級數據緩存大小為16K字節，cache塊大小為64字節；二級緩存大小為256K字節，cache塊大小為4K字節，採用二路組相聯。經測試，下面兩段代碼運行時效率差別很大，請分析哪段代碼更好，以及可能的原因。
為了進一步提高效率，你還可以採取什麼辦法？
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.內存中有一個長數組，條目數為10萬，數組單元為結構體struct array，sizeof(struct array)為512字節。結構有一int型成員變量weight。現需要取得按weight值從大到小排序的前500個數組單元，請實現算法，要求效率儘可能高。

Tags：筆試百度