搜狐 2021 C++工程師面試題

第1題：

?一、單選題

1、假設整數0x12345678 存放在內存地址0x0開(kāi)始的連續四個(gè)字節中 (即地址0x0到 0x3). 那么在以L(fǎng)ittle Endian字節序存儲的memory中,地址0x3的地方存放的字節是:??????

A、0x12

B、0x34

C、0x56

D、0x78

?1、A

a) Little-Endian就是低位字節排放在內存的低地址端， ? 高位字節排放在內存的高地址端。

b) ?Big-Endian就是高位字節排放在內存的低地址端，低位字節排放在內存的高地址端。

c) ? 網(wǎng)絡(luò )字節序：TCP/IP各層協(xié)議將字節序定義為Big-Endian，因此TCP/IP協(xié)議中使用的字節序通常稱(chēng)之為網(wǎng)絡(luò )字節序。

如果是?Little-Endian：0x0-0x3內存分別存放的是：0x78、0x56、0x34、0x12； ? ? ??

如果是? ? ? ? Big-Endian ? ? ：0x0-0x3內存分別存放的是：0x12、0x34、0x56、0x78； ? ? ?? ??

第2題：

?2、以下代碼輸出的是__?

int foo(int x,int y)

{

????if(x<=0||y<=0)? return 1;

????return 3*foo(x-1,y/2);

}

cout<

A、81

B、27

C、9

D、3

?2、B

遞歸：3*3*3*f(0,0）=3*3*3*1=27。

第3題：

?3、給定下列程序，那么執行printf（"%\n"，foo(20,13)); 的輸出結果是多少？

int foo （int x，int y ）

{

????if （x＜＝0││y＜＝0）

????????return 1；

????return 3*foo（x-6，y/2）；

}????

A、3

B、9

C、27

D、81

?3、D

第4題：

?4、如果x=2021，下面函數的返回值是（）

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

2021對應的二進(jìn)制為：0000 0000 000 0000 0000 0111 1101 1110

而x|（x+1）的作用是對一個(gè)數中二進(jìn)制0的個(gè)數進(jìn)行統計

例如本題：

