往年百度校園招聘筆試題

1、第 PAGE17 頁(yè) 共 NUMPAGES17 頁(yè)往年百度校園招聘筆試題往年百度校園招聘筆試題筆試的題目：一.簡(jiǎn)答題1.簡(jiǎn)述iso的7層設(shè)計(jì)2.如何在多個(gè)進(jìn)展間進(jìn)展數(shù)據(jù)共享(至少寫出3種)3.簡(jiǎn)述TCP與UDP的區(qū)別二.算法題1.有一個(gè)數(shù)據(jù)A = a_1,a_2,a_3a_n,n的大小不定，請(qǐng)?jiān)O(shè)計(jì)算法將A中的所有數(shù)據(jù)組合進(jìn)展輸出2.有一個(gè)數(shù)組，里面的元素相鄰之間相差絕對(duì)值1，如4,5,6,5,4,5,6,7,8,7,8,9，先給定已數(shù)據(jù)A請(qǐng)輸出該數(shù)據(jù)在數(shù)組中的位置J?3.二叉樹的面積等于二叉樹的長(zhǎng)乘以二叉樹的寬，二叉樹的寬等于最長(zhǎng)節(jié)點(diǎn)間的間隔 ，二叉樹的長(zhǎng)等于根節(jié)點(diǎn)到子節(jié)點(diǎn)的最長(zhǎng)長(zhǎng)度，請(qǐng)?jiān)O(shè)計(jì)算

2、法計(jì)算二叉樹的面積?三.算法設(shè)計(jì)題百度地圖中存在需要標(biāo)注的很多點(diǎn)，并且這些點(diǎn)都需要帶描繪，現(xiàn)將描繪假設(shè)為矩形，并且可以位于點(diǎn)的左邊或右邊，但點(diǎn)不能挪動(dòng)，假如兩個(gè)點(diǎn)間的描繪發(fā)生覆蓋，那么需要將其中的一個(gè)點(diǎn)進(jìn)展刪除1.在一個(gè)區(qū)域內(nèi)，請(qǐng)?jiān)O(shè)計(jì)算法將有效的點(diǎn)進(jìn)展輸出(盡可能多的點(diǎn))?2.假如區(qū)域足夠大，點(diǎn)足夠多，算法會(huì)出現(xiàn)性能的瓶頸，請(qǐng)?jiān)O(shè)計(jì)詳細(xì)的算法來(lái)說(shuō)明并解決問(wèn)題?百度校園招聘筆試題一、簡(jiǎn)答題1、OSI的七層模型。(10分)OSI的七層模型如下列圖所示：2、請(qǐng)列舉下不同進(jìn)程之間共享數(shù)據(jù)的方式(至少舉出三種)。(10分)1、文件映射(Memory-Mapped Files)能使進(jìn)程把文件內(nèi)容當(dāng)作進(jìn)程地址

3、間一塊內(nèi)存那樣來(lái)對(duì)待2、共享內(nèi)存(Shared Memory)實(shí)際就是文件映射的一種特殊情況3、命名管道(Named Pipe)是效勞器進(jìn)程和一個(gè)或多個(gè)客戶進(jìn)程之間通信的單向或雙向管道4、郵件槽(Mailslots)提供進(jìn)程間單向通信才能，任何進(jìn)程都能建立郵件槽成為郵件槽效勞器5、剪貼板(Clipped Board)為不同應(yīng)用程序之間共享不同格式數(shù)據(jù)提供了一條捷徑6、動(dòng)態(tài)連接庫(kù)(DLL)中的全局?jǐn)?shù)據(jù)可以被調(diào)用DLL的所有進(jìn)程共享3、請(qǐng)描繪下TCP和UDP的差異，并且各列舉出一個(gè)上層協(xié)議。(10分)TCP傳輸控制協(xié)議,提供的是面向連接、可靠的字節(jié)流效勞。當(dāng)客戶和效勞器彼此交換數(shù)據(jù)前，必須先在雙方

