十月下旬騰訊，網易遊戲，百度最新校園招聘筆試題集錦(第271-330題)

引言

    此文十月百度，阿裡巴巴，迅雷搜狗最新面試十一題已經整理了最新的面試題70道，本文依次整理騰訊，網易遊戲，百度等各大公司最新校園招聘的筆試題，後續将繼續整理十月下旬的筆/面試題。

騰訊2011.10.15校園招聘會筆試題

1、下面的排序算法中，初始資料集的排列順序對算法的性能無影響的是（B）

A、插入排序                      B、堆排序                    C、冒泡排序                     D、快速排序

2、以下關于Cache的叙述中，正确的是（B）

A、CPU中的Cache容量應大于CPU之外的Cache容量

B、Cache的設計思想是在合理成本下提高命中率

C、Cache的設計目标是容量盡可能與主存容量相等

D、在容量确定的情況下，替換算法的時間複雜度是影響Cache命中率的關鍵因素

3、資料存儲在磁盤上的排列方式會影響I/O服務的性能，一個圓環的磁道上有10個實體塊，10個資料記錄R1------R10存放在這個磁道上，記錄的安排順序如下表所示：

實體塊	1	2	3	4	5	6	7	8	9	10
邏輯記錄	R1	R2	R3	R4	R5	R6	R7	R8	R9	R10

假設磁盤的旋轉速度為20ms/周，磁盤目前處在R1的開頭處，若系統順序掃描後将資料放入單緩沖區内，處理資料的時間為4ms（然後再讀取下個記錄），則處理這10個記錄的最長時間為（C）

A、180ms                           B、200ms                          C、204ms                             D、220ms

4、随着IP網絡的發展，為了節省可配置設定的注冊IP位址，有一些位址被拿出來用于私有IP位址，以下不屬于私有IP位址範圍的是（C）（私網IP位址：10.0.0.0- 10.255.255.255 ；172.16.0.0 -   172.31.255.255；192.168.0.0-192.168.255.255。故選C）

A、10.6.207.84                              B、172.23.30.28                      C、172.32.50.80               D、192.168.1.100

5、下列關于一個類的靜态成員的描述中，不正确的是（D）

A、該類的對象共享其靜态成員變量的值                              B、靜态成員變量可被該類的所有方法通路                 

C、該類的靜态方法隻能通路該類的靜态成員變量                 D、該類的靜态資料成員變量的值不可修改

6、已知一個線性表（38，25，74，63，52，48），假定采用散列函數h（key) = key%7計算散列位址，并散列存儲在散清單A【0....6】中，若采用線性探測方法解決沖突，則在該散清單上進行等機率成功查找的平均查找長度為（C）

A、1.5                  B、1.7                           C、2.0                       D、2.3

依次進行取模運算求出哈希位址：

A	1	2	3	4	5	6
記錄	63	48	38	25	74	52
查找次數	1	3	1	1	2	4

74應該放在下标為4的位置，由于25已經放在這個地方，是以74往後移動，放在了下标為5的位置上了。

由于是等機率查找，是以結果為：1/6*（1+3+1+1+2+4）= 2.0

7、表達式“X=A+B*（C--D）/E”的字尾表示形式可以為（C）

A、XAB+CDE/-*=                     B、XA+BC-DE=

8、（B）設計模式将抽象部分與它的實作部分相分離。

A、Singleton（單例）                   B、 Bridge（橋接）                     

C、 Composite（組合）                                   D、 Facade（外觀）

9、下面程式的輸出結果為多少？

view plain

1. void Func(char str_arg[100])  
2. {  
3.     printf("%d\n",sizeof(str_arg));  
4. }  
5. int main(void)  
6. {  
7.     char str[]="Hello";  
8.     printf("%d\n",sizeof(str));  
9.     printf("%d\n",strlen(str));  
10.     char *p = str;  
11.     printf("%d\n",sizeof(p));  
12.     Func(str);  
13. }  

輸出結果為：6   5     4      4

對字元串進行sizeof操作的時候，會把字元串的結束符“\0”計算進去的，進行strlen操作求字元串的長度的時候，不計算\0的。

數組作為函數參數傳遞的時候，已經退化為指針了，Func函數的參數str_arg隻是表示一個指針，那個100不起任何作用的。