第一次循環(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 1111

.

.

.

每循環(huán)一次0的數量減一 ，直到溢出?

所以2021二進(jìn)制中一共有23個(gè)0則返回值為23

第5題：

?5、以下代碼的輸出是（）

int a[5]={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 * 每次步長(cháng)為一個(gè)int

&a 代表的是 int[]* 每次步長(cháng)為所指向的數組的大小

故

ptr 指向的是數組a最后一個(gè)元素的下一個(gè)元素

所以ptr-1指向的是數組a的最后一個(gè)元素

a+1指向的是數組a的第二個(gè)元素

所以正確答案是B

第6題：

?6、在linux下64位c程序，請計算輸出的三個(gè)sizeof分別是（）

void func(char str_arg[100])

{

?????cout<

}

int main(int argc,char* argv[])

{

?????char str[]="Hello";

?????char *p=str;

?????cout<

?????cout<

?????func("test");

?????return 0;

}?????

A、5，5，8

B、6，6，4

C、6，8，4

D、6，8，8

?6、D?
這里主要是區分sizeof運算符的測量對象
sizeof(str)測量的是字符數組的占用長(cháng)度，注意字符串后還有個(gè)\0，所以是6
sizeof(p)測量的是指針的占用長(cháng)度，64位系統下是8字節
sizeof(str_arg)測量的是指針長(cháng)度，因為這里是形參。

第7題：

?7、下面關(guān)于迭代器失效的描述哪個(gè)是錯誤的（）???????

A、vector的插入操作不會(huì )導致迭代器失效

B、map的插入操作不會(huì )導致迭代器失效

C、vector的刪除操作只會(huì )導致指向被刪除元素及后面的迭代器失效

D、map的刪除操作只會(huì )導致指向被刪除元素的迭代器失效

?7、A

因為由 Vector 的 iterator 和 listIterator ?方法所返回的迭代器是快速失敗的 ：如果在迭代器創(chuàng )建后的任意時(shí)間從結構上修改了向量（通過(guò)迭代器自身的 remove 或 add ?方法之外的任何其他方式），則迭代器將拋出 ConcurrentModificationException。

第8題：

8、函數fun的聲明為int fun(int *p[4]),以下哪個(gè)變量可以作為fun的合法參數（）??????

A、int a[4][4];

B、int **a;

C、int **a[4]

D、int (*a)[4];

8、B
可以看出fun函數的形參是一個(gè)指針數組，也就是指針指向一個(gè)地址，地址中存放的內容也是指針。
A，二維數組，不符合
B，二級指針，也就是指針指向的內容也還是存放指針的，符合
C，二級指針數組，數組的內容是二級指針，不符合
D，數組指針，不符合

第9題：

?9、下面說(shuō)法正確的是（）??????????

A、C++已有的任何運算符都可以重載

B、const對象只能調用const類(lèi)型成員函數

C、構造函數和析構函數都可以是虛函數

D、函數重載返回值類(lèi)型必須相同

?9、B

A?不能重載‘.’，因為‘.’在類(lèi)中對任何成員都有意義，已經(jīng)成為標準用法。? ?
不能重載??:?，因為這個(gè)運算符對于類(lèi)對象來(lái)說(shuō)沒(méi)有實(shí)際意義，相反還會(huì )引起歧義?

還有：：

C 構造函數 不能是虛函數。?

D 函數重載只跟 參數類(lèi)型 和參數個(gè)數 有關(guān)。

第10題：

?10、典型的創(chuàng )建Windows窗口過(guò)程的流程為（）?????????

A、注冊窗口類(lèi)->創(chuàng )建窗口->顯示窗口->更新窗口->消息循環(huán)

B、注冊窗口類(lèi)->創(chuàng )建窗口->更新窗口->顯示窗口->消息循環(huán)

C、創(chuàng )建窗口->注冊窗口類(lèi)->更新窗口->顯示窗口->消息循環(huán)

D、創(chuàng )建窗口->注冊窗口類(lèi)->顯示窗口->更新窗口->消息循環(huán)

?10、A
在屏幕上顯示一個(gè)窗口的過(guò)程一般有以下步驟，這就是主程序的結構流程：
（1）得到應用程序的句柄（GetModuleHandle）。
（2）注冊窗口類(lèi)(RegisterClassEx)。在注冊之前，要先填寫(xiě)RegisterClassEx的參數WNDCLASSEX結構。
（3）建立窗口（CreateWindowEx）。
（4）顯示窗口（ShowWindows）。
（5）刷新窗口客戶(hù)區（UpdateWindow）。
（6）進(jìn)入無(wú)限的消息獲取和處理的循環(huán)。首先獲取消息（GetMessage），如果有消息到達，則將消息分派到回調函數處理（DispatchMessage），如果消息是WM_QUIT，則退出循環(huán)。

第11題：

?11、下面哪個(gè)API返回的不屬于windows內核對象（）????????????

A、CreateFile

B、CreateSemaphore

C、CreateDC

D、eateEvent

?11、C
ABD選項是內核對象：事件對象HANDLE CreateEvent();文件對象HANDLE CreateFile();信號量對象HANDLE CreateSemaphore();
C選項是GDI對象。設備上下文（HDC) ?CreateDC

第12題：

?12、用戶(hù)雙擊鼠標時(shí)產(chǎn)生的消息序列，下面正確的是（）????????????

A、WM_LBUTTONDOWN，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（doubleclick），放掉再觸發(fā)LBUTTONUP

第13題：

?13、以下關(guān)于線(xiàn)程以下描述正確的是（）

1.windows線(xiàn)程創(chuàng )建時(shí)，默認綁定在1個(gè)特定的CPU上

2.可采用SetThreadAffinityMask接口設置線(xiàn)程與某個(gè)cpu綁定

3._beginthreadex比CreateThread創(chuàng )建線(xiàn)程安全是因為使用_beginthreadex會(huì )創(chuàng )建一個(gè)_tiddata,在調用一些諸如strtok函數時(shí)會(huì )將需要保護的數據存入_tiddata

4.使用_beginthread創(chuàng )建線(xiàn)程時(shí)，線(xiàn)程執行函數必須為_(kāi)cdecl約束規范，而_beginthreadex指定的線(xiàn)程執行函數必須為_(kāi)stdcall???

A、1，2

B、1，3

C、1

D、以上都不正確

?13、D

解釋?zhuān)?：不正確。windows線(xiàn)程創(chuàng )建時(shí)，不會(huì )綁定在特定的CPU上，需要手動(dòng)綁定，或者調用 ? SetThreadAffinityMask接口進(jìn)行綁定；

