百度筆試題目及答案(一)
第一題簡答題
1.多執行緒和多程序模式有什麼區別?在用兩種模型開發服務程式時，分別有什麼優缺點?採用長連線和短連線模式有什麼區別?分別有什麼優缺點?採用同步和非同步模式有什麼區別?分別有什麼優缺點。
(1)啟動程序的時候，作業系統會為程序分配資源，其中最主要的資源是記憶體空間，因為程式是在記憶體中執行的。在程序中，有些程式流程塊是可以亂序執行的，並且這個程式碼塊可以同時被多次執行。實際上，這樣的程式碼塊就是執行緒體。執行緒是程序中亂序執行的程式碼流程。當多個執行緒同時執行的時候，這樣的執行模式成為併發執行。
對於一個程序中的多個執行緒來說，多個執行緒共享程序的記憶體塊，當有新的執行緒產生的時候，作業系統不分配新的記憶體，而是讓新執行緒共享原有的程序塊的記憶體。因此，執行緒間的通訊很容易，速度也很快。不同的程序因為處於不同的記憶體塊，因此程序之間的通訊相對困難。執行緒切換快，但實現稍複雜。程序易實現，較穩定，但效能與執行緒相比較差。
(2)所謂長連線，指在一個TCP連線上可以連續傳送多個數據包，在TCP連線保持期間，如果沒有資料包傳送，需要雙方發檢測包以維持此連線，一般需要自己做線上維持。
短連線是指通訊雙方有資料互動時，就建立一個TCP連線，資料傳送完成後，則斷開此TCP連線，一般銀行都使用短連線。
長連線多用於操作頻繁，點對點的通訊，而且連線數不能太多情況，。每個TCP連線都需要三步握手，這需要時間，如果每個操作都是先連線，再操作的話那麼處理速度會降低很多，所以每個操作完後都不斷開，次處理時直接傳送資料包就OK了，不用建立TCP連線。而像WEB網站的http服務一般都用短連結，因為長連線對於服務端來說會耗費一定的資源，而像WEB網站這麼頻繁的成千上萬甚至上億客戶端的連線用短連線會更省一些資源，如果用長連線，而且同時有成千上萬的使用者，如果每個使用者都佔用一個連線的話，那可想而知吧。所以併發量大，但每個使用者無需頻繁操作情況下需用短連好。
(3)同步:呼叫方呼叫一個程式,等待返回,然後再繼續下面的程式處理
非同步: 呼叫方呼叫一個程式,不等待返回,繼續執行下面的程式。
1)非同步通訊簡單，雙方時鐘可允許一定誤差。同步通訊較複雜，雙方時鐘的允許誤差較小。
2)通訊效率：非同步通訊低，同步通訊高。
2.請寫出以下程式的執行結果，並解釋導致這樣執行結果的關鍵性原因。
#include
using std::cout;
class P
{
public:
virtual void print()
{
cout << "P";
}
};
class Q: public P
{
public:
virtual void print()
{
cout << "Q";
}
};
int main()
{
P * p = new P;
Q * q = static_cast (p);
q->print();
delete p;
cout << endl;
q = new Q;
p = q;
q->print();
p->print();
cout << endl;
p = new (q) P;
q->print();
p->print();
cout << endl;
p->~P();
delete q;
return 0;
}
P
QQ
PP
第二題 演算法與程式設計題
1.給定如下的n*n的數字矩陣，每行從左到右是嚴格遞增， 每列的資料也是嚴格遞增
1 2 3
3 5 6
4 8 9
現在要求設計一個演算法， 給定一個數k 判斷出k是否在這個矩陣中。 描述演算法並且給出時間複雜度(不考慮載入矩陣的消耗)
演算法思想：
沿著對角線查詢，獲得i,使得k位於a[i][i]與a[i+1][i+1]之間。
k只可能存在於a[i][i]對應的右上角矩陣 和a[i+1][i+1]對應的左下角矩陣。
使用遞迴法繼續查詢即可。
時間複雜度 O(n)
int searchK(int int_arr[][],int n,int startlow,int startclm,int k)
{
int lefttemp=0;
int downtemp=0;
int i=0;
i++; if (i==n) return 0; else if(arr[i][i]==k) reuturn 1; else return searchK(int_arr,n,startlow,startclm+i,k)+searchK(int_arr,n,startlow+i,startclm,k); } 2.設 一個64位整型n,各個bit位是1的個數為a個. 比如7, 2進位制就是 111, 所以a為3。 現在給出m個數, 求各個a的值。要求程式碼實現。 #include #include using namespace std; int count(long long v) { int num=0; while(v) { v &=(v-1); //執行效率為V中1的個數，時間複雜度比通過除操作、位操作比較高出很多 num++; } return num; } void main() { vector long long i; cout<<"輸入需要計算的'數，Ctrl+z 停止" < while(cin>>i) { //輸入隨機個數的數，使用Ctrl+z 停止，之後回車鍵繼續。 _back(i); }; for(vector { int n=count(arr[idx]); cout< } } 第三題 系統設計題 實現一個簡化的搜尋提示系統。給定一個包含了使用者query的日誌檔案，對於輸入的任意一個字串s，輸出以s為字首的在日誌中出現頻率最高的前10條query。 由於是分散式系統，假設至少有26臺機器，每個機器儲存以26個字母開頭的query日誌檔案(如機器1存的是a字母開頭的，機器2存的是以b字母開頭的……) 每個機器上維護著一張雜湊表，對於每條query, 在雜湊表表中存放其地址(雜湊地址為鏈式的)，並對其進行排序，按頻率由高到低進行排序。 當用戶進行搜尋時，可以很快定位到某臺機器，並根據雜湊表，返回出現頻率最高的前10條query。 提示： 1、可以預處理日誌 2、假設query不超過10億條，每個query不超過50位元組。 3、考慮在大查詢量的情況下如何實現分散式服務 百度筆試題目及答案(二) 一、選擇題：15 分 共 10 題 1. 在排序方法中，關鍵碼比較次數與記錄地初始排列無關的是： A. Shell 排序 B. 歸併排序 C. 直接插入排序 D. 選擇排序 選擇 A 2. 以下多執行緒對 int 型變數x的操作，哪幾個需要進行同步： A. x=y; B. x++; C. ++x; D. x=1; 選擇 B, C 3. 程式碼 void func() { static int val; … } 中，變數 val 的記憶體地址位於： A. 已初始化資料段 B.未初始化資料段 C.堆 D.棧 選擇 A 4. 同一程序下的執行緒可以共享以下： A. stack B. data section C. register set D. thread ID 選擇 A, B 5. TCP 和 IP 分別對應了 OSI 中的哪幾層? A. Application layer B. Data link layer C. Presentation layer D. Physical layer E. Transport layer F. Session layer G. Network layer 選擇 EG 6. short a[100]，sizeof(a) 返回? A. 2 B. 4 C. 100 D. 200 E. 400 選擇 D 7. 以下哪種不是基於元件的開發技術_____。 A. XPCOM B. XP C. COM D. CORBA 選擇 B 8. 以下程式碼列印的結果是(假設執行在 i386 系列計算機上)： 字串2 struct st_t { int status; short *pdata; char errstr[32]; }; st_t st[16]; char *p = (char *)( st[2]tr + 32 ); printf( "%d", ( p - (char *)(st) ) ); A. 32 B. 114 C. 120 D. 1112 選擇 C,因為st[2]的起始地址比st[0]的起始地址高80位, st[2]tr的起始地址比st[2]的起始地址高8位 再加上32位就等於 120. 9. STL 中的哪種結構是連續形式的儲存： A. map B. set C. list D. vector 選擇 D 10. 一個棧的入棧序列是 A，B，C，D，E，則棧的不可能的輸出序列是： A. EDCBA B. DECBA C. DCEAB D. ABCDE 選擇 C 二、簡答題：20 分，共 2 題 1. (5 分)重複多次 fclose 一個開啟過一次的 FILE *fp 指標會有什麼結果，並請解釋。 導致 fp 所指的檔案被多次釋放, 導致不可預期的後果. 5. 一個B類網的子網掩碼是，這個子網能擁有的最大主機數是： A. 240 B. 255 C.4094 D. 65534 6. 以下程式碼執行後，val的值是___: unsigned long val = 0; char a = 0x48; char b = 0x52; val = b << 8 | a; A 20992 B 21064 C 72 D 0 選擇 B，b 的十進位制為 82，二進位制為 101，0010 b 左移 8 位為 101，0010，0000，0000 a 的十進位制為 72， 二進位制為 100，1000 b<<8 | a 為 21064 7. 記憶體的速度遠遠高於磁碟速度，所以為了解決這個矛盾，可以採用： 字串2 A 並行技術 B 虛存技術 C 緩衝技術 D 通道技術 9. 同一程序下的執行緒可以共享以下 A. stack B. data section C. register set D. thread ID 選擇 B,C 10. 以下哪種操作最適合先進行排序處理? A 找最大、最小值 B 計算算術平均值 C 找中間值 D 找出現次數最多的值 選擇 A 一、選擇題：15 分 共 10 題 1. 在排序方法中，關鍵碼比較次數與記錄地初始排列無關的是： A. Shell 排序 B. 歸併排序 C. 直接插入排序 D. 選擇排序 2. 以下多執行緒對 int 型變數x的操作，哪幾個需要進行同步： A. x=y; B. x++; C. ++x; D. x=1; 3. 程式碼 void func() { static int val; … } 中，變數 val 的記憶體地址位於： A. 已初始化資料段 B.未初始化資料段 C.堆 D.棧 4. 同一程序下的執行緒可以共享以下： A. stack B. data section C. register set D. thread ID 5. TCP 和 IP 分別對應了 OSI 中的哪幾層? A. Application layer B. Data link layer C. Presentation layer D. Physical layer E. Transport layer F. Session layer G. Network layer 6. short a[100]，sizeof(a) 返回? A. 2 B. 4 C. 100 D. 200 E. 400 7. 以下哪種不是基於元件的開發技術_____。 A. XPCOM B. XP C. COM D. CORBA 8. 以下程式碼列印的結果是(假設執行在 i386 系列計算機上)： struct st_t { int status; short *pdata; char errstr[32]; }; st_t st[16]; char *p = (char *)( st[2]tr + 32 ); printf( "%d", ( p - (char *)(st) ) ); A. 32 B. 114 C. 120 D. 1112 9. STL 中的哪種結構是連續形式的儲存： A. map B. set C. list D. vector 10. 一個棧的入棧序列是 A，B，C，D，E，則棧的不可能的輸出序列是： A. EDCBA B. DECBA C. DCEAB D. ABCDE 二、簡答題：20 分，共 2 題
while(int_arr[startlow+i][startclm+i]