4、之間建立一個(gè)TCP連接，之后才能傳輸數(shù)據(jù)。TCP提供超時(shí)重發(fā)，丟棄重復(fù)數(shù)據(jù)，檢驗(yàn)數(shù)據(jù)，流量控制等功能，保證數(shù)據(jù)能從一端傳到另一端。UDP用戶數(shù)據(jù)報(bào)協(xié)議，是一個(gè)簡(jiǎn)單的面向數(shù)據(jù)報(bào)的運(yùn)輸層協(xié)議。UDP不提供可靠性，它只是把應(yīng)用程序傳給IP層的數(shù)據(jù)報(bào)發(fā)送出去，但是并不能保證它們能到達(dá)目的地。由于UDP在傳輸數(shù)據(jù)報(bào)前不用在客戶和效勞器之間建立一個(gè)連接，且沒(méi)有超時(shí)重發(fā)等機(jī)制，故而傳輸速度很快。經(jīng)常使用“ping”命令的原理就是向?qū)Ψ街鳈C(jī)發(fā)送UDP數(shù)據(jù)包，ftp等就是使用到的TCP協(xié)議二、算法與程序設(shè)計(jì)1、給出一個(gè)數(shù)據(jù)A=a_0,a_1,a_2a_n(其中n可變)，打印出該數(shù)值元素的所有組合。(15分)因?yàn)?/p>

5、題目要求n可變，所以不可能是n層for循環(huán)的方式，可以采用遞歸的方式來(lái)實(shí)現(xiàn)，每次取一個(gè)元素，在剩下元素的數(shù)組中遞歸，要注意遞歸完畢的條件。2、有這樣一個(gè)數(shù)組A，大小為n，相鄰元素差的絕對(duì)值都是1，如A=4,5,6,5,6,7,8,9,10,9，如今給定數(shù)組A和目的整數(shù)t，請(qǐng)找到t在A中的位置。(15分)最簡(jiǎn)單的方式是循環(huán)遍歷每一個(gè)元素之后比擬，找到t在A中的位置，此種方法效率最低;改良：因?yàn)橄噜徳夭畹慕^對(duì)值都是1，那么任意兩個(gè)元素相距的位置至少是兩元素差的絕對(duì)值個(gè)，假設(shè)要找的元素是t，t和a(0)的差為y1=abs(t-a0),那么t和a0的間隔 至少是y1，再求一次差值y2=abs(t-a

6、y1),t和ay1+y2的間隔 至少是y2，繼續(xù)向后查找，直到相等為止，此種方法效率較前一種高3、有一顆二叉樹，定義樹的高度為從根到葉子節(jié)點(diǎn)的最長(zhǎng)間隔 ，樹的寬度為每層節(jié)點(diǎn)的最大值，樹的面積定義為高度和寬度的乘積。寫一個(gè)函數(shù)計(jì)算一個(gè)二叉樹的面積。(15分)廣度遍歷求樹的寬度，深度遍歷求樹的高度，之后計(jì)算面積歷年網(wǎng)易校園招聘筆試題1、假設(shè)進(jìn)棧次序是e1, e2, e3, e4，那可能的出棧次序是A、e2, e4, e3, e1B、e2, e3, e4, e1C、e3, e2, e4, e1D、e1, e2, e4, e3給定入棧順序，求出可能的出棧順序。(點(diǎn)評(píng)：老得掉渣得題目了，只要小心點(diǎn)都沒(méi)有

7、問(wèn)題)2、表達(dá)式X=A+B_(C-D)/E的后綴表示形式可以是A、XAB+CDE/-_=B、XA+BC-DE/_=C、XABCD-_E/+=D、XABCDE+_/=分析p ：XABCD-_E/+=3.四叉樹中包含地空指針數(shù)量有多少?假設(shè)每個(gè)節(jié)點(diǎn)含有四個(gè)指向其孩子的指針，那么給定n個(gè)節(jié)點(diǎn)，其4n個(gè)指針有多少指向空?(比擬簡(jiǎn)單的題目，n個(gè)節(jié)點(diǎn)使用了的指針有n-1,所以最后的答案位4n-(n-1)=3n+1)分析p ：或者舉例說(shuō)明也行。4.那個(gè)排序算法是非穩(wěn)定的?選擇，冒泡、希爾，堆排序，快速等 (也是比擬根底的題目)A、冒泡排序 B、歸并排序 C、快速排序 D、堆排序 E、希爾排序分析p ：但凡O

