1、假設(shè)進(jìn)棧次序是e1, e2, e3, e4，那可能的出棧次序是()

A、e2, e4, e3, e1

B、e2, e3, e4, e1

C、e3, e2, e4, e1

D、e1, e2, e4, e3

給定入棧順序，求出可能的出棧順序。(點(diǎn)評(píng)：老得掉渣得題目了，只要小心點(diǎn)都沒有問題)

2、表達(dá)式X=A+B(C-D)/E的后綴表示形式可以是()

A、XAB+CDE/-=

B、XA+BC-DE/=

C、XABCD-E/+=

D、XABCDE+/=

分析：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)

分析：或者舉例說明也行。。

4.那個(gè)排序算法是非穩(wěn)定的?選擇，冒泡、希爾，堆排序，快速等 (也是比較基礎(chǔ)的題目)

A、冒泡排序 B、歸并排序 C、快速排序 D、堆排序 E、希爾排序

分析：凡是O(n^2)的全部是穩(wěn)定排序，O(nlogn)的全部是非穩(wěn)定排序。。

5.根據(jù)函數(shù)，賦予參數(shù)值，寫輸出。。請(qǐng)問func(0x7f530829)的返回值是()

int func(unsigned int i)

{

unsigned int temp = i;

temp = (temp & 0x55555555) + ((temp & 0xaaaaaaaa)>>1);

temp = (temp & 0x33333333) + ((temp & 0xcccccccc)>>2);

temp = (temp & 0x0f0f0f0f) + ((temp & 0xf0f0f0f0)>>4);

temp = (temp & 0xff00ff) + ((temp & 0xff00ff00)>>8);

temp = (temp & 0xffff) + ((temp & 0xffff0000)>>16);

return temp;

}

A、15 B、16 C、17 D、18

分析：函數(shù)實(shí)現(xiàn)的是求二進(jìn)制表示的時(shí)候，1的個(gè)數(shù)，一共15個(gè)

最開始把每一個(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)程可以通過IPC通信,但線程不可以

7.內(nèi)存管理：段頁式管理，地址映射表是?(操作系統(tǒng)方面的知識(shí)也不能掉以輕心呀)

A. 每個(gè)作業(yè)或進(jìn)程一張段表，一張頁表

B. 每個(gè)作業(yè)或進(jìn)程的每個(gè)段一張段表，一張頁表

C. 每個(gè)作業(yè)或進(jìn)程一張段表，每個(gè)段一張頁表

D. 每個(gè)作業(yè)一張頁表，每個(gè)段一張段表

8、關(guān)于TCP協(xié)議，下面哪種說法是錯(cuò)誤的()

A、TCP關(guān)閉連接過程中，兩端的socket都會(huì)經(jīng)過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、在成功建立連接的TCP上，只有在Established狀態(tài)才能收發(fā)數(shù)據(jù)，其他狀態(tài)都不可以。

分析：tcp/ip協(xié)議的實(shí)際使用過程中的問題：例如單方面斷開后，另一端出于哪種狀態(tài)，還有

9、關(guān)于主鍵Primary Key和索引index的說法哪些是錯(cuò)誤的?()

A、唯一索引的列允許為NULL值

B、一個(gè)關(guān)系表中的外鍵必定是另一表中的主鍵

C、一個(gè)表中只能有一個(gè)唯一性索引

D、索引主要影響查詢過程，對(duì)數(shù)據(jù)的插入影響不大

分析：數(shù)據(jù)庫方面的知識(shí)：主鍵和索引的基本定義及其性質(zhì)，例如主鍵在表中是否唯一，索引的速度以及對(duì)表的改變的影響;無論是唯一索引還是非唯一索引，索引列都允許取NULL值

10、數(shù)據(jù)庫的事務(wù)隔離級(jí)別一般分為4個(gè)級(jí)別，其中可能發(fā)生“不可重復(fù)讀”的事物級(jí)別有()

A、SERIALIZABLE

B、READ COMMITTED

C、READ UNCOMMITTED

D、REPEATABLE READ

分析數(shù)據(jù)庫：數(shù)據(jù)庫的不可重復(fù)訪問異常，四種事務(wù)隔離級(jí)別中哪些可以避免該類異常?

各隔離級(jí)別對(duì)各種異常的控制能力

11、如果F(n)為該數(shù)列的第n項(xiàng)，那么這句話可以寫成如下形式：

F(1)=1，F(xiàn)(2)=1，F(xiàn)(n)=F(n-1)+F(n-2) (n>=3)

請(qǐng)實(shí)現(xiàn)該函數(shù)F(n)的求解，并給出算法復(fù)雜度，要求算法復(fù)雜度小于O(n^2)。

思路：使用滾動(dòng)數(shù)組可以保存以前保存的結(jié)果，加快速度，減少空間復(fù)雜度。