????????? ?2：正確。參考 ? ?http://blog.csdn.net/beyond_cn/article/details/15813361

????????? ?3：不正確。參考2的鏈接。歡迎各位糾正。

????????? ?4：正確。參考msdn:?

????????????_beginthread?函數可創(chuàng )建在?start_address?開(kāi)始執行例程的線(xiàn)程。? ? start_address?中的例程必須使用? ? ? ? __cdecl ? ? （用于本機代碼）或? ? ? ? __clrcall ? ? （用于托管代碼）調用約定，并且應沒(méi)有返回值。

????????????傳遞給? ? _beginthreadex ? ?? ? ? 的 ? ? ? start_address ? ? ? 中的例程必須使用 ? ? ? __stdcall ? ?? （用于本機代碼）或 ? ? ? __clrcall ? ?? （用于托管代碼）調用約定，并且必須返回線(xiàn)程退出代碼。

????????? ? 所以，通過(guò)1，就能選出D。

第14題：

?14、以下哪些線(xiàn)程同步鎖可以為遞歸鎖
1.信號量 ?2.讀寫(xiě)鎖 ? 3.互斥量 ? 4.事件 ? 5.臨界區（Critical Section）??????

A、1，3，4，5

B、5

C、3，5

D、1，3，5

?14、C

進(jìn)程/線(xiàn)程同步方法

常見(jiàn)的進(jìn)程/線(xiàn)程同步方法有互斥鎖（或稱(chēng)互斥量Mutex）、讀寫(xiě)鎖（rdlock）、條件變量（cond）、信號量（Semophore）等。

在windows系統中，臨界區（Critical Section）和事件對象（Event）也是常用的同步方法。

遞歸鎖/非遞歸鎖

Mutex可以分為遞歸鎖（recursive mutex）和非遞歸鎖（non-recursive mutex）。 ?遞歸鎖也叫可重入鎖（reentrant mutex），非遞歸鎖也叫不可重入鎖（non-reentrant mutex）。

二者唯一的區別是：

同一個(gè)線(xiàn)程可以多次獲取同一個(gè)遞歸鎖，不會(huì )產(chǎn)生死鎖。

如果一個(gè)線(xiàn)程多次獲取同一個(gè)非遞歸鎖，則會(huì )產(chǎn)生死鎖。

Windows下的Mutex和Critical Section是可遞歸的。

Linux下的pthread_mutex_t鎖是默認是非遞歸的�？梢酝ㄟ^(guò)設置PTHREAD_MUTEX_RECURSIVE屬性，將pthread_mutex_t鎖設置為遞歸鎖。

第15題：

?15、關(guān)于sendmessage和postmessage的區別，下面的說(shuō)法錯誤的是（）????????????

A、postmessage發(fā)出消息后，將消息放到消息隊列中，馬上返回

B、sendmessage發(fā)出消息后，一直等到該消息執行完畢，才返回

C、用sendmessage給其他線(xiàn)程創(chuàng )建的窗口發(fā)送消息時(shí)，消息也會(huì )進(jìn)消息隊列

