騰訊實習筆試真題精選

2015騰訊實習筆試題

1. 關於二叉樹，下面説法正確的是

A. 對於N個節點的二叉樹，其高度為nlog2n;

B. 一個具有1025個節點的二叉樹，其高度範圍在11~1025之間

C. 二叉樹的先序遍歷是EFHIGJK，中序遍歷為HFIEJKG，該二叉樹的右子樹的根為G

D. 二叉樹中至少有一個節點的度為2

這個題目我的思路是BC，

A二叉樹不一定是滿二叉樹等，高度應該是範圍。

D選項其中如果只有一個樹根的二叉樹應該是反例。

2. 假設函數f1的時間複雜度O(n)，那麼f1*f1的時間複雜度為

A. O(n)B. O(n*n)C. O(n*log(n))D. 以上都不對

這個題目我的思路是A，討論後答案應該是D，因為f1的返回值不確定，如果是個數組當然複雜度就不同了。

3. 對下列四種排序方法，在排序中關鍵字比較次數與記錄初始化順序無關的是

A. 直接排序B. 二分法插入C. 快速排序D. 歸併排序

這個答案據説是BD，我的答案是D，因為一時反應不過來什麼是二分法插入。可以百度一下二分法插入，據説是考研的原題。

4. 已知一段文本有1382個字符，使用了1382個字節存儲，這段文本全部是由a、b、c、d、e字符組成，a 354次，b 483次，c 227次，d 96次，e 222次，對這5個字符使用哈夫曼編碼。則以下説法正確的是?

A. 使用哈夫曼編碼後，使用編碼值來存儲這段文本將花費最少的存儲空間、

B. 使用哈夫曼編碼後，a b c d e 這5個字符對應的編碼值是唯一確定的

C. 使用哈夫曼編碼後，a b c d e 這5個字符對應的編碼值可以有多套，但每個字符的編碼位數是確定的

D. b這個字符的編碼位數最短，d這個字符的哈夫曼編碼位數應該最長

5. 判斷單鏈表有沒有環的算法中，至少需要幾個指針

A. 1 B. 2 C. 3 D. 4

之前遇到過的一個算法題目，利用快慢的兩個人在環形的跑道上跑必定會再次相遇的原理。

6. 在編譯過程中，產生Parse tree的過程是

A. 語法分析 B. 語義分析階段C. 詞法分析D. 目標代碼生成階段

編譯原理的基本知識。

7. 閲讀下面代碼，程序會打印出來的值是

#include