8、(n2)的全部是穩(wěn)定排序，O(nlogn)的全部是非穩(wěn)定排序。5.根據(jù)函數(shù)，賦予參數(shù)值，寫輸出。請(qǐng)問(wèn)func(0 x7f530829)的返回值是int func(unsigned int i)unsigned int temp = i;temp = (temp 0 x55555555) + (temp 0 xaaaaaaaa)1temp = (temp 0 x33333333) + (temp 0 xcccccccc)2temp = (temp 0 x0f0f0f0f) + (temp 0 xf0f0f0f0)4temp = (temp 0 xff00ff) + (temp 0 xff00ff

9、00)8temp = (temp 0 xffff) + (temp 0 xffff0000)16return temp;A、15 B、16 C、17 D、18分析p ：函數(shù)實(shí)現(xiàn)的是求二進(jìn)制表示的時(shí)候，1的個(gè)數(shù)，一共15個(gè)最開場(chǎng)把每一個(gè)位看做一個(gè)節(jié)點(diǎn)，相鄰節(jié)點(diǎn)值相加，結(jié)果用兩個(gè)位表示。然后每?jī)蓚€(gè)位看做一個(gè)節(jié)點(diǎn)，相鄰節(jié)點(diǎn)值相加，結(jié)果用四個(gè)位表示。以此類推，直到只剩下一個(gè)節(jié)點(diǎn)。6.進(jìn)程與線程的區(qū)別：系統(tǒng)調(diào)度是對(duì)進(jìn)程還是線程，線程與進(jìn)程共享的內(nèi)存空間、公共地址空間等;A.操作系統(tǒng)只調(diào)度進(jìn)程，不調(diào)度線程B.線程共享內(nèi)存地址空間，進(jìn)程不共享C.線程間可共享內(nèi)存數(shù)據(jù)，但進(jìn)程不可以D.進(jìn)程可以通過(guò)IPC通信,

10、但線程不可以7.內(nèi)存管理：段頁(yè)式管理，地址映射表是?(操作系統(tǒng)方面的知識(shí)也不能掉以輕心呀)A. 每個(gè)作業(yè)或進(jìn)程一張段表，一張頁(yè)表B. 每個(gè)作業(yè)或進(jìn)程的每個(gè)段一張段表，一張頁(yè)表C. 每個(gè)作業(yè)或進(jìn)程一張段表，每個(gè)段一張頁(yè)表D. 每個(gè)作業(yè)一張頁(yè)表，每個(gè)段一張段表8、關(guān)于TCP協(xié)議，下面哪種說(shuō)法是錯(cuò)誤的A、TCP關(guān)閉連接過(guò)程中，兩端的socket都會(huì)經(jīng)過(guò)TIME_WAIT狀態(tài)B、對(duì)一個(gè)Established狀態(tài)的TCP連接，調(diào)用shutdown函數(shù)可以讓主動(dòng)調(diào)用的一方進(jìn)入半關(guān)閉狀態(tài)C、TCP協(xié)議默認(rèn)保證了當(dāng)TCP的一端發(fā)生意外崩潰(當(dāng)機(jī)、網(wǎng)線斷開或路由器故障)，另一端能自動(dòng)檢測(cè)到連接失效D、在成功建立

11、連接的TCP上，只有在Established狀態(tài)才能收發(fā)數(shù)據(jù)，其他狀態(tài)都不可以。分析p ：tcp/ip協(xié)議的實(shí)際使用過(guò)程中的問(wèn)題：例如單方面斷開后，另一端出于哪種狀態(tài)，還有9、關(guān)于主鍵Primary Key和索引index的說(shuō)法哪些是錯(cuò)誤的?A、唯一索引的列允許為NULL值B、一個(gè)關(guān)系表中的外鍵必定是另一表中的主鍵C、一個(gè)表中只能有一個(gè)唯一性索引D、索引主要影響查詢過(guò)程，對(duì)數(shù)據(jù)的插入影響不大分析p ：數(shù)據(jù)庫(kù)方面的知識(shí)：主鍵和索引的根本定義及其性質(zhì)，例如主鍵在表中是否唯一，索引的速度以及對(duì)表的改變的影響;無(wú)論是唯一索引還是非唯一索引，索引列都允許取NULL值10、數(shù)據(jù)庫(kù)的事務(wù)隔離級(jí)別一般分為4個(gè)

