2006百度筆試題

一、選擇題：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個數組單元，請實現演算法，要求效率儘可能高。