D、用2個(gè)函數只能給當前進(jìn)程的窗口發(fā)送消息

?15、D

A：PostMessage只把消息放入隊列，不管其他程序是否處理都返回，然后繼續執行，這是個(gè)異步消息投放函數。

B:SendMessage必須等待其他程序處理消息完了之后才返回，繼續執行，這是個(gè)同步消息投放函數。

C:當某線(xiàn)程調用sendmessage給別的線(xiàn)程創(chuàng )建的窗口時(shí)，發(fā)送的消息首先追加到接收線(xiàn)程的發(fā)送消息隊列，發(fā)送線(xiàn)程處于空閑狀態(tài)，等待接收線(xiàn)程處理完他的消息返回給發(fā)送線(xiàn)程的應答隊列，等到后發(fā)送線(xiàn)程被喚醒取得應答隊列的消息 ? (就是處理完消息的返回值)，繼續執行。

D:sendmessage和postmessage都可以給其他線(xiàn)程發(fā)送消息

第16題：

?16、關(guān)于WM_COPYDATA消息的處理，下面描述錯誤的是（）?????????

A、可以在不同進(jìn)程之間傳遞少量只讀數據

B、只能通過(guò)sendmessage方式來(lái)發(fā)送該消息

C、只能在窗口過(guò)程函數中處理該消息

D、可以在消息隊列或窗口過(guò)程函數中處理該消息

?16、C

A：WM_COPYDATA消息的主要目的是允許在進(jìn)程間傳遞只讀數據。Windows在通過(guò)WM_COPYDATA消息傳遞期間，不提供繼承同步方式。

B;該消息只能由SendMessage()來(lái)發(fā)送，而不能使用PostMessage()。因為系統必須管理用以傳遞數據的緩沖區的生命期，如果使用了PostMessage()，數據緩沖區會(huì )在接收方（線(xiàn)程）有機會(huì )處理該數據之前，就被系統清除和回收。

D:可以在消息隊列或窗口過(guò)程函數中處理該消息

第17題：

?17、常用的windows進(jìn)入點(diǎn)函數wWinMain共有四個(gè)參數，其中不包括以下哪種類(lèi)型的參數（）????????

A、int

B、char*

C、PWSTR

D、HINSTANCE

?17、C
WinMain 函數的原型聲明如下：

int WINAPI WinMain(

?HINSTANCE hInstance , // handle to current instance

?HINSTANCE hPrevInstance , // handle to previous instance

?LPSTR lpCmdLine , // command line

?int nCmdShow // show state

?);

第一個(gè)參數 hInstance 表示該程序當前運行的實(shí)例的句柄，這是一個(gè)數值。
第二個(gè)參數 hPrevInstance 表示當前實(shí)例的前一個(gè)實(shí)例的句柄。
第三個(gè)參數 lpCmdLine 是一個(gè)以空終止的字符串，指定傳遞給應用程序的命令行參數。?
第四個(gè)參數 nCmdShow 指定程序的窗口應該如何顯示，例如最大化、最小化、隱藏等。

第18題：

?18、下列windows消息中，優(yōu)先級相對較低的是哪一個(gè)（）????

A、WM_MOUSEMOVE

B、WM_TIMER

C、WM_CHAR

D、WM_WINDOWPOSCHANGED

?18、B

WM_TIMER消息的優(yōu)先級最低，所以在有其他消息的情況下，WM_TIMER消息得不到處理

A:WM_MOUSEMOVE消息在鼠標移動(dòng)時(shí)被發(fā)送至已獲焦點(diǎn)的窗口

B:Windows定時(shí)器是一種周期性的消息產(chǎn)生裝置，它會(huì )每隔一段指定時(shí)間發(fā)送一次定時(shí)消息WM_TIMER。

C:未經(jīng)輸入法而直接送人程序中的字符會(huì )響應WM_CHAR消息