12、級(jí)別，其中可能發(fā)生“不可重復(fù)讀”的事物級(jí)別有A、SERIALIZABLEB、READ MITTEDC、READ UNMITTEDD、REPEATABLE READ分析p 數(shù)據(jù)庫(kù)：數(shù)據(jù)庫(kù)的不可重復(fù)訪問(wèn)異常，四種事務(wù)隔離級(jí)別中哪些可以防止該類異常?各隔離級(jí)別對(duì)各種異常的控制才能LU喪失更新 DR臟讀 NRR非重復(fù)讀 SLU二類喪失更新 PR幻像讀 未提交讀 RU Y Y Y Y Y 提交讀 RC N N Y Y Y 可重復(fù)讀 RR N N N N Y 串行讀 S N N N N Y11、假如F(n)為該數(shù)列的第n項(xiàng)，那么這句話可以寫成如下形式：F(1)=1，F(xiàn)(2)=1，F(xiàn)(n)=F(n-1)+F

13、(n-2) (n=3)請(qǐng)實(shí)現(xiàn)該函數(shù)F(n)的求解，并給出算法復(fù)雜度，要求算法復(fù)雜度小于O(n2)。思路：使用滾動(dòng)數(shù)組可以保存以前保存的結(jié)果，加快速度，減少空間復(fù)雜度。int Fib(int index)if(index1)return-1;int a1=1,a2=1,a3=1;for(int i=0;ia3=a1+a2;a1=a2;a2=a3;return a3;第二 局部(必做)：程序設(shè)計(jì)1、下面的程序的輸出是什么?#includeint main(void)int n;char y10 = “ntse”;char _x = y;n = strlen(x_x = xn;x+;printf(“

14、x=%sn”,xprintf(“y=%sn”,yreturn 0;輸出：x=tsey=因?yàn)閚=4，那么_x = xn; 的功能是將x指向的第一個(gè)字符n修改為0，這樣y字符串就完畢了，所以第二輸出為空，x+操作后，x指向第二個(gè)字符t，所以第一個(gè)輸出為：tse。2、請(qǐng)給出下面程序的輸出結(jié)果，并說(shuō)明原因。#include#includeusing namespace std;templateclass arraypublic:array(int sizesize_t getVectorSizereturn _data.size(size_t getSizereturn _size;public:ve

15、ctor _data;size_t _size;templatearray:array(int size) : _size(size) , _data(_size) int main(void)array _arr = new array(3coutcoutreturn 0;12.寫一個(gè)程序來(lái)確定系統(tǒng)是大端形式還是小端形式;13.編程實(shí)現(xiàn)采用位操作來(lái)實(shí)現(xiàn)整數(shù)的加法操作。14. 圖的矩陣表示法，圖的深度優(yōu)先遍歷，算法思路及其實(shí)現(xiàn)。16.fork函數(shù)的用法。詳細(xì)題目為：#include#include#includeint main(void)int i;for(i=0; i2; i+)fork(

16、printf(“-”fflush(stdoutreturn 0;6個(gè)-17.spin lock原理：先來(lái)一些代碼吧!void initlock(volatile int_ lock_status)_lock_status = 0;void lock(volatile int_ lock_status)while(test_and_set(lock_status = =1void unlock(volatile int_ lock_status)_lock_status = 0;問(wèn)題：volatile的作用?lock函數(shù)優(yōu)化(針對(duì)在多cpu上進(jìn)步cpu cache)?上面的缺陷(內(nèi)存形式上的)?

17、volatile的作用： 作為指令關(guān)鍵字，確保本條指令不會(huì)因編譯器的優(yōu)化而省略，且要求每次直接讀值。假如沒(méi)有volatile，根本上會(huì)導(dǎo)致這樣的結(jié)果：要么無(wú)法編寫多線程程序，要么編譯器失去大量?jī)?yōu)化的時(shí)機(jī)。18.給定一個(gè)宏大的文件，如何從中選出k行，隨處輸出k行到文件中。要求每一行出現(xiàn)的概率都相等。設(shè)計(jì)算法、說(shuō)明思路，算法復(fù)雜度。19.win32中WM_Quit的作用是什么?20.比擬mutex和臨街區(qū)之間的區(qū)別，并說(shuō)明其使用場(chǎng)景。21.多線程編程，如何平安退出線程。還有網(wǎng)易數(shù)據(jù)挖掘方面的題目，這次數(shù)據(jù)挖掘的題目比擬新奇，都是簡(jiǎn)答題。如下：1，簡(jiǎn)述你對(duì)數(shù)據(jù)與處理的認(rèn)識(shí);2，簡(jiǎn)述你對(duì)中文分詞的理解，