百度筆試題及答案

1、第一題 簡(jiǎn)答題1多線程和多進(jìn)程模式有什么區(qū)別？在用兩種模型開(kāi)發(fā)效勞程序時(shí)，分別有什么優(yōu)缺點(diǎn)？采用長(zhǎng)連接和短連接模式有什么區(qū)別？分別有什么優(yōu)缺點(diǎn)？采用同步和異步模式有什么區(qū)別？分別有什么優(yōu)缺點(diǎn)。1啟動(dòng)進(jìn)程的時(shí)候，操作系統(tǒng)會(huì)為進(jìn)程分配資源，其中最主要的資源是內(nèi)存空間，因?yàn)槌绦蚴窃趦?nèi)存中運(yùn)行的。在進(jìn)程中，有些程序流程塊是可以亂序執(zhí)行的，并且這個(gè)代碼塊可以同時(shí)被屢次執(zhí)行。實(shí)際上，這樣的代碼塊就是線程體。線程是進(jìn)程中亂序執(zhí)行的代碼流程。當(dāng)多個(gè)線程同時(shí)運(yùn)行的時(shí)候，這樣的執(zhí)行模式成為并發(fā)執(zhí)行。對(duì)于一個(gè)進(jìn)程中的多個(gè)線程來(lái)說(shuō)，多個(gè)線程共享進(jìn)程的內(nèi)存塊，當(dāng)有新的線程產(chǎn)生的時(shí)候，操作系統(tǒng)不分配新的內(nèi)存，而是讓新線程

2、共享原有的進(jìn)程塊的內(nèi)存。因此，線程間的通信很容易，速度也很快。不同的進(jìn)程因?yàn)樘幱诓煌膬?nèi)存塊，因此進(jìn)程之間的通信相對(duì)困難。線程切換快，但實(shí)現(xiàn)稍復(fù)雜。進(jìn)程易實(shí)現(xiàn)，較穩(wěn)定，但性能與線程相比擬差。2所謂長(zhǎng)連接，指在一個(gè)TCP連接上可以連續(xù)發(fā)送多個(gè)數(shù)據(jù)包，在TCP連接保持期間，如果沒(méi)有數(shù)據(jù)包發(fā)送，需要雙方發(fā)檢測(cè)包以維持此連接，一般需要自己做在線維持。 短連接是指通信雙方有數(shù)據(jù)交互時(shí)，就建立一個(gè)TCP連接，數(shù)據(jù)發(fā)送完成后，那么斷開(kāi)此TCP連接，一般銀行都使用短連接。長(zhǎng)連接多用于操作頻繁，點(diǎn)對(duì)點(diǎn)的通訊，而且連接數(shù)不能太多情況，。每個(gè)TCP連接都需要三步握手，這需要時(shí)間，如果每個(gè)操作都是先連接，再操作的話那

3、么處理速度會(huì)降低很多，所以每個(gè)操作完后都不斷開(kāi)，次處理時(shí)直接發(fā)送數(shù)據(jù)包就OK了，不用建立TCP連接。而像WEB網(wǎng)站的 效勞一般都用短鏈接，因?yàn)殚L(zhǎng)連接對(duì)于效勞端來(lái)說(shuō)會(huì)消耗一定的資源，而像WEB網(wǎng)站這么頻繁的成千上萬(wàn)甚至上億客戶(hù)端的連接用短連接會(huì)更省一些資源，如果用長(zhǎng)連接，而且同時(shí)有成千上萬(wàn)的用戶(hù)，如果每個(gè)用戶(hù)都占用一個(gè)連接的話，那可想而知吧。所以并發(fā)量大，但每個(gè)用戶(hù)無(wú)需頻繁操作情況下需用短連好。3同步:調(diào)用方調(diào)用一個(gè)程序,等待返回,然后再繼續(xù)下面的程序處理異步: 調(diào)用方調(diào)用一個(gè)程序,不等待返回,繼續(xù)執(zhí)行下面的程序。1)異步通信簡(jiǎn)單，雙方時(shí)鐘可允許一定誤差。同步通信較復(fù)雜，雙方時(shí)鐘的允許誤差較小。

4、2)通信效率：異步通信低，同步通信高。2請(qǐng)寫(xiě)出以下程序的運(yùn)行結(jié)果，并解釋導(dǎo)致這樣運(yùn)行結(jié)果的關(guān)鍵性原因。#include using std:cout;class Ppublic: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 print(); p-print(); cout print(); p-print(); cout P();

5、 delete q; return 0;PQQPP第二題 算法與程序設(shè)計(jì)題1給定如下的n*n的數(shù)字矩陣，每行從左到右是嚴(yán)格遞增， 每列的數(shù)據(jù)也是嚴(yán)格遞增1 2 33 5 64 8 9現(xiàn)在要求設(shè)計(jì)一個(gè)算法， 給定一個(gè)數(shù)k 判斷出k是否在這個(gè)矩陣中。 描述算法并且給出時(shí)間復(fù)雜度不考慮載入矩陣的消耗算法思想： 沿著對(duì)角線查找，獲得i,使得k位于aii與ai+1i+1之間。 k只可能存在于aii對(duì)應(yīng)的右上角矩陣 和ai+1i+1對(duì)應(yīng)的左下角矩陣。 使用遞歸法繼續(xù)查找即可。時(shí)間復(fù)雜度 O(n)int searchK(int int_arr,int n,int startlow,int startclm,

6、int k)int lefttemp=0;int downtemp=0;int i=0;while(int_arrstartlow+istartclm+ik|in)i+;if (i=n)return 0;else if(arrii=k)reuturn 1;else return searchK(int_arr,n,startlow,startclm+i,k)+searchK(int_arr,n,startlow+i,startclm,k);2設(shè) 一個(gè)64位整型n,各個(gè)bit位是1的個(gè)數(shù)為a個(gè). 比方7, 2進(jìn)制就是 111, 所以a為3?，F(xiàn)在給出m個(gè)數(shù), 求各個(gè)a的值。要求代碼實(shí)現(xiàn)。#incl

7、ude #includeusing namespace std;int count(long long v)int num=0;while(v)v &=(v-1);/執(zhí)行效率為V中1的個(gè)數(shù)，時(shí)間復(fù)雜度比通過(guò)除操作、位操作比擬高出很多num+;return num;void main() vector arr; long long i; cout輸入需要計(jì)算的數(shù)，Ctrl+z 停止 i) /輸入隨機(jī)個(gè)數(shù)的數(shù)，使用Ctrl+z 停止，之后回車(chē)鍵繼續(xù)。arr.push_back(i); ; for(vector:size_type idx=0;idx!=arr.size();+idx) int n=count(arridx);coutnn; 第三題 系統(tǒng)設(shè)計(jì)題實(shí)現(xiàn)一個(gè)簡(jiǎn)化的搜索提示系統(tǒng)。給定一個(gè)包含了用戶(hù)query的日志文件，對(duì)于輸入的任意一個(gè)字符串s，輸出以s為前綴的在日志中出現(xiàn)頻率最高的前10條query。由于是分布式系統(tǒng)，假設(shè)至少有26臺(tái)機(jī)器，每個(gè)機(jī)器存儲(chǔ)以26個(gè)字母開(kāi)頭的query日志文件如機(jī)器1存的是a字母開(kāi)頭的，機(jī)器2存的是以b字母開(kāi)頭的每個(gè)機(jī)器上維護(hù)著一張哈希表，對(duì)于每條query, 在哈希表表中存放其地址哈希地址為鏈?zhǔn)降?，并?duì)其進(jìn)行排序，按頻率