D:發(fā)送此消息給那個(gè)窗口的大小和位置已經(jīng)被改變時(shí)，來(lái)調用setwindowpos函數或其它窗口管理函數

第19題：

?19、最小堆[0,3,2,5,7,4,6,8],在刪除堆頂元素0之后，其結果是（）???????

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ìn)行，也就是刪除0元素。
然后讓最后一個(gè)節點(diǎn)放在堆頂，做向下調整工作，讓剩下的數組依然滿(mǎn)足最小堆。
刪除0后用8填充0的位置，為[8,3,2,5,7,4,6]
然后8和其子節點(diǎn)3,2比較，結果2最小，將2和8交換，為：[2,3,8,5,7,4,6]
然后8的下標為2，其兩個(gè)孩子節點(diǎn)下標分別為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)沒(méi)有孩子節點(diǎn)了，調整完成。

第20題：

?20、對一個(gè)由A,B,C,D隨機組成的序列進(jìn)行哈弗曼編碼，據統計，各個(gè)元素的概率分別為：P(A)=0.4，P(B)=0.35，P(C)=0.2，P(D)=0.05，請問(wèn)該編碼的平均期望編碼長(cháng)度為（）bits？

A、1.45

B、1.7

C、1.85

D、1.92

?20、C

首先要建立哈夫曼樹(shù)，然后計算平均期望編碼長(cháng)度：0.4*1 + 0.35*2 + 0.2*3 + 0.05*3 = 1.85

第21題：

?21、設有遞歸算法如下，

int x(int n)

{

?if(n<=3)

?????return 1;

?else

?????return x(n-2)+x(n-4)+1;

}

試問(wèn)計算x(x(8))時(shí)需要計算（）次x函數。??????

A、8

B、9

C、16

D、18

?21、D

x(8)=x(6)+x(4)+1 ?遞歸計算x(8)第一次調用

x(6)=x(4)+x(2)+1? 遞歸計算x(6)第二次調用

x(4)= ? x(2)+x(0)+1? ? 遞歸計算x(4)第三次調用

x(4)= ? x(2)+x(0)+1 ? ? 遞歸計算x(4)第四次調用??

之后再調用x()計算黑體部分的結果(5次，加上前面4次，一共9次)，最后x(8)返回值為9

接著(zhù)計算x(9)

x(9)=x(7)+x(5)+1 ?遞歸計算x(9)第一次調用

x(7)=x(5)+x(3)+1? 遞歸計算x(7)第二次調用

x(5)=x(3)+x(1)+1??遞歸計算x(5)第三次調用

x(5)=x(3)+x(1)+1??遞歸計算x(5)第四次調用

之后再調用x()計算黑體部分的結果(5次，加上前面4次，一共9次)，最后x(8)返回值為9 ?

所以總共調用x()的次數是9+9=18

第22題：

?22、設一組初始記錄關(guān)鍵字序列(Q,H,C,Y,P,A,M,S,R,D,F,X),則按字母升序的第一趟冒泡排序結束后的結果是（）

A、F，H，C，D，P，A，M，Q，R，S，Y，X

B、P，A，C，S，Q，D，F，X，R，H，M，Y

C、A，D，C，R，F，Q，M，S，Y，P，H，X

D、H，C，Q，P，A，M，S，R，D，F，X，Y

?22、D

第一趟冒泡：從數組第一個(gè)元素到最后一個(gè)元素掃描，比較相鄰的元素，如果后一個(gè)元素小于前一個(gè)，則交換位置。第一趟結束時(shí)，最大元素到達最后一個(gè)元素位置

第23題：

23、堆排序的空間復雜度是（），堆排序中構建堆的時(shí)間復雜度是（）。?

A、Ｏ(logn)，O(n)

B、O(logn)，O(nlogn)

C、O(1)，O(n)

D、O(1)，O(nlogn)

23、C

“空間復雜度”指占內存大小，堆排序每次只對一個(gè)元素操作，是就地排序，所用輔助空間O(1)，空間復雜度是O（1）