int Fib(int index)

{

if(index<1)

{

return-1;

}

int a1=1,a2=1,a3=1;

for(int i=0;i

{

a3=a1+a2;

a1=a2;

a2=a3;

}

return a3;

}

第二 部分(必做)：程序設(shè)計(jì)

1、下面的程序的輸出是什么?

#include

int main(void)

{

int n;

char y[10] = "ntse";

char x = y;

n = strlen(x);

x = x[n];

x++;

printf("x=%s\n",x);

printf("y=%s\n",y);

return 0;

}

輸出：

x=tse

y=

因?yàn)閚=4，則x = x[n]; 的功能是將x指向的第一個(gè)字符n修改為\0，這樣y字符串就結(jié)束了，所以第二輸出為空，x++操作后，x指向第二個(gè)字符t，所以第一個(gè)輸出為：tse。

2、請(qǐng)給出下面程序的輸出結(jié)果，并說明原因。

#include

#include

using namespace std;

template

class array

{

public:

array(int size);

size_t getVectorSize()

{

return _data.size();

}

size_t getSize()

{

return _size;

}

public:

vector _data;

size_t _size;

};

template

array::array(int size) : _size(size) , _data(_size)

{ }

int main(void)

{

array arr = new array(3);

cout

cout

return 0;

}

12.寫一個(gè)程序來確定系統(tǒng)是大端模式還是小端模式;

13.編程實(shí)現(xiàn)采用位操作來實(shí)現(xiàn)整數(shù)的加法操作。

14. 圖的矩陣表示法，圖的深度優(yōu)先遍歷，算法思路及其實(shí)現(xiàn)。

15.CAS(compare and swap)操作實(shí)現(xiàn)：(具體原理可以參考)

16.fork函數(shù)的用法。具體題目為：

#include

#include

#include

int main(void)

{

int i;

for(i=0; i<2; i++){

fork();

printf("-");

fflush(stdout);

}

return 0;

}

6個(gè)-

詳見：http://coolshell.cn/articles/7965.html

17.spin lock原理：

先來一些代碼吧!

void initlock(volatile int lock_status)

{

lock_status = 0;

}

void lock(volatile int lock_status)

{

while(test_and_set(lock_status = =1);

}

void unlock(volatile int lock_status)

{

lock_status = 0;

}

問題：volatile的作用?lock函數(shù)優(yōu)化(針對(duì)在多cpu上提高cpu cache)?上面的缺陷(內(nèi)存模式上的)?

volatile的作用： 作為指令關(guān)鍵字，確保本條指令不會(huì)因編譯器的優(yōu)化而省略，且要求每次直接讀值。如果沒有volatile，基本上會(huì)導(dǎo)致這樣的結(jié)果：要么無法編寫多線程程序，要么編譯器失去大量?jī)?yōu)化的機(jī)會(huì)。

18.給定一個(gè)巨大的文件，如何從中選出k行，隨處輸出k行到文件中。要求每一行出現(xiàn)的概率都相等。設(shè)計(jì)算法、說明思路，算法復(fù)雜度。

19.win32中WM_Quit的作用是什么?

20.比較mutex和臨街區(qū)之間的區(qū)別，并說明其使用場(chǎng)景。

21.多線程編程，如何安全退出線程。

還有網(wǎng)易數(shù)據(jù)挖掘方面的題目，這次數(shù)據(jù)挖掘的題目比較新奇，都是簡(jiǎn)答題。如下：

1，簡(jiǎn)述你對(duì)數(shù)據(jù)與處理的認(rèn)識(shí);

2，簡(jiǎn)述你對(duì)中文分詞的理解，說明主要難點(diǎn)和常用算法;

3，常見的分類算法有哪些;

4，簡(jiǎn)述K-MEANS算法;

5，設(shè)計(jì)一個(gè)智能的商品推薦系統(tǒng);

6，簡(jiǎn)述你對(duì)觀點(diǎn)挖掘的認(rèn)識(shí)

網(wǎng)易游戲筆試的人太少，因此可提供的筆試題目都不全，只是聽說特別的難。還有好多是數(shù)學(xué)方面的智力題。例如：

1、英雄升級(jí)，從0級(jí)升到1級(jí)，概率100%。

從1級(jí)升到2級(jí)，有1/3的可能成功;1/3的可能停留原級(jí);1/3的可能下降到0級(jí);

從2級(jí)升到3級(jí)，有1/9的可能成功;4/9的可能停留原級(jí);4/9的可能下降到1級(jí)。

每次升級(jí)要花費(fèi)一個(gè)寶石，不管成功還是停留還是降級(jí)。

求英雄從0級(jí)升到3級(jí)平均花費(fèi)的寶石數(shù)目。