百度軟件筆試題
一、選擇題：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地址的映射
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字節 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分別排序，并請指出排序過程中可能會遇到的哪些問題?如何提高效率?
例如：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的一級數據緩存大小為16K字節，cache塊大小為64字節;二級緩存大小為256K字節，cache塊大小為4K字節，采用二路組相聯，
資料共享平臺
《百度軟件筆試題》(http://salifelink.com)。經測試，下面兩段代碼運行時效率差別很大，請分析哪段代碼更好，以及可能的原因。為了進一步提高效率，你還可以采取什么辦法?
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個數組單元，請實現算法，要求效率盡可能高。
四、設計題：35分 共1題
注意：請盡可能詳細描述你的數據結構、系統架構、設計思路等，建議多寫一些偽代碼或者流程說明。
1. 請設計一個字典。以字符串為索引，存儲用戶定義的定長結構。要求有增、刪、查、改的功能。已經給定一個函數，可以由字符串映射到一個簽名，每個簽名由兩個unsigned int類型組成。假設每一個字符串能夠對應唯一的一個簽名，完全沒有重復(或者重復的概率可以忽略)，并且簽名分布足夠均勻。
請描述你的數據結構?內存如何申請?增、刪、查、改的功能如何實現?如果操作很頻繁，該如何優化?
///////////////
有一個數據庫，用一張表存儲了某超市的歷史銷售記錄，這個表中包含如下數據信息：商品大類、商品小類、商品編號、商品名稱、供應商編號、供應商名稱、入庫時間、入庫價格、批次、當批入庫總量、目前庫存量、銷售時間、商品單價、銷售數量、付款方式、銷售金額、是否優惠、優惠金額、銷售柜臺號、銷售終端號、銷售人員姓名等。
(1)請把數據表拆分成符合第三范式的多個表(寫出表的結構定義SQL語句);
(2)根據拆分后的結構，寫出如下統計SQL語句：
某種商品的總銷售額;
某個供應商的總交易次數;
每月每個商品大類的銷售額排名;
(3)如果對該表的操作主要是如(2)所要求的數據統計。在數據量非常大的情況下，上述統計會出現效率問題，要更快的得到上述數據統計的結果，都有哪些思路和辦法?如果你面對這樣一個需求，會采取什么樣的設計，或者對現有的設計進行怎樣的改進?
【百度軟件筆試題】相關文章：
6.軟件測試 試題
7.軟件測試 試題
8.軟件筆試題