Void f(char **p){

*p += 2;

Void main {

Char *a = { 123 , abc , 456 },**p;

p = a;

f(p);

printf( %s ,**p);

A. 123 B. abc C. 456 D. 3

指針的應用，a是二維數組的首位指針，首先取值之後變成第一行的首指針，+2移動至3的位置，輸出為3。

8. Char p1 = Tencent , void p2 = malloc((10)在32位機器上sizeof(p1)和sizeof(p2)對應的值是

A. 8：B. 4：1C. 8：4 D. 4：4

數組的長度和指針的長度，數組只有在傳參的時候才會退化為指針。sizeof的時候針對指針進行計算。

9. 現在有以下兩個函數，調用test的`結果是

Char* getMem(void) { Char * p = hello world ;

P[5] = 0x0;

Return p;

Voidtest(void) { Char *s = 0x0;

s = getMem;

Printf(s);

A. hello B. 無輸出 C. Hello0world D. 不確定

局部變量在函數返回的時候會刪除掉，指向內容就不確定了。答案應該是D。

10. 馮諾依曼體系結構計算機的基本原理是

A信息存儲 B 存儲智能 C 數字控制 D 存儲程序和程序控制

應該是D。

11. 求貢獻

12.下面哪種設計模式的定義為：定義對象間的一種一對多的關係，當一個對象改變時，其他依賴於他的對象都能夠得到通知並自動更新。

A. Visitor B. Adapter C. Observer D. Interpreter

觀察察者模式也就是C符合描述。

13.請看一下這一段C++代碼，如果編譯後程序在windows下運行，則一下説話正確的是

Char*p1 = 123456 ;

Char*p2 = (char*)malloc(10);

A. P1 he p2都存在棧中

B. P2指向的10個字節內存在棧中

C. 堆和棧在內存中的生長方向是相反的

D. 123456 這6個字符存儲在棧中

關於堆和棧的內存模型不是很瞭解...所以這個題目應該寫錯了。

14.將3個球隨機放入4個杯子中，則杯子中球的最大個數為2的概率是

A. 9/16 B. 3/4 C. 3/8 D. 3/16

這個和同學討論了以下也計算錯誤了，答案應該是A，其實利用反推法比較簡單。

15.對n個元素的數組進行快速排序，所需要的二外空間為

A. O(1)B. O(n)C. O(log(2n)D. O(n^2))

快速排序又稱為原地排序，本以為選擇應該是A，但是所謂原地排序也是遞歸搞定的，不知道需不需要算遞歸需要的深度，這樣這個題目就不確定了。

16.下面關於編譯器與解釋器的觀點，錯誤的是

A. 解釋器不產生目標程序，它直接執行源程序或者源程序的內部形式

B. 解釋程序和編譯程序的主要區別在於是否產生目標程序

C. 編譯器對高級語言程序的處理過程劃分成詞法分析、語法分析、語義分析，中間代碼生成、代碼優化、目標代碼生成幾個階段

D. 解釋器參與運行控制、程序執行的速度快

這個我選擇的是D。

17.假設系統中有5太設備，有多個進程需要使用2個設備，假定每個進程一次只能使用一台，則至多允許多少個進程來競爭這5個資源，而不會發生死鎖

A. 2 B. 3 C. 4 D. 5

4個設備避免競爭，必定有一個利用完之後會進行釋放。

18.下面哪些協議，存在源端口和目的端口是

A. IP B. TCP C. UDP D. ICMP協議

ICMP協議是網絡層的協議，所以BC，這個選錯了。

19.下列哪些sql是等價的

A. Select e ,rt from teacher A joincourse B on =

B. Select e ,rt from teacher A =

C. Select e ,rt from teacher wheretno in (select tno from course)

D. Select e ,rt from teacher where exsist (select * from course B where = );

這個詭異的sql語句不是很懂。

20.某一磁盤請求序列(磁道號):9818337、122、14、1246561，按照先來先服務FCFS磁盤調度對磁盤進行請求服務，假設當前磁頭在53道上，則磁臂總移動道數為：

A、169 B、208 C、64D、236

640?這個題目也太簡單了。

21.將一個C類網絡劃分為3個子網，每個子網最少要容納55台主機，使用的子網掩碼是：

A、 B、 C、 D、255.255.255. 192

192，保留6位計算得到的。3個子網不確定是怎麼得到。

22下列關於計算機硬件的描述，正確的是：

[next]

A、磁盤的平均存取時間指的是磁盤的尋道時間加上磁頭在某一磁道等待記錄扇區的時間

B、計算機的控制器是由多種部件組成，其中包括，指令寄存器、程序計數器和算數邏輯單元

C、一台計算機的字長是32位，表明該機器能處理的數值最多為4個字節

D、系統總線可以分為數據總線、地址總線和控制總線三類

這個題目不怎麼會，計算機體系結構的題目。

23、假設有關係模式R(A,B,C,D),其數據依賴集：F={(A,B)- 》C,C-》D},則關係模式R的規範化程度最高達到：

A.1NFB.2NF

C.3NF

這個也不太會，同學説選擇應該是B。

24.以下為一段瀏覽器中可運行的Javascript 代碼，則運行該段Javascript代碼的頁面彈出框中顯示的結果是：

Var obj = { key : 1 , value :2};

Var newObj = obj;

e += ;

alert(e);

A、2 B、12 C、3 D、21

javascript的題目，答案是D...我還以為是考引用的...

25.有足夠量的2分、5分、1分硬幣，如果想湊齊一元錢，可以有種方法

A、541 B、27C、1024 D、128

這個也不會計算了，組合數學的知識。

填空題(共5題，每題4分，共20分)

26、閲讀下面代碼：

#defineMAX_NUM 1000+1

int Temp = Max_NUM*10;

則Temp的值為( )

1010

27.某個單CPU操作系統搶佔式進程調度策略。現在有三個任務T1(優先級高)，T2(優先級中)，T3(優先級低)同時進入調度隊列，每個任務都需要佔用CPU時間10ms,10ms,13ms,然後再用CPU時間5ms，則T3從進入調度對了到完成需要ms(不考慮系統任務調度的開銷)

28.在一個採用頁式虛擬存儲管理的系統中，有一用户作業，它依次要訪問的也沒序列是1，2，3，4，1，2，5，1，2，3，4，5.假定分配給該作業的頁數為3且作業初始時未裝載頁面，那麼採用FIFO調度算法產生的缺頁中斷數為，採用LRU調度算法產生的缺頁中斷數為

9，10，當時寫了一個6,7，真是不認真...

29.

#include

class Base

public:

virtual int foo(int x){return x*10;}

int foo(char x[14]){return sizeof(x)+10;}

class Derived:public Base

int foo(int x){return x*20;}

virtual int foo(char x[10]){return sizeof (x)+20;}

int main(void)

Derived stDerived;

Base * pstBase=& stDerived;

char x[10];

printf( %d ,pstBase-》foo(100)+pstBase-》foo(x));

return 0;

在32位環境下，以上程序的輸出結果是

20XX

附加題(共2題，不計入總分)

31.珠寶商甲需要去鑑定一批41克以下的寶石(可能是41克以下不包括41克的任意重量)，他只能攜帶一個天平和四個砝碼去稱重，請問他會攜帶那些重量的砝碼?

-8是現在流行的編碼方式，下面是RFC2279對UTF-8編碼規則的規定，根據這個規則，中文字符 我 的unicode值為0X6211,utf-8編碼之後為0XE68891。

請回答一下問題：

A)英文字符 a ，其unicode的十六進制值為0X61，則其UTF-8編碼後的十六進制值為?

B)中文字符 騰 ，其unicode的十六進制值為0X817E，則其UTF-8編碼後的十六進制值為?

C)中文字符 訊 ，其unicode值經過UTF-8編碼之後為0XE8AEAF,則請問其unicode的十六進制值是?