10、下面程式的輸出結果為多少？

view plain

1. void Func(char str_arg[2])  
2. {  
3.     int m = sizeof(str_arg);     //指針的大小為4  
4.     int n = strlen(str_arg);     //對數組求長度，str_arg後面的那個2沒有任何意義，數組已經退化為指針了  
5.     printf("%d\n",m);  
6.     printf("%d\n",n);  
7. }  
8. int main(void)  
9. {  
10.     char str[]="Hello";  
11.     Func(str);  
12. }  

輸出結果為：      4         5

strlen隻是對傳遞給Func函數的那個字元串求長度，跟str_arg中的那個2是沒有任何關系的，即使把2改為200也是不影響輸出結果的。。

11、到商店裡買200的商品返還100優惠券（可以在本商店代替現金）。請問實際上折扣是多少？

算法程式設計題：

1、給定一個字元串，求出其最長的重複子串。

思路：使用字尾數組，對一個字元串生成相應的字尾數組後，然後再排序，排完序依次檢測相鄰的兩個字元串的開頭公共部分。

這樣的時間複雜度為：

生成字尾數組 O(N)

排序 O(NlogN*N) 最後面的 N 是因為字元串比較也是 O(N)

依次檢測相鄰的兩個字元串 O(N * N)

總的時間複雜度是 O(N^2*logN), 

網易遊戲2011.10.15校園招聘會筆試題

1、對于一個記憶體位址是32位、記憶體頁是8KB的系統。0X0005F123這個位址的頁号與頁内偏移分别是多少。

2、如果X大于0并小于65536，用移位法計算X乘以255的值為：-X+X<<8

X<<8-X是不對的，X<<8，已經把X的值改變了（訂正：X<<8是個臨時變量，不會改變X的值，就像a+1不會改變a一樣）。

3、一個包含n個節點的四叉樹，每個節點都有四個指向孩子節點的指針，這4n個指針中有   3n+1   個空指針。

4、以下兩個語句的差別是：

view plain

1. int *p1 = new int[10];  
2. int *p2 = new int[10]();  

5、計算機在記憶體中存儲資料時使用了大、小端模式，請分别寫出A=0X123456在不同情況下的首位元組是，大端模式：0X12           小端模式：0X56           X86結構的計算機使用  小端    模式。

一般來說，大部分使用者的作業系統（如windows, FreeBsd,Linux）是小端模式的。少部分，如MAC OS，是大端模式 的。

6、在遊戲設計中，經常會根據不同的遊戲狀态調用不同的函數，我們可以通過函數指針來實作這一功能，請聲明一個參數為int *，傳回值為int的函數指針：

int (*fun)(int *)

7、在一冒險遊戲裡，你見到一個寶箱，身上有N把鑰匙，其中一把可以打開寶箱，假如沒有任何提示，随機嘗試，問：

（1）恰好第K次（1=<K<=N）打開寶箱的機率是多少。

（2）平均需要嘗試多少次。

百度2011.10.16校園招聘會筆試題

 一、算法設計

1、設rand（s，t）傳回[s,t]之間的随機小數，利用該函數在一個半徑為R的圓内找随機n個點，并給出時間複雜度分析。

2、為分析使用者行為，系統常需存儲使用者的一些query，但因query非常多，故系統不能全存，設系統每天隻存m個query，現設計一個算法，對使用者請求的query進行随機選擇m個，請給一個方案，使得每個query被抽中的機率相等，并分析之，注意：不到最後一刻，并不知使用者的總請求量。

3、C++ STL中vector的相關問題：

    （1）、調用push_back時，其内部的記憶體配置設定是如何進行的？

    （2）、調用clear時，内部是如何具體實作的？若想将其記憶體釋放，該如何操作？

二、系統設計

正常使用者端每分鐘最多發一個請求至服務端，服務端需做一個異常用戶端行為的過濾系統，設伺服器在某一刻收到用戶端A的一個請求，則1分鐘内的用戶端任何其它請求都需要被過濾，現知每一用戶端都有一個IPv6位址可作為其ID，用戶端個數太多，以至于無法全部放到單台伺服器的記憶體hash表中，現需簡單設計一個系統，使用支援高效的過濾，可使用多台機器，但要求使用的機器越少越好，請将關鍵的設計和思想用圖表和代碼表現出來。