在構建堆的過(guò)程中，完全二叉樹(shù)從最下層最右邊的非終端結點(diǎn)開(kāi)始構建，將它與其孩子進(jìn)行比較和必要的互換，對于每個(gè)非終端結點(diǎn)來(lái)說(shuō)，其實(shí)最多進(jìn)行兩次比較和互換操作，因此整個(gè)構建堆的時(shí)間復雜度為O(n)。
在正式排序時(shí)，第i次取堆頂記錄重建堆需要用O(logi)的時(shí)間（完全二叉樹(shù)的某個(gè)結點(diǎn)到根結點(diǎn)的距離為?log2i?+1），并且需要取n-1次堆頂記錄，因此，重建堆的時(shí)間復雜度為O(nlogn)。

第24題：

?24、若用一個(gè)大小為6的數組來(lái)實(shí)現循環(huán)隊列，且當前rear和front的值分別0和3。當從隊列中刪除一個(gè)元素，再加入兩 個(gè)元素后，rear和front的值分別為（）

?A、2和4

B、1和5

C、4和2

D、5和1

?24、A
因為出隊時(shí)，front=front+1/MAXSIZE,rear不變，所以front=4
入隊時(shí)，rear=rear+1/MAXSIZE,front不變，所以rear=2;

第25題：

?25、如下表是用戶(hù)是否使用某產(chǎn)品的調查結果（）?

UID ?? ?年齡 ?? ?地區 ?? ?學(xué)歷 ?? ?收入 ?? ?用戶(hù)是否使用調查產(chǎn)品 ?? ?

1 ?? ?低 ?? ?北方 ?? ?博士 ?? ?低 ?? ?是 ?? ?

2 ?? ?高 ?? ?北方 ?? ?本科 ?? ?中 ?? ?否 ?? ?

3 ?? ?低 ?? ?南方 ?? ?本科 ?? ?高 ?? ?否 ?? ?

4 ?? ?高 ?? ?北方 ?? ?研究生 ?? ?中 ?? ?是?????????
請計算年齡，地區，學(xué)歷，收入中對用戶(hù)是否使用調查產(chǎn)品信息增益最大的屬性（Log23≈0.63）????????

A、年齡

B、地區

C、學(xué)歷

D、收入

?25、C
不用算一眼就能看出來(lái)，所有本科學(xué)歷都不使用調查產(chǎn)品，所有非本科學(xué)歷都使用了調查產(chǎn)品。這種可以確定的劃分導致信息熵為0，信息增益最大

第26題：

?26、假設某算法的計算時(shí)間可用遞推關(guān)系式T(n)=2T(n/2)+n表示，則該算法的時(shí)間復雜度為（）?

A、O(logn)

B、O(n*logn)

C、O(n)

D、O(n^2)

?26、B

T(n)=2^k*(T(n/(2^k)))+k*n

2^k = n,k = log(n) ??(以2為底)

T（n） = n*T(1)+n*log(n)<= c*n*log(n) ?(c為常數)

所以是O(n*logn)

第27題：

?27、基于統計的分詞方法為（）????????

A、正向最大匹配法

B、逆向最大匹配法

C、最少切分

D、條件隨機場(chǎng)

