騰訊實習生筆試題

1、計算表達式x6+4x4+2x3+x+1最少需要做（）次乘法

A、3                 B、4                  C、5                       D、6

第一次乘法：x^2，第二次乘法：x^4=x^2 * x^2，第三次乘法：原式=x^2 * (x^4+4x^2+2x)+x+1，每一項的系數可以使用加法來實作。。

2、給定3個int類型的正整數x，y，z，對如下4組表達式判斷正确的選項（）

Int a1=x+y-z; int b1=x*y/z;

Int a2=x-z+y; int b2=x/z*y;

Int c1=x<<y>>z; int d1=x&y|z;

Int c2=x>>z<<y; int d2=x|z&y;

A、a1一定等于a2

B、b1一定定于b2

C、c1一定等于c2

D、d1一定等于d2

3、程式的完整編譯過程分為是：預處理，編譯，彙編等，如下關于編譯階段的編譯優化的說法中不正确的是（）

A、死代碼删除指的是編譯過程直接抛棄掉被注釋的代碼；

B、函數内聯可以避免函數調用中壓棧和退棧的開銷

C、For循環的循環控制變量通常很适合排程到寄存器通路

D、強度削弱是指執行時間較短的指令等價的替代執行時間較長的指令

4、 如下關于程序的描述不正确的是（）

A、程序在退出時會自動關閉自己打開的所有檔案

B、程序在退出時會自動關閉自己打開的網絡連結

C、程序在退出時會自動銷毀自己建立的所有線程

D、程序在退出時會自動銷毀自己打開的共享記憶體

5、 在如下8*6的矩陣中，請計算從A移動到B一共有多少種走法？要求每次隻能向上或着向右移動一格，并且不能經過P；

A、492

B、494

C、496

D、498

6、SQL語言中删除一個表的指令是（）

A、DROP TABLE

B、DELETE TABLE

C、DESTROY TABLE

D、REMOVE TABLE

7、某産品團隊由美術組、産品組、client程式組和server程式組4個小組構成，每次建構一套完整的版本時，需要各個組釋出如下資源。美術組想用戶端提供圖像資源（需要10分鐘），産品組向client組合server提供文字内容資源（同時進行，10分鐘），server和client源代碼放置在不同工作站上，其完整編譯時間均為10分鐘切編譯過程不依賴于任何資源，client程式（不包含任何資源）在編譯完畢後還需要完成對程式的統一加密過程（10分鐘）。可以請問，從要完成一次版本建構（client與server的版本代碼與資源齊備），至少需要多少時間（）

A、60分鐘

B、40分鐘

C、30分鐘

D、20分鐘

8、如下關于編譯連結的說法錯誤的是（）

A、編譯優化會使得編譯速度變慢

B、預編譯頭檔案可以優化程式的性能

C、靜态連結會使得可執行檔案偏大

D、動态連結庫會使程序啟動速度偏慢

9、如下關于連結的說法錯誤的是（）

A、一個靜态庫中不能包含兩個同名全局函數的定義

B、一個動态庫中不能包含兩個同名全局函數的定義

C、如果兩個靜态庫都包含一個同名全局函數，他們不能同時被連結

D、如果兩個動态庫都包含一個同名全局函數，他們不能同時被連結

10、排序算法的穩定是指，關鍵碼相同的記錄排序前後相對位置不發生改變，下面哪種排序算法是不穩定的（）

A、插入排序

B、冒泡排序

C、快速排序

D、歸并排序

11、下列說法中錯誤的是：（）

A、插入排序某些情況下複雜度為O（n）

B、排序二叉樹元素查找的複雜度可能為O（n）

C、對于有序清單的排序最快的是快速排序

D、在有序清單中通過二分查找的複雜度一定是O（n log2n）

12、在程式設計中，要對兩個16K×16K的多精度浮點數二維數組進行矩陣求和時，行優先讀取和列優先讀取的差別是（）

A、沒差別

B、行優先快

C、列優先快

D、2種讀取方式速度為随機值，無法判斷

13、字元串www.qq.com所有非空子串（兩個子串如果内容相同則隻算一個）個數是（）

A、1024

B、1018

C、55

D、50

14、TCP的關閉過程，說法正确的是（）

A、TIME_WAIT狀态稱為MSL（Maximum Segment Lifetime）等待狀态

B、對一個established狀态的TCP連接配接，在調用shutdown函數之前調用close接口，可以讓主動調用的一方進入半關閉狀态

