搜狐 2022 C++工程師面試題（應(yīng)聘 求職 面試準(zhǔn)備資料）

1、 搜狐 2022 C+工程師面試題第1題： 一、單選題 1、假設(shè)整數(shù)0 x12345678 存放在內(nèi)存地址0 x0開頭的連續(xù)四個(gè)字節(jié)中 (即地址0 x0到 0 x3). 那么在以Little Endian字節(jié)序存儲(chǔ)的memory中,地址0 x3的地方存放的字節(jié)是: A、0 x12 B、0 x34 C、0 x56 D、0 x78 1、A a) Little-Endian就是低位字節(jié)排放在內(nèi)存的低地址端， 高位字節(jié)排放在內(nèi)存的高地址端。 b) Big-Endian就是高位字節(jié)排放在內(nèi)存的低地址端，低位字節(jié)排放在內(nèi)存的高地址端。 c) 網(wǎng)絡(luò)字節(jié)序：TCP/IP各層協(xié)議將字節(jié)序定義為Big-Endia

2、n，因此TCP/IP協(xié)議中使用的字節(jié)序通常稱之為網(wǎng)絡(luò)字節(jié)序。 假如是Little-Endian：0 x0-0 x3內(nèi)存分別存放的是：0 x78、0 x56、0 x34、0 x12； 假如是 Big-Endian ：0 x0-0 x3內(nèi)存分別存放的是：0 x12、0 x34、0 x56、0 x78； 第2題： 2、以下代碼輸出的是_? int foo(int x,int y) if(x=0|y=0) return 1; return 3*foo(x-1,y/2); coutfoo(3,5)endl; A、81 B、27 C、9 D、3 2、B 遞歸：3*3*3*f(0,0）=3*3*3*1=27

3、。 第3題： 3、給定下列程序，那么執(zhí)行printf（%n，foo(20,13); 的輸出結(jié)果是多少？ int foo （int x，int y ） if （x0y0） return 1； return 3*foo（x-6，y/2）； A、3 B、9 C、27 D、81 3、D 第4題： 4、假如x=2022，下面函數(shù)的返回值是（） int fun(unsigned int x) int n=0; while(x+1) n+; x=x|(x+1); return n; A、20 B、21 C、23 D、25 4、C 返回值為：23 2022對(duì)應(yīng)的二進(jìn)制為：0000 0000 000 0000

4、0000 0111 1101 1110 而x|（x+1）的作用是對(duì)一個(gè)數(shù)中二進(jìn)制0的個(gè)數(shù)進(jìn)行統(tǒng)計(jì) 例如本題： 第一次循環(huán)：0000 0000 000 0000 0000 0111 1101 1110 |0000 0000 000 0000 0000 0111 1101 1110 =0000 0000 000 0000 0000 0111 1101 1111 其次次循環(huán)：0000 0000 000 0000 0000 0111 1101 1111 |0000 0000 000 0000 0000 0111 1110 0000 =0000 0000 000 0000 0000 0111 1111

5、1111 . . . 每循環(huán)一次0的數(shù)量減一 ，直到溢出 所以2022二進(jìn)制中一共有23個(gè)0則返回值為23 第5題： 5、以下代碼的輸出是（） int a5=1,2,3,4,5; int *ptr=(int*)(a+1); printf(%d,%d,*(a+1),*(ptr-1); A、1，2 B、2，5 C、2，1 D、1，5 5、B a 代表的是int * 每次步長(zhǎng)為一個(gè)int a 代表的是 int* 每次步長(zhǎng)為所指向的數(shù)組的大小 故 ptr 指向的是數(shù)組a最終一個(gè)元素的下一個(gè)元素 所以ptr-1指向的是數(shù)組a的最終一個(gè)元素 a+1指向的是數(shù)組a的其次個(gè)元素 所以正確答案是B 第6題： 6

6、、在linux下64位c程序，請(qǐng)計(jì)算輸出的三個(gè)sizeof分別是（） void func(char str_arg100) coutsizeof(str_arg)endl; int main(int argc,char* argv) char str=Hello; char *p=str; coutsizeof(str)endl; coutsizeof(p)endl; func(test); return 0; A、5，5，8 B、6，6，4 C、6，8，4 D、6，8，8 6、D 這里主要是區(qū)分sizeof運(yùn)算符的測(cè)量對(duì)象sizeof(str)測(cè)量的是字符數(shù)組的占用長(zhǎng)度，留意字符串后還有個(gè)0

7、，所以是6sizeof(p)測(cè)量的是指針的占用長(zhǎng)度，64位系統(tǒng)下是8字節(jié)sizeof(str_arg)測(cè)量的是指針長(zhǎng)度，由于這里是形參。 第7題： 7、下面關(guān)于迭代器失效的描述哪個(gè)是錯(cuò)誤的（） A、vector的插入操作不會(huì)導(dǎo)致迭代器失效 B、map的插入操作不會(huì)導(dǎo)致迭代器失效 C、vector的刪除操作只會(huì)導(dǎo)致指向被刪除元素及后面的迭代器失效 D、map的刪除操作只會(huì)導(dǎo)致指向被刪除元素的迭代器失效 7、A 由于由 Vector 的 iterator 和 listIterator 方法所返回的迭代器是快速失敗的 ：假如在迭代器創(chuàng)建后的任意時(shí)間從結(jié)構(gòu)上修改了向量（通過迭代器自身的 remove

8、或 add 方法之外的任何其他方式），則迭代器將拋出 ConcurrentModificationException。 第8題： 8、函數(shù)fun的聲明為int fun(int *p4),以下哪個(gè)變量可以作為fun的合法參數(shù)（） A、int a44; B、int *a; C、int *a4 D、int (*a)4; 8、B 可以看出fun函數(shù)的形參是一個(gè)指針數(shù)組，也就是指針指向一個(gè)地址，地址中存放的內(nèi)容也是指針。A，二維數(shù)組，不符合B，二級(jí)指針，也就是指針指向的內(nèi)容也還是存放指針的，符合C，二級(jí)指針數(shù)組，數(shù)組的內(nèi)容是二級(jí)指針，不符合D，數(shù)組指針，不符合 第9題： 9、下面說法正確的是（） A、C

9、+已有的任何運(yùn)算符都可以重載 B、const對(duì)象只能調(diào)用const類型成員函數(shù) C、構(gòu)造函數(shù)和析構(gòu)函數(shù)都可以是虛函數(shù) D、函數(shù)重載返回值類型必需相同 9、B A不能重載.，由于.在類中對(duì)任何成員都有意義，已經(jīng)成為標(biāo)準(zhǔn)用法。 不能重載?:，由于這個(gè)運(yùn)算符對(duì)于類對(duì)象來說沒有實(shí)際意義，相反還會(huì)引起歧義 還有： C 構(gòu)造函數(shù) 不能是虛函數(shù)。 D 函數(shù)重載只跟 參數(shù)類型 和參數(shù)個(gè)數(shù) 有關(guān)。 第10題： 10、典型的創(chuàng)建Windows窗口過程的流程為（） A、注冊(cè)窗口類-創(chuàng)建窗口-顯示窗口-更新窗口-消息循環(huán) B、注冊(cè)窗口類-創(chuàng)建窗口-更新窗口-顯示窗口-消息循環(huán) C、創(chuàng)建窗口-注冊(cè)窗口類-更新窗口-顯示

10、窗口-消息循環(huán) D、創(chuàng)建窗口-注冊(cè)窗口類-顯示窗口-更新窗口-消息循環(huán) 10、A 在屏幕上顯示一個(gè)窗口的過程一般有以下步驟，這就是主程序的結(jié)構(gòu)流程：（1）得到應(yīng)用程序的句柄（GetModuleHandle）。（2）注冊(cè)窗口類(RegisterClassEx)。在注冊(cè)之前，要先填寫RegisterClassEx的參數(shù)WNDCLASSEX結(jié)構(gòu)。（3）建立窗口（CreateWindowEx）。（4）顯示窗口（ShowWindows）。（5）刷新窗口客戶區(qū)（UpdateWindow）。（6）進(jìn)入無限的消息獵取和處理的循環(huán)。首先獵取消息（GetMessage），假如有消息到達(dá)，則將消息分派到回調(diào)函數(shù)處理

11、（DispatchMessage），假如消息是WM_QUIT，則退出循環(huán)。 第11題： 11、下面哪個(gè)API返回的不屬于windows內(nèi)核對(duì)象（） A、CreateFile B、CreateSemaphore C、CreateDC D、eateEvent 11、C ABD選項(xiàng)是內(nèi)核對(duì)象：大事對(duì)象HANDLE CreateEvent();文件對(duì)象HANDLE CreateFile();信號(hào)量對(duì)象HANDLE CreateSemaphore();C選項(xiàng)是GDI對(duì)象。設(shè)備上下文（HDC) CreateDC 第12題： 12、用戶雙擊鼠標(biāo)時(shí)產(chǎn)生的消息序列，下面正確的是（） A、WM_LBUTTONDO

12、WN，WM_LBUTTONUP，WM_LBUTTONDOWN，WM_LBUTTONUP B、WM_LBUTTONDOWN，WM_LBUTTONUP，WM_LBUTTONUP，WM_LBUTTONDBLCLK C、WM_LBUTTONDOWN，WM_LBUTTONUP，WM_LBUTTONDOWN，WM_LBUTTONDBLCLK D、WM_LBUTTONDOWN，WM_LBUTTONUP，WM_LBUTTONDBLCLK，WM_LBUTTONUP 12、D 雙擊即點(diǎn)擊左鍵兩下，第一次觸發(fā)LBUTTONDOWN和LBUTTONUP，其次次點(diǎn)擊時(shí)觸發(fā)雙擊大事LBUTTONDBLCLK（double

13、click），放掉再觸發(fā)LBUTTONUP 第13題： 13、以下關(guān)于線程以下描述正確的是（） 1.windows線程創(chuàng)建時(shí)，默認(rèn)綁定在1個(gè)特定的CPU上 2.可采納SetThreadAffinityMask接口設(shè)置線程與某個(gè)cpu綁定 3._beginthreadex比CreateThread創(chuàng)建線程平安是由于使用_beginthreadex會(huì)創(chuàng)建一個(gè)_tiddata,在調(diào)用一些諸如strtok函數(shù)時(shí)會(huì)將需要愛護(hù)的數(shù)據(jù)存入_tiddata 4.使用_beginthread創(chuàng)建線程時(shí)，線程執(zhí)行函數(shù)必需為_cdecl約束規(guī)范，而_beginthreadex指定的線程執(zhí)行函數(shù)必需為_stdcall

14、 A、1，2 B、1，3 C、1 D、以上都不正確 13、D 解釋：1：不正確。windows線程創(chuàng)建時(shí)，不會(huì)綁定在特定的CPU上，需要手動(dòng)綁定，或者調(diào)用 SetThreadAffinityMask接口進(jìn)行綁定； 2：正確。參考 /beyond_cn/article/details/15813361 3：不正確。參考2的鏈接。歡迎各位訂正。 4：正確。參考msdn: _beginthread函數(shù)可創(chuàng)建在start_address開頭執(zhí)行例程的線程。 start_address中的例程必需使用 _cdecl （用于本機(jī)代碼）或 _clrcall （用于托管代碼）調(diào)用商定，并且應(yīng)沒有返回值。 傳遞

15、給 _beginthreadex 的 start_address 中的例程必需使用 _stdcall （用于本機(jī)代碼）或 _clrcall （用于托管代碼）調(diào)用商定，并且必需返回線程退出代碼。 所以，通過1，就能選出D。 第14題： 14、以下哪些線程同步鎖可以為遞歸鎖 1.信號(hào)量 2.讀寫鎖 3.互斥量 4.大事 5.臨界區(qū)（Critical Section） A、1，3，4，5 B、5 C、3，5 D、1，3，5 14、C 進(jìn)程/線程同步方法 常見的進(jìn)程/線程同步方法有互斥鎖（或稱互斥量Mutex）、讀寫鎖（rdlock）、條件變量（cond）、信號(hào)量（Semophore）等。 在wind

16、ows系統(tǒng)中，臨界區(qū)（Critical Section）和大事對(duì)象（Event）也是常用的同步方法。 遞歸鎖/非遞歸鎖 Mutex可以分為遞歸鎖（recursive mutex）和非遞歸鎖（non-recursive mutex）。 遞歸鎖也叫可重入鎖（reentrant mutex），非遞歸鎖也叫不行重入鎖（non-reentrant mutex）。 二者唯一的區(qū)分是： 同一個(gè)線程可以多次獵取同一個(gè)遞歸鎖，不會(huì)產(chǎn)生死鎖。 假如一個(gè)線程多次獵取同一個(gè)非遞歸鎖，則會(huì)產(chǎn)生死鎖。 Windows下的Mutex和Critical Section是可遞歸的。 Linux下的pthread_mutex_t

17、鎖是默認(rèn)是非遞歸的。可以通過設(shè)置PTHREAD_MUTEX_RECURSIVE屬性，將pthread_mutex_t鎖設(shè)置為遞歸鎖。 第15題： 15、關(guān)于sendmessage和postmessage的區(qū)分，下面的說法錯(cuò)誤的是（） A、postmessage發(fā)出消息后，將消息放到消息隊(duì)列中，立刻返回 B、sendmessage發(fā)出消息后，始終等到該消息執(zhí)行完畢，才返回 C、用sendmessage給其他線程創(chuàng)建的窗口發(fā)送消息時(shí)，消息也會(huì)進(jìn)消息隊(duì)列 D、用2個(gè)函數(shù)只能給當(dāng)前進(jìn)程的窗口發(fā)送消息 15、D A：PostMessage只把消息放入隊(duì)列，不管其他程序是否處理都返回，然后連續(xù)執(zhí)行，這是個(gè)

18、異步消息投放函數(shù)。 B:SendMessage必需等待其他程序處理消息完了之后才返回，連續(xù)執(zhí)行，這是個(gè)同步消息投放函數(shù)。 C:當(dāng)某線程調(diào)用sendmessage給別的線程創(chuàng)建的窗口時(shí)，發(fā)送的消息首先追加到接收線程的發(fā)送消息隊(duì)列，發(fā)送線程處于空閑狀態(tài)，等待接收線程處理完他的消息返回給發(fā)送線程的應(yīng)答隊(duì)列，等到后發(fā)送線程被喚醒取得應(yīng)答隊(duì)列的消息 (就是處理完消息的返回值)，連續(xù)執(zhí)行。 D:sendmessage和postmessage都可以給其他線程發(fā)送消息 第16題： 16、關(guān)于WM_COPYDATA消息的處理，下面描述錯(cuò)誤的是（） A、可以在不同進(jìn)程之間傳遞少量只讀數(shù)據(jù) B、只能通過sendme

19、ssage方式來發(fā)送該消息 C、只能在窗口過程函數(shù)中處理該消息 D、可以在消息隊(duì)列或窗口過程函數(shù)中處理該消息 16、C A：WM_COPYDATA消息的主要目的是允許在進(jìn)程間傳遞只讀數(shù)據(jù)。Windows在通過WM_COPYDATA消息傳遞期間，不供應(yīng)繼承同步方式。 B;該消息只能由SendMessage()來發(fā)送，而不能使用PostMessage()。由于系統(tǒng)必需管理用以傳遞數(shù)據(jù)的緩沖區(qū)的生命期，假如使用了PostMessage()，數(shù)據(jù)緩沖區(qū)會(huì)在接收方（線程）有機(jī)會(huì)處理該數(shù)據(jù)之前，就被系統(tǒng)清除和回收。 D:可以在消息隊(duì)列或窗口過程函數(shù)中處理該消息 第17題： 17、常用的windows進(jìn)入點(diǎn)

20、函數(shù)wWinMain共有四個(gè)參數(shù)，其中不包括以下哪種類型的參數(shù)（） A、int B、char* C、PWSTR D、HINSTANCE 17、C WinMain 函數(shù)的原型聲明如下： int WINAPI WinMain( HINSTANCE hInstance , / handle to current instance HINSTANCE hPrevInstance , / handle to previous instance LPSTR lpCmdLine , / command line int nCmdShow / show state ); 第一個(gè)參數(shù) hInstance 表示該

21、程序當(dāng)前運(yùn)行的實(shí)例的句柄，這是一個(gè)數(shù)值。 其次個(gè)參數(shù) hPrevInstance 表示當(dāng)前實(shí)例的前一個(gè)實(shí)例的句柄。第三個(gè)參數(shù) lpCmdLine 是一個(gè)以空終止的字符串，指定傳遞給應(yīng)用程序的命令行參數(shù)。第四個(gè)參數(shù) nCmdShow 指定程序的窗口應(yīng)當(dāng)如何顯示，例如最大化、最小化、隱蔽等。 第18題： 18、下列windows消息中，優(yōu)先級(jí)相對(duì)較低的是哪一個(gè)（） A、WM_MOUSEMOVE B、WM_TIMER C、WM_CHAR D、WM_WINDOWPOSCHANGED 18、B WM_TIMER消息的優(yōu)先級(jí)最低，所以在有其他消息的狀況下，WM_TIMER消息得不處處理 A:WM_MOUS

22、EMOVE消息在鼠標(biāo)移動(dòng)時(shí)被發(fā)送至已獲焦點(diǎn)的窗口 B:Windows定時(shí)器是一種周期性的消息產(chǎn)生裝置，它會(huì)每隔一段指定時(shí)間發(fā)送一次定時(shí)消息WM_TIMER。 C:未經(jīng)輸入法而直接送人程序中的字符會(huì)響應(yīng)WM_CHAR消息 D:發(fā)送此消息給那個(gè)窗口的大小和位置已經(jīng)被轉(zhuǎn)變時(shí)，來調(diào)用setwindowpos函數(shù)或其它窗口管理函數(shù) 第19題： 19、最小堆0,3,2,5,7,4,6,8,在刪除堆頂元素0之后，其結(jié)果是（） A、3，2，5，7，4，6，8 B、2，3，5，7，4，6，8 C、2，3，4，5，7，8，6 D、2，3，4，5，6，7，8 19、C 依據(jù)堆的刪除規(guī)章，刪除操作只能在堆頂進(jìn)行，也就

23、是刪除0元素。然后讓最終一個(gè)節(jié)點(diǎn)放在堆頂，做向下調(diào)整工作，讓剩下的數(shù)組依舊滿意最小堆。刪除0后用8填充0的位置，為8,3,2,5,7,4,6然后8和其子節(jié)點(diǎn)3,2比較，結(jié)果2最小，將2和8交換，為：2,3,8,5,7,4,6然后8的下標(biāo)為2，其兩個(gè)孩子節(jié)點(diǎn)下標(biāo)分別為2*2+1=5,2*2+2=6也就是4和6兩個(gè)元素，經(jīng)比較，4最小，將8與4交換，為2,3,4,5,7,8,6這時(shí)候8已經(jīng)沒有孩子節(jié)點(diǎn)了，調(diào)整完成。 第20題： 20、對(duì)一個(gè)由A,B,C,D隨機(jī)組成的序列進(jìn)行哈弗曼編碼，據(jù)統(tǒng)計(jì)，各個(gè)元素的概率分別為：P(A)=0.4，P(B)=0.35，P(C)=0.2，P(D)=0.05，請(qǐng)問該編

24、碼的平均期望編碼長(zhǎng)度為（）bits？ A、1.45 B、1.7 C、1.85 D、1.92 20、C 首先要建立哈夫曼樹，然后計(jì)算平均期望編碼長(zhǎng)度：0.4*1 + 0.35*2 + 0.2*3 + 0.05*3 = 1.85 第21題： 21、設(shè)有遞歸算法如下， int x(int n) if(n=3) return 1; else return x(n-2)+x(n-4)+1; 試問計(jì)算x(x(8)時(shí)需要計(jì)算（）次x函數(shù)。 A、8 B、9 C、16 D、18 21、D x(8)=x(6)+x(4)+1 遞歸計(jì)算x(8)第一次調(diào)用 x(6)=x(4)+x(2)+1 遞歸計(jì)算x(6)其次次調(diào)用

25、x(4)= x(2)+x(0)+1 遞歸計(jì)算x(4)第三次調(diào)用 x(4)= x(2)+x(0)+1 遞歸計(jì)算x(4)第四次調(diào)用 之后再調(diào)用x()計(jì)算黑體部分的結(jié)果(5次，加上前面4次，一共9次)，最終x(8)返回值為9 接著計(jì)算x(9) x(9)=x(7)+x(5)+1 遞歸計(jì)算x(9)第一次調(diào)用 x(7)=x(5)+x(3)+1 遞歸計(jì)算x(7)其次次調(diào)用 x(5)=x(3)+x(1)+1遞歸計(jì)算x(5)第三次調(diào)用 x(5)=x(3)+x(1)+1遞歸計(jì)算x(5)第四次調(diào)用 之后再調(diào)用x()計(jì)算黑體部分的結(jié)果(5次，加上前面4次，一共9次)，最終x(8)返回值為9 所以總共調(diào)用x()的次數(shù)是

26、9+9=18 第22題： 22、設(shè)一組初始記錄關(guān)鍵字序列(Q,H,C,Y,P,A,M,S,R,D,F,X),則按字母升序的第一趟冒泡排序結(jié)束后的結(jié)果是（） A、F，H，C，D，P，A，M，Q，R，S，Y，X B、P，A，C，S，Q，D，F(xiàn)，X，R，H，M，Y C、A，D，C，R，F(xiàn)，Q，M，S，Y，P，H，X D、H，C，Q，P，A，M，S，R，D，F(xiàn)，X，Y 22、D 第一趟冒泡：從數(shù)組第一個(gè)元素到最終一個(gè)元素掃描，比較相鄰的元素，假如后一個(gè)元素小于前一個(gè)，則交換位置。第一趟結(jié)束時(shí)，最大元素到達(dá)最終一個(gè)元素位置 第23題： 23、堆排序的空間簡(jiǎn)單度是（），堆排序中構(gòu)建堆的時(shí)間簡(jiǎn)單度是（）。

27、A、(logn)，O(n) B、O(logn)，O(nlogn) C、O(1)，O(n) D、O(1)，O(nlogn) 23、C “空間簡(jiǎn)單度”指占內(nèi)存大小，堆排序每次只對(duì)一個(gè)元素操作，是就地排序，所用幫助空間O(1)，空間簡(jiǎn)單度是O（1） 在構(gòu)建堆的過程中，完全二叉樹從最下層最右邊的非終端結(jié)點(diǎn)開頭構(gòu)建，將它與其孩子進(jìn)行比較和必要的互換，對(duì)于每個(gè)非終端結(jié)點(diǎn)來說，其實(shí)最多進(jìn)行兩次比較和互換操作，因此整個(gè)構(gòu)建堆的時(shí)間簡(jiǎn)單度為O(n)。 在正式排序時(shí)，第i次取堆頂記錄重建堆需要用O(logi)的時(shí)間（完全二叉樹的某個(gè)結(jié)點(diǎn)到根結(jié)點(diǎn)的距離為?log2i?+1），并且需要取n-1次堆頂記錄，因此，重建堆

28、的時(shí)間簡(jiǎn)單度為O(nlogn)。 第24題： 24、若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別0和3。當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩 個(gè)元素后，rear和front的值分別為（） A、2和4 B、1和5 C、4和2 D、5和1 24、A 由于出隊(duì)時(shí)，front=front+1/MAXSIZE,rear不變，所以front=4入隊(duì)時(shí)，rear=rear+1/MAXSIZE,front不變，所以rear=2; 第25題： 25、如下表是用戶是否使用某產(chǎn)品的調(diào)查結(jié)果（） UID 年齡 地區(qū) 學(xué)歷 收入 用戶是否使用調(diào)查產(chǎn)品 1 低 北方 博士 低 是 2 高 北方 本

29、科 中 否 3 低 南方 本科 高 否 4 高 北方 討論生 中 是 請(qǐng)計(jì)算年齡，地區(qū)，學(xué)歷，收入中對(duì)用戶是否使用調(diào)查產(chǎn)品信息增益最大的屬性（Log230.63） A、年齡 B、地區(qū) C、學(xué)歷 D、收入 25、C 不用算一眼就能看出來，全部本科學(xué)歷都不使用調(diào)查產(chǎn)品，全部非本科學(xué)歷都使用了調(diào)查產(chǎn)品。這種可以確定的劃分導(dǎo)致信息熵為0，信息增益最大 第26題： 26、假設(shè)某算法的計(jì)算時(shí)間可用遞推關(guān)系式T(n)=2T(n/2)+n表示，則該算法的時(shí)間簡(jiǎn)單度為（） A、O(logn) B、O(n*logn) C、O(n) D、O(n2) 26、B T(n)=2k*(T(n/(2k)+k*n 2k = n

30、,k = log(n) (以2為底) T（n） = n*T(1)+n*log(n)= c*n*log(n) (c為常數(shù)) 所以是O(n*logn) 第27題： 27、基于統(tǒng)計(jì)的分詞方法為（） A、正向最大匹配法 B、逆向最大匹配法 C、最少切分 D、條件隨機(jī)場(chǎng) 27、D 目前的分詞方法歸納起來有3 類:第一類是基于語法和規(guī)章的分詞法。其基本思想就是在分詞的同時(shí)進(jìn)行句法、語義分析, 利用句法信息和語義信息來進(jìn)行詞性標(biāo)注, 以解決分詞歧義現(xiàn)象。由于現(xiàn)有的語法學(xué)問、句法規(guī)章非常籠統(tǒng)、簡(jiǎn)單, 基于語法和規(guī)章的分詞法所能達(dá)到的精確度遠(yuǎn)遠(yuǎn)還不能令人滿足, 目前這種分詞系統(tǒng)還處在試驗(yàn)階段。其次類是機(jī)械式分詞

31、法（即基于詞典）。機(jī)械分詞的原理是將文檔中的字符串與詞典中的詞條進(jìn)行逐一匹配, 假如詞典中找到某個(gè)字符串, 則匹配勝利, 可以切分, 否則不予切分?；谠~典的機(jī)械分詞法, 實(shí)現(xiàn)簡(jiǎn)潔, 有用性強(qiáng), 但機(jī)械分詞法的最大的缺點(diǎn)就是詞典的完備性不能得到保證。據(jù)統(tǒng)計(jì), 用一個(gè)含有70 000 個(gè)詞的詞典去切分含有15 000 個(gè)詞的語料庫, 仍舊有30% 以上的詞條沒有被分出來, 也就是說有4500 個(gè)詞沒有在詞典中登錄。第三類是基于統(tǒng)計(jì)的方法?；诮y(tǒng)計(jì)的分詞法的基本原理是依據(jù)字符串在語料庫中消失的統(tǒng)計(jì)頻率來打算其是否構(gòu)成詞。詞是字的組合, 相鄰的字同時(shí)消失的次數(shù)越多, 就越有可能構(gòu)成一個(gè)詞。因此字與字

32、相鄰共現(xiàn)的頻率或概率能夠較好的反映它們成為詞的可信度。最大匹配是指以詞典為依據(jù)，取詞典中最長(zhǎng)單詞為第一個(gè)次取字?jǐn)?shù)量的掃描串，在詞典中進(jìn)行掃描，這是基于詞典分詞的方法1.正向最大匹配法2.逆向最大匹配法3.最少切分法：使每一句中切出的詞數(shù)最小，這也是基于詞典分詞的方法條件隨機(jī)場(chǎng)是一個(gè)基于統(tǒng)計(jì)的序列標(biāo)記和分割的方法，屬于基于統(tǒng)計(jì)的分詞方法范疇。它定義了整個(gè)標(biāo)簽序列的聯(lián)合概率，各狀態(tài)是非*的，彼此之間可以交互，因此可以更好地模擬現(xiàn)實(shí)世界的數(shù)據(jù) 第28題： 28、下列哪個(gè)不屬于CRF模型對(duì)于HMM和MEMM模型的優(yōu)勢(shì)（） A、特征敏捷 B、速度快 C、可容納較多上下文信息 D、全局最優(yōu) 28、B 隱馬

33、爾可夫模型（Hidden Markov Model，HMM），最大熵馬爾可夫模型（Maximum Entropy Markov Model，MEMM）以及條件隨機(jī)場(chǎng)（Conditional Random Field，CRF）是序列標(biāo)注中最常用也是最基本的三個(gè)模型。HMM模型是對(duì)轉(zhuǎn)移概率和表現(xiàn)概率直接建模，統(tǒng)計(jì)共現(xiàn)概率。MEMM模型是對(duì)轉(zhuǎn)移概率和表現(xiàn)概率建立聯(lián)合概率，統(tǒng)計(jì)時(shí)統(tǒng)計(jì)的是條件概率，但MEMM簡(jiǎn)單陷入局部最優(yōu)，是由于MEMM只在局部做歸一化。RF模型中，統(tǒng)計(jì)了全局概率，在 做歸一化時(shí)，考慮了數(shù)據(jù)在全局的分布，而不是僅僅在局部歸一化，這樣就解決了MEMM中的標(biāo)記偏置（label bias）

34、的問題。CRF沒有HMM那樣嚴(yán)格的*性假設(shè)條件，因而可以容納任意的上下文信息。特征設(shè)計(jì)敏捷。（與ME一樣） 與HMM比較同時(shí)，由于CRF計(jì)算全局最優(yōu)輸出節(jié)點(diǎn)的條件概率，它還克服了最大熵馬爾可夫模型標(biāo)記偏置（Label-bias）的缺點(diǎn)。 shy;shy;與MEMM比較CRF是在給定需要標(biāo)記的觀看序列的條件下，計(jì)算整個(gè)標(biāo)記序列的聯(lián)合概率分布，而不是在給定當(dāng)前狀態(tài)條件下，定義下一個(gè)狀態(tài)的狀態(tài)分布。CRF需要訓(xùn)練的參數(shù)更多，與MEMM和HMM相比，它存在訓(xùn)練代價(jià)大、簡(jiǎn)單度高的缺點(diǎn)。 第29題： 29、假設(shè)一個(gè)完整的撲克牌有52張牌，2黑色（黑葵和梅花）和2紅色（方塊和紅心）。假如給你一副完整的牌，和

35、半副牌（1紅色和1黑色），則兩種狀況下抽兩種牌都是紅色的概率是多少（） A、1/2，1/2 B、25/102，12/50 C、50/51，24/25 D、25/51，12/25 29、B 第一種狀況 26/52 * 25/51 =25/102 其次種狀況 13/26 * 12/25=12/50 第30題： 30、在二分類問題中，當(dāng)測(cè)試集的正例和負(fù)例數(shù)量不均衡時(shí)，以下評(píng)價(jià)方案哪個(gè)是相對(duì)不合理的（）（假設(shè) precision=TP/(TP+FP),recall=TP/(TP+FN)。） A、Accuracy:(TP+TN)/all B、F-value:2*recall*precision/(recall+precision) C、G-mean:sqrt(precision*recall) D、AUC:曲線下面積 30、A 題目提到測(cè)試集正例和負(fù)例數(shù)量不均衡，那么假設(shè)正例數(shù)量很少占10%，負(fù)例數(shù)量占大部分90%。 而且算法能