?27、D
目前的分詞方法歸納起來(lái)有3 類(lèi):
第一類(lèi)是基于語(yǔ)法和規則的分詞法。其基本思想就是在分詞的同時(shí)進(jìn)行句法、語(yǔ)義分析, 利用句法信息和語(yǔ)義信息來(lái)進(jìn)行詞性標注, 以解決分詞歧義現象。因為現有的語(yǔ)法知識、句法規則十分籠統、復雜, 基于語(yǔ)法和規則的分詞法所能達到的精確度遠遠還不能令人滿(mǎn)意, 目前這種分詞系統還處在試驗階段。
第二類(lèi)是機械式分詞法（即基于詞典）。機械分詞的原理是將文檔中的字符串與詞典中的詞條進(jìn)行逐一匹配, 如果詞典中找到某個(gè)字符串, 則匹配成功, 可以切分, 否則不予切分�；谠~典的機械分詞法, 實(shí)現簡(jiǎn)單, 實(shí)用性強, 但機械分詞法的最大的缺點(diǎn)就是詞典的完備性不能得到保證。據統計, 用一個(gè)含有70 000 個(gè)詞的詞典去切分含有15 000 個(gè)詞的語(yǔ)料庫, 仍然有30% 以上的詞條沒(méi)有被分出來(lái), 也就是說(shuō)有4500 個(gè)詞沒(méi)有在詞典中登錄。
第三類(lèi)是基于統計的方法�；诮y計的分詞法的基本原理是根據字符串在語(yǔ)料庫中出現的統計頻率來(lái)決定其是否構成詞。詞是字的組合, 相鄰的字同時(shí)出現的次數越多, 就越有可能構成一個(gè)詞。因此字與字相鄰共現的頻率或概率能夠較好的反映它們成為詞的可信度。
最大匹配是指以詞典為依據，取詞典中最長(cháng)單詞為第一個(gè)次取字數量的掃描串，在詞典中進(jìn)行掃描，這是基于詞典分詞的方法
1.正向最大匹配法?
2.逆向最大匹配法
3.最少切分法：使每一句中切出的詞數最小，這也是基于詞典分詞的方法
條件隨機場(chǎng)是一個(gè)基于統計的序列標記和分割的方法，屬于基于統計的分詞方法范疇。它定義了整個(gè)標簽序列的聯(lián)合概率，各狀態(tài)是非獨立的，彼此之間可以交互，因此可以更好地模擬現實(shí)世界的數據．

第28題：

?28、下列哪個(gè)不屬于CRF模型對于HMM和MEMM模型的優(yōu)勢（）????????????

A、特征靈活

B、速度快

C、可容納較多上下文信息

D、全局最優(yōu)

?28、B
隱馬爾可夫模型（Hidden Markov Model，HMM），最大熵馬爾可夫模型（Maximum Entropy Markov ?Model，MEMM）以及條件隨機場(chǎng)（Conditional Random Field，CRF）是序列標注中最常用也是最基本的三個(gè)模型。
HMM模型是對轉移概率和表現概率直接建模，統計共現概率。
MEMM模型是對轉移概率和表現概率建立聯(lián)合概率，統計時(shí)統計的是條件概率，但MEMM容易陷入局部最優(yōu)，是因為MEMM只在局部做歸一化。
RF模型中，統計了全局概率，在 做歸一化時(shí)，考慮了數據在全局的分布，而不是僅僅在局部歸一化，這樣就解決了MEMM中的標記偏置（label bias）的問(wèn)題。
CRF沒(méi)有HMM那樣嚴格的獨立性假設條件，因而可以容納任意的上下文信息。特征設計靈活。（與ME一樣） ————與HMM比較
同時(shí)，由于CRF計算全局最優(yōu)輸出節點(diǎn)的條件概率，它還克服了最大熵馬爾可夫模型標記偏置（Label-bias）的缺點(diǎn)。 ­­————與MEMM比較
CRF是在給定需要標記的觀(guān)察序列的條件下，計算整個(gè)標記序列的聯(lián)合概率分布，而不是在給定當前狀態(tài)條件下，定義下一個(gè)狀態(tài)的狀態(tài)分布。
CRF需要訓練的參數更多，與MEMM和HMM相比，它存在訓練代價(jià)大、復雜度高的缺點(diǎn)。

第29題：

29、假設一個(gè)完整的撲克牌有52張牌，2黑色（黑葵和梅花）和2紅色（方塊和紅心）。如果給你一副完整的牌，和半副牌（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、在二分類(lèi)問(wèn)題中，當測試集的正例和負例數量不均衡時(shí)，以下評價(jià)方案哪個(gè)是相對不合理的（）（假設 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:曲線(xiàn)下面積