三、求一個全排列函數：

如p([1,2,3])輸出：

[123]、[132]、[213]、[231]、[321]、[323]

 求一個組合函數

如p([1,2,3])輸出：

[1]、[2]、[3]、[1,2]、[2,3]、[1,3]、[1,2,3]

這兩問可以用僞代碼。  

迅雷2011.10.21筆試題

1、下面的程式可以從1....n中随機輸出m個不重複的數。請填空

knuth(int n, int m)

{

         srand((unsigned int)time(0));

       for (int i=0; i<n; i++)

          {

                 if (            )

                  {

                                cout<<i<<endl;

                                                         ;

                   }

          }

}

分别為：rand()%(n-i)<m  和 m--;

2、以下prim函數的功能是分解質因數。請填空

void prim(int m, int n)

{

    if (m>n)

    {

        while (            ) n++;

                                       ;

       prim(m,n);

       cout<<n<<endl;

    }

}

分别為：m%n  和 m/=n

3、下面程式的功能是輸出數組的全排列。請填空

void perm(int list[], int k, int m)

{

    if (            )

    {

        copy(list,list+m,ostream_iterator<int>(cout," "));

        cout<<endl;

        return;

    }

    for (int i=k; i<=m; i++)

    {

        swap(&list[k],&list[i]);

                                         ;

        swap(&list[k],&list[i]);

    }

}

分别為：k==m 和 perm（list,k+1,m）

二、主觀題：

1、（40分）使用者啟動迅雷時，伺服器會以uid,login_time,logout_time的形式記錄使用者的線上時間；使用者在使用迅雷下載下傳時，伺服器會以taskid,start_time,finish_time的形式記錄任務的開始時間和結束時間。有效下載下傳時間是指使用者在開始時間和結束時間之間的線上時間，由于使用者可能在下載下傳的時候退出迅雷，是以有效下載下傳時間并非finish_time 和 start_time之差。假設登入記錄儲存在login.txt中，每一行代表使用者的上下線記錄；下載下傳記錄儲存在task.txt中，每一行代表一個任務記錄，記錄的字段之間以空格分開。計算每個使用者的有效下載下傳時間和總線上時間的比例。注意：請盡量使用STL的資料結構和算法

2、（60分）在8X8的棋盤上分布着n個騎士，他們想約在某一個格中聚會。騎士每天可以像國際象棋中的馬那樣移動一次，可以從中間像8個方向移動（當然不能走出棋盤），請計算n個騎士的最早聚會地點和要走多少天。要求盡早聚會，且n個人走的總步數最少，先到聚會地點的騎士可以不再移動等待其他的騎士。

 從鍵盤輸入n（0<n<=64），然後一次輸入n個騎士的初始位置xi,yi（0<=xi,yi<=7）。螢幕輸出以空格分隔的三個數，分别為聚會點（x，y）以及走的天數。

盛大遊戲2011.10.22校園招聘會筆試題

1、下列代碼的輸出為：

1. #include "iostream"  
2. #include "vector"  
3. using namespace std;  
4. int main(void)  
5. {  
6.     vector<int>array;  
7.     array.push_back(100);  
8.     array.push_back(300);  
9.     array.push_back(300);  
10.     array.push_back(500);  
11.     vector<int>::iterator itor;  
12.     for(itor=array.begin();itor!=array.end();itor++)  
13.     {  
14.         if(*itor==300)  
15.         {  
16.             itor = array.erase(itor);  
17.         }  
18.     }  
19.     for(itor=array.begin();itor!=array.end();itor++)  
20.     {  
21.         cout<<*itor<<" ";  
22.     }  
23.     return 0;  
24. }  

A、100   300   300   500      B、100    300     500       C、100    500      D、程式錯誤

vector在erase之後，指向下一個元素的位置，其實進行erase操作時将後面所有元素都向前移動，疊代器位置沒有移動。itor=array.erase(itor)  erase傳回下一個元素的位址，相當于給itor一個新值。

2、下列代碼的輸出為：