C、主動發送FIN消息的連接配接端，收到對方回應ack之前不能發隻能收，在收到對方回複ack之後不能發也不能收，進入CLOSING狀态

D、在已經成功建立連接配接的TCP連接配接上，如果一端收到RST消息可以讓TCP的連潔端繞過半關閉狀态并允許丢失資料。

15、作業系統的一些特别端口要為特定的服務做預留，必須要root權限才能打開的端口描述正确的是（）

A、端口号在64512-65535之間的端口

B、所有小于1024的每個端口

C、RFC标準文檔中已經聲明特定服務的相關端口，例如http服務的80端口，8080端口等

D、所有端口都可以不受權限限制打開

16、圖書館有6人排隊，其中3人要還同一本書，書名為《面試寶典》，另外3人要借。問求能保證另外3人借到的種類。

Catalan數 C（2n , n）/( n+1 )   C(6,3)/4 = 5

5*3!*3! = 180

17、ack（3 , 3）的執行結果是多少？

[cpp] view plaincopy

1. int ack(int m,int n)  
2. {  
3.     if(m == 0)  
4.         return n + 1;  
5.     else if(n == 0)  
6.         return ack(m-1,1);  
7.     else  
8.         return ack(m - 1 , ack(m , n-1));  
9. }  

這個題目可以找規律的。。

18、如下SQL語句是需要列出一個論壇版面第一頁（每頁顯示20個）的文章（post）标題（title），并按照釋出（create_time）降序排列：

SELECT title FROM post( )create_time DESC( )0,20    order by  limit

19、為了某項目需要，我們準備構造了一種面向對象的腳本語言，例如，對所有的整數，我們都通過Integer類型的對象來描述。在計算“1+2”時，這裡的“1”，“2”和結果“3”分别為一個Integer對象。為了降低設計複雜度，我們決定讓Integer對象都是隻讀對象，也即在計算a=a+b後，對象a引用的是一個新的對象，而非改a所指對象的值。考慮到性能問題，我們又引入兩種優化方案：（1）對于數值相等的Integer對象，我們不會重複建立。例如，計算“1+1”，這裡兩個“1”的引用的是同一個對象——這種設計模式叫做（）；（2）腳本語言解析器啟動時，預設建立數值範圍[1,32]的32個Integer對象。現在，假設我們要計算表達式“1+2+3+…+40”，在計算過程需要建立的Integer對象個數是（）。

享元模式  40。1到7以及他們的和是不用建立的，從8開始，28（是1到7的和）+8=36，36需要建立，36+9=45，45需要建立…依次類推，在加數是32之前（含32）需要建立的對象是32-8+1=25，某數+32=某數之後33至40所表示的加數也要建立，這樣有8個加數 + 8個和，共有16個數需要建立，注意，加數中包含36，這個我們已經建立了，是以有25+8+8-1=40個數的對象需要建立。

20、甲、乙兩個人在玩猜數字遊戲，甲随機寫了一個數字，在[1，100]區間之内，将這個數字寫在了一張紙上，然後乙來猜。

如果乙猜的數字偏小的話，甲會提示：“數字偏小”

一旦乙猜的數字偏大的話，甲以後就再也不會提示了，隻會回答“猜對 或 猜錯”

問： 乙至少猜    多少次  猜可以準确猜出這個數字，在這種政策下，  乙猜的第一個數字是多少？？？

答案：猜測序列是14,、27、39、50、60、69、77、84、90、95、99

因為無論第幾次猜大了，最終的總次數總是14。     這個題目類似于一道Google面試題 ：  扔玻璃球求最高樓層。。

一道關于動态規劃的面試題——Google面試題：扔玻璃珠

某幢大樓有100層。你手裡有兩顆一模一樣的玻璃珠。當你拿着玻璃珠在某一層往下扔的時候，一定會有兩個結果，玻璃珠碎了或者沒碎。這幢大樓有個臨界樓層。低于它的樓層，往下扔玻璃珠，玻璃珠不會碎，等于或高于它的樓層，扔下玻璃珠，玻璃珠一定會碎。玻璃珠碎了就不能再扔。現在讓你設計一種方式，使得在該方式下，最壞的情況扔的次數比其他任何方式最壞的次數都少。也就是設計一種最有效的方式。

首先，為了儲存下一顆玻璃珠自己玩，就采用最笨的辦法吧：從第一層開始試，每次增加一層，當哪一層扔下玻璃珠後碎掉了，也就知道了。不過最壞的情況扔的次數可能為100。