?30、A

題目提到測試集正例和負例數量不均衡，那么假設正例數量很少占10%，負例數量占大部分90%。

而且算法能正確識別所有負例，但正例只有一半能正確判別。

那么TP=0.05×all, TN=0.9×all，Accuracy=95%。

雖然Accuracy很高，但正例precision只有50%

第31題：

?31、下面關(guān)于ID3算法中說(shuō)法錯誤的是（）??????????

A、ID3算法要求特征必須離散化

B、信息增益可以用熵，而不是GINI系數來(lái)計算

C、選取信息增益最大的特征，作為樹(shù)的根節點(diǎn)

D、ID3算法是一個(gè)二叉樹(shù)模型???????

?31、D
ID3 算法生成的決策樹(shù)是一棵多叉樹(shù)，分支的數量取決于分裂屬性有多少 個(gè)不同的取值。?

第32題：

?32、圓內接三角形是銳角三角形概率是多少（）?????????

A、1/4

B、1/3

C、1/2

D、2/3

?32、A
三角形的三點(diǎn)在圓上的位置是等概率的。這種任意位置組成的三角形中，最大的那個(gè)角必定大于等于60度，因此滿(mǎn)是三角形是銳角的變化范圍是60-90度，鈍角的范圍是90-180度

第33題：

?33、六個(gè)人排成一排，甲與乙不相鄰，且甲與丙不相鄰的不同排法數是多少（）??????????

A、216

B、240

C、288

D、360

?33、C

1，首先將甲乙丙拿出來(lái)，剩下三個(gè)做全排列，有A(3,3)=6種排列,

2，將甲乙兩個(gè)插入第一步三個(gè)人的四個(gè)空隙中，有A(4,2)=12種

3，剩下丙插入到前五個(gè)人中的六個(gè)空隙中，其中甲的左右兩側不符合，

? ?還有4個(gè)符合條件的空隙，C(4,1)=4

4,總共有6*12*4=288

第34題：

?34、在其他條件不變的前提下，以下哪種做法容易引起機器學(xué)習中的過(guò)擬合問(wèn)題（）

A、增加訓練集量

B、減少神經(jīng)網(wǎng)絡(luò )隱藏層節點(diǎn)數

C、刪除稀疏的特征 ? S

D、SVM算法中使用高斯核/RBF核代替線(xiàn)性核

?34、B
過(guò)擬合就是導致擬合過(guò)度，算法的普適性降低
B選項減少神經(jīng)網(wǎng)絡(luò )隱層節點(diǎn)數，也就減小了輸入層與隱層，隱層與輸出層之間的連接矩陣，使其適應性變差

第35題：

?35、計算一個(gè)任意三角形的面積，S=√(p(p-a)(p-b)(p-c)),p=(a+b+c)/2,以下等價(jià)類(lèi)測試用例中，不屬于無(wú)效等價(jià)類(lèi)的是（）?????

A、a=5，b=3，c=6;

B、a=2，b=3，c=5;

C、a=7，b=3，c=3;

D、a=2，b=6，c=3;

?35、A
選項A滿(mǎn)足三角形兩邊之和大于第三邊，兩邊之差小于第三邊，是有效的
選項BCD都不滿(mǎn)足兩邊之和大于第三邊，屬于等級無(wú)效的

第36題：

?二、多選題

36、下列排序算法的常規實(shí)現中，哪些空間復雜度是O(1)????

A、冒泡

B、選擇

C、歸并

D、快排

E、堆排序

?36、A.B.E

冒泡排序,選擇排序,堆排序的空間復雜度為O(1),因為需要一個(gè)臨時(shí)變量來(lái)交換元素位置,(另外遍歷序列時(shí)自然少不了用一個(gè)變量來(lái)做索引).

快速排序空間復雜度為logn(因為遞歸調用了) ,歸并排序空間復雜是O(n),需要一個(gè)大小為n的臨時(shí)數組.