1. class CParent  
2. {  
3. public:  
4.     virtual void Intro()  
5.     {  
6.         printf("I'm a Parent, ");  
7.         Hobby();  
8.     }  
9.     virtual void Hobby()  
10.     {  
11.         printf("I like football!");  
12.     }  
13. };  
14. class CChild:public CParent  
15. {  
16. public:  
17.     virtual void Intro()  
18.     {  
19.         printf("I'm a Child, ");  
20.         Hobby();  
21.     }  
22.     virtual void Hobby()  
23.     {  
24.         printf("I like basketball!\n");  
25.     }  
26. };  
27. int main(void)  
28. {  
29.     CChild *pChild = new CChild();  
30.     CParent *pParent = (CParent*)pChild;  
31.     pParent->Intro();  
32.     return 0;  
33. }  

A、I'm a Child,I like football!                            B、I'm a Child,I like basketball!  

C、I'm a Parent,I like football!                         D、I'm a Parent,I like basketball! 

3、在win32平台下，以下哪種方式無法實作程序同步？

A、Critical Section      B、Event      C、Mutex         D、Semaphore

4、以下哪句的說法是正确的

A、在頁式存儲管理中，使用者應将自己的程式劃分為若幹個相等的頁

B、所有的程序都挂起時，系統将陷入死鎖

C、執行系統調用可以被中斷

D、程序優先數是程序排程的重要依據，必須根據程序運作情況動态改變

5、以下描述正确的是

A、虛函數是可以内聯的，可以減少函數調用的開銷提高效率

B、類裡面可以同時存在函數名和參數都一樣的虛函數和靜态函數

C、父類的析構函數是非虛的，但是子類的析構函數是虛的，delete子類對象指針會調用父類的析構函數

D、以上都不對

簡答題：快速排序的思想是遞歸的，但是它的平均效率卻是衆多排序算法中最快的，為什麼？請結合本例說明你對遞歸程式的了解。

算法題：用你熟悉的程式設計語言，設計如下功能的函數：輸入一個字元串，輸出該字元串中所有字母的全排列。程式請适當添加注釋。

C++函數原型： void Print（const char *str）

輸入樣例： abc

輸出結果： abc、acb、bca、bac、cab、cba

（以上部分整理自此君部落格： http://blog.csdn.net/Hackbuteer1。十分感謝。有何不妥之處，還望海涵海涵。）  

後續整理

1. 12個工廠分布在一條東西向高速公路的兩側，工廠距離公路最西端的距離分别是0、4、5、10、12、18、27、30、31、38、39、47.在這12個工廠中選取3個原料供應廠，使得剩餘工廠到最近的原料供應廠距離之和最短，問應該選哪三個廠 ？ 

2. 

3. hash沖突時候的解決方法？

    1）、開放位址法

    2）、再哈希法

    3）、鍊位址法

    4）、建立一個公共溢出區

4. int main()

   {

     if()

     {   

       printf("Hello ");

     }

     else

     {

       printf("World !!!");

     }

     return 0;

   }

   在if裡面請寫入語句 使得列印出  hello  world。

5. 今天10.19西山居筆試題：

   分别寫一個宏和函數來擷取元素個數 如count(a) 會得到a數組元素個數 。

6. 平均要取多少個(0,1)中的随機數才能讓和超過1。（答案： e 次，  其中e是自然對數的底數）

   

7. 今天支付寶10.20筆試題：漢諾塔一共為 2*N，2個一樣大小，有編号順序 每次隻能移動一個 大的不能疊在小得上面 移動完之後，相同大小的編号必須和原來一樣 問最小要移動多少次？ 如 A1 A2  B1 B2 C1 C2 ...... 這樣疊，A<B<C....   B不能放A上面，C不能放B A上面，移動到另外一個柱子後，還必須是 A1 A2  B1 B2 C1 C2 ....

8. socket程式設計的問題

   TCP連接配接建立後，調用send 5次，每次發100位元組，問recv最少要幾次，最多要幾次？

9. 迅雷筆試題：

   下面的程式可以從1....n中随機輸出m個不重複的數。請填空

   knuth(int n, int m) 

   {

       srand((unsigned int)time(0));

       for (int i=0; i<n; i++)

           if (            )

           {

              cout<<i<<endl;

               (                 );

           }

   }