當然，為了這一顆玻璃珠代價也高了點，還是采取另外一種辦法吧。随便挑一層，假如為N層，扔下去後，如果碎了，那就隻能從第一層開始試了，最壞的情況可能為N。假如沒碎，就一次增加一層繼續扔吧，這時最壞的情況為100-N。也就是說，采用這種辦法，最壞的情況為max{N, 100-N+1}。之是以要加一，是因為第一次是從第N層開始扔。

不過還是覺得不夠好，運氣好的話，挑到的N可能剛好是臨界樓層，運氣不好的話，要扔的次數還是很多。不過回過頭看看第二種方式，有沒有什麼發現。假如沒摔的話，不如不要一次增加一層繼續扔吧，而是采取另外一種方式：把問題轉換為100-N，在這裡面找臨界樓層，這樣不就把問題轉換成用遞歸的方式來解決嗎？看下面：

假如結果都儲存在F[101]這個數組裡面，那麼：

F[N]=100-N，

F[100]=min（max（1，1+F[N-1]），max（2，1+F[N-2]），……，max（N-1，1+F[1]））;

看出來了沒有，其實最終就是利用動态規劃來解決這個問題。

下面是自己随便寫的C++代碼：

[cpp] view plaincopy

1. #include<iostream>  
2. using namespace std;  
3. int dp[101] = { 0 };  
4. void solve()  
5. {  
6.     int i , j , k;  
7.     for(i = 2 ; i < 101 ; ++i)  
8.     {  
9.         dp[i] = i;  
10.         for(j = 1 ; j < i ; ++j)  
11.         {  
12.             k = (j>=(1 + dp[i-j])) ? j : (1 + dp[i-j]);  
13.             if(dp[i] > k)  
14.                 dp[i] = k;  
15.         }  
16.     }  
17. }  
18. int main(void)  
19. {  
20.     dp[0] = 0 , dp[1] = 1;  
21.     solve();  
22.     printf("%d\n",dp[100]);  
23.     return 0;  
24. }  

輸出結果為14。也就是說，最好的方式隻要試14次就能夠得出結果了。

答案是先從14樓開始抛第一次；如果沒碎，再從27樓抛第二次；如果還沒碎，再從39樓抛第三次；如果還沒碎，再從50樓抛第四次；如此，每次間隔的樓層少一層。這樣，任何一次抛棋子碎時，都能確定最多抛14次可以找出臨界樓層。

證明如下：

1、第一次抛棋子的樓層：最優的選擇必然是間隔最大的樓層。比如，第一次如果在m層抛下棋子，以後再抛棋子時兩次樓層的間隔必然不大于m層（大家可以自己用反證法簡單證明）

2、從第二次抛棋子的間隔樓層最優的選擇必然比第一次間隔少一層，第三次的樓層間隔比第二次間隔少一層，如此，以後每次抛棋子樓層間隔比上一次間隔少一層。（大家不妨自己證明一下）

3、是以，設n是第一次抛棋子的最佳樓層，則n即為滿足下列不等式的最小自然數：

  不等式如下：  1+2+3+...+(n-1)+n  >=   100

由上式可得出n=14

即最優的政策是先從第14層抛下，最多抛14次肯定能找出臨界樓層。

21、給定一個數組a[N],我們希望構造數組b[N]，其中b[i]=a[0]*a[1]*...*a[N-1]/a[i]。在構造過程：

不允許使用除法；

要求O(1)空間複雜度和O(n)時間複雜度；

除周遊計數器與a[N] b[N]外，不可使用新的變量(包括棧臨時變量、對空間和全局靜态變量等)；

請用程式實作并簡單描述。

[cpp] view plaincopy

1. void makeArray(int a[],int b[],int len)  
2. {  
3.     int i;  
4.     b[0] = 1;  
5.     for(i = 1 ; i < len ; ++i)  
6.         b[i] = b[i-1] * a[i-1];    // b[0] = 1 , b[i] = a[0]*a[1]*...*a[i-1]  
7.     a[len - 1] = a[len - 1]^a[len - 2];   //不使用中間變量，通過位運算來交換兩個變量  
8.     a[len - 2] = a[len - 1]^a[len - 2];  
9.     a[len - 1] = a[len - 1]^a[len - 2];  
10.     for(i = len - 3 ; i >= 0 ; --i)  
11.     {  
12.         a[len - 1] = a[i + 1] * a[len - 1];  
13.         a[i] = a[i]^a[len - 1];    //交換兩個變量  
14.         a[len - 1] = a[i]^a[len - 1];  
15.         a[i] = a[i]^a[len - 1];  
16.     }  
17.     a[len - 1 ] = 1;    //a[len - 1 ] = 1 , a[i] = a[i+1]*a[i+2]*...*a[len-1]  
18.     for(i = 0 ; i < len ; ++i)  
19.         b[i] = a[i] * b[i];  
20. }  

方法二：

[cpp] view plaincopy

1. //方法二，保持a數組不變  
2. void makeArray(int a[],int b[],int len)  
3. {  
4.     int i;  
5.     b[0] = 1;  
6.     for(i = 1 ; i < len ; ++i)  
7.     {  
8.         b[0] *= a[i-1];  
9.         b[i] = b[0];      // b[i] = a[0]*a[1]*...*a[i-1]  
10.     }  
11.     b[0] = 1;  
12.     for(i = len - 2 ; i > 0 ; --i)  
13.     {  
14.         b[0] *= a[i+1];   // b[0] = a[i+1]*a[i+2]...*a[len-1]  
15.         b[i] *= b[0];     // b[i] = a[0]*a[1]*...*a[i-1]*a[i+1]*...*a[len-1]  
16.     }  
17.     b[0] *= a[1];   
18. }  

方法三：

[cpp] view plaincopy

1. void makeArray(int a[],int b[],int len)  
2. {  
3.     int i;  
4.     b[0] = 1;  
5.     for(i = 1 ; i < len ; ++i)  
6.     {  
7.         b[i] = b[i-1] * a[i-1];    // b[i] = a[0]*a[1]*...*a[i-1]  
8.     }  
9.     b[0] = a[len - 1];  
10.     for(i = len - 2 ; i > 0 ; --i)  
11.     {  
12.         b[i] *= b[0];     // b[i] = a[0]*a[1]*...*a[i-1]*a[i+1]*...*a[len-1]  
13.         b[0] *= a[i];     // b[0] = a[i+1]*a[i+2]...*a[len-1]  
14.     }  
15. }  

22、20世紀60年代，美國心理學家米爾格蘭姆設計了一個連鎖信件實驗。米爾格蘭姆把信随即發送給住在美國各城市的一部分居民，信中寫有一個波士頓股票經紀人的名字，并要求每名收信人把這封信寄給自己認為是比較接近這名股票經紀人的朋友。這位朋友收到信後再把信寄給他認為更接近這名股票經紀人的朋友。最終，大部分信件都寄到了這名股票經紀人手中，每封信平均經受6.2詞到達。于是，米爾格蘭姆提出六度分割理論，認為世界上任意兩個人之間建立聯系最多隻需要6個人。

假設QQ号大概有10億個注冊使用者，存儲在一千台機器上的關系資料庫中，每台機器存儲一百萬個使用者及其的好友資訊，假設使用者的平均好友個數大約為25人左右。

第一問：請你設計一個方案，盡可能快的計算存儲任意兩個QQ号之間是否六度（好友是1度）可達，并得出這兩位使用者六度可達的話，最短是幾度可達。

第二問：我們希望得到平均每個使用者的n度好友個數，以增加對使用者更多的了解，現在如果每台機器一秒鐘可以傳回一千條查詢結果，那麼在10天的時間内，利用給出的硬體條件，可以統計出使用者的最多幾度好友個數？如果希望得到更高的平均n度好友個數，可以怎樣改進方案？

23、段頁式虛拟存儲管理方案的特點。

答：空間浪費小、存儲共享容易、存儲保護容易、能動态連接配接。

       段頁式管理是段式管理和頁式管理結合而成，兼有段式和頁式管理的優點，每一段分成若幹頁，再按頁式管理，頁間不要求連續(能動态連接配接);用分段方法配置設定管理作業，用分頁方法配置設定管理記憶體(空間浪費小)。

       段頁式管理采用二維位址空間，如段号(S)、頁号(P)和頁内單元号(D);系統建兩張表格每一作業一張段表，每一段建立一張頁表，段表指出該段的頁表在記憶體中的位置;位址變換機構類似頁式機制，隻是前面增加一項段号。是以存儲共享容易、存儲保護容易。

轉載請标明出處，原文位址：http://blog.csdn.net/hackbuteer1/article/details/7438986