10. 四個線程t1,t2,t3,t4,向4個檔案中寫入資料，t1隻能寫入1，t2隻能寫入2，t3隻能寫入3，t4隻能寫入4，對4個檔案A，B，C，D寫入如下内容

    A:123412341234.....

    B:234123412341....

    C:341234123412....

    D:412341234123....

    怎麼實作同步可以讓線程并行工作？

11. 比如一個數組[1,2,3,4,6,8,9,4,8,11,18,19,100]

    前半部分是是一個遞增數組，後面一個還是遞增數組，但整個數組不是遞增數組，那麼怎麼最快的找出其中一個數？

12. 今日10.21迅雷筆試題：  1、一棵二叉樹節點的定義（和平時我們定義的一樣的） 它給出了一棵二叉樹的根節點 說現在懷疑這棵二叉樹有問題 其中可能存在某些節點不隻有一個父親節點 現要你編寫一個函數判斷給定的二叉樹是否存在這樣的節點  存在則列印出其父親節點傳回true 否則傳回false

    列印節點形式：

    [目前節點][父親節點1][父親節點的父親節點][。。。]

    [目前節點][父親節點2][父親節點的父親節點][。。。]

      2、有一億個整數，請找出最大的1000個，要求時間越短越好，空間占用越少越好

13. 在頻繁使用小記憶體時，通常會先申請一塊大的記憶體，每次使用小記憶體時都從大記憶體裡取，最後大記憶體使用完後一次性釋放，用算法實作。

14. 今天亞馬遜A卷校招筆試題：

    輸入一個字元串，如何求最大重複出現的字元串呢？比如輸入ttabcftrgabcd,輸出結果為abc，canffcancd,輸出結果為can。

15. 今天10.22盛大：删除模式串中出現的字元，如“welcome to asted”,模式串為“aeiou”那麼得到的字元串為“wlcm t std"，要求性能最優。

16. 數組中的數分為兩組，讓給出一個算法，使得兩個組的和的差的絕對值最小 

    數組中的數的取值範圍是0<x<100，元素個數也是大于0， 小于100 

    比如a[]={2,4,5,6,7},得出的兩組數｛2，4，6｝和｛5，7｝，abs(sum(a1)-sum(a2))=0；

    比如｛2，5，6，10｝，abs（sum(2,10)-sum(5,6))=1,是以得出的兩組數分别為｛2，10｝和｛5，6｝。

17. 百度北京研發一道系統設計題，如何快速通路ipv6位址呢？ipv6位址如何存放？
18. 百度2012校招北京站筆試題系統設計：正常使用者端每分鐘最多發一個請求至服務端，服務端需做一個異常用戶端行為的過濾系統，設伺服器在某一刻收到用戶端A的一個請求，則1分鐘内的用戶端任何其它請求都需要被過濾，現知每一用戶端都有一個IPv6位址可作為其ID，用戶端個數太多，以至于無法全部放到單台伺服器的記憶體hash表中，現需簡單設計一個系統，使用支援高效的過濾，可使用多台機器，但要求使用的機器越少越好，請将關鍵的設計和思想用圖表和代碼表現出來。 

19. #include <iostream>

    using namespace std;

    class A

    {

    public:

    A(){cout<<"A"<<endl;}

    ~A(){cout<<"~A"<<endl;}

    };

    class B

    {

    public:

    B(A &a):_a(a)

    {

    cout<<"B"<<endl;

    }

    ~B(){cout<<"~B"<<endl;}

    private:

    A _a;

    };

    int main()

    {

    A a; 

    B b(a); 

    return 0;

    // 構造次序和析構次序是對稱的,這種題解答都是有技巧的.

    // 拷貝構造就不說了,構造過程是:

    // A A B ,那麼析構必然是對稱的：B A A。

    }

    

....     ok，以上所有任何參考答案若有問題，歡迎不吝指正。謝謝。日後，繼續整理十月下旬的各大IT公司的筆/面試題，持續更新，直到十月月底。祝所有諸君找到自己合适而滿意的offer，工作。July、2011.10.17。 複制 搜尋 複制 搜尋 複制 搜尋