騰訊筆試題三、四

騰訊筆試題(三)

騰訊2009 校園招聘

軟件開發職位方向筆試試題(A1 卷) 考試時長：120 分鐘

第一、單項選擇題。(每個選項3 分，20 個選項，共60 分)

1. 在一個單鏈表中，若p 所指的結點不是最後結點，在p 所指結點之後插入s 所指結點，

則應執行操作( )。

A. s →link = p ; p →link = s B. s →link = p →link ; p →link = s

C. s →link = p →link ; p = s D. p →link = s ; s →link = p

2. 在下列排序方法中，不穩定的方法有( )。

A. 歸併排序與基數排序B. 插入排序與希爾排序

C. 堆排序與快速排序D. 選擇排序與冒泡排序

3. 在多級存儲體系中，“Cache-主存”結構的作用是解決( )的問題。

A. 主存容量不足B. 輔存與CpU 速度不匹配C. 主存與輔存速度不匹配

D. 主存與CpU 速度不匹配

4. 在需要經常查找結點的前驅與後繼的場合中，使用( )比較合適。

A. 單鏈表B. 循環鏈表C. 鏈棧

5. 帶頭結點的單鏈表head 為空的判斷條件( )。

A. head = NULL B. head →next = NULL

C. head →next = head D. head <> NULL

6. 將一個遞歸算法改為對應的非遞歸算法時，通常需要使用( )。

A. 優先隊列B. 隊列C. 循環隊列D. 棧

7. 下列描述的不是鏈表的優點是( )。

A. 邏輯上相鄰的結點物理上不必鄰接

B. 插入、刪除運算操作方便，不必移動結點

C. 所需存儲空間比線性表節省

D. 無需事先估計存儲空間的大小

8. SQL 語言集數據查詢、數據操作、數據定義和數據控制功能於一體，語句INSERT、

DELETE、UpDATE 實現( )功能。

A. 數據查詢B. 數據控制C. 數據定義D. 數據操作

9. 設某種二叉樹有如下特點：每個結點要麼是葉子結點，要麼有2 棵子樹。如果一棵這樣

的二叉樹中有m(m>0)個葉子結點，那麼該二叉樹上的結點總數為( )。

A. 2m+1 B. 2m-1 C. 2(m-1) D. 2m

10. TCp/Ip 協議棧的網絡層的主要功能是通過( )來完成的。

A. Ip 協議B. TCp 協議C. 以太網協議D. IGp 協議

11. 實現不同的作業處理方式(如：批處理、分時處理、實時處理等)，主要是基於操作系

統對( )管理採取了不同的策略。

A. 處理機B. 存儲C. 數據庫D. 文件

12. 下面關於編譯系統和解釋系統的觀點中，錯誤的是( )。

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

B. 使用編譯系統時會區分編譯階段和運行階段

C. 一般來説，解釋系統比編譯系統複雜，但是可移植性好

D. 一般來説，建立在編譯基礎上的.系統在執行速度上要優於建立在解釋執行基礎上的系統

13. 散列文件使用散列函數將記錄的關鍵字值計算轉化為記錄的存放地址。因為散列函數不

是一對一的關係，所以選擇好的( )方法是散列文件的關鍵。

A. 散列函數B. 除餘法中的質數C. 衝突處理D. 散列函數和衝突處理

14. 衡量查找算法效率的主要標準是( )。

A. 元素個數B. 所需的存儲量C. 平均查找長度D. 算法難易程度

15. 對於#include和#include “filename.h”，以下説法錯誤的是( )。

A. #include只搜索標準庫路徑

B. #include “filename.h”只搜索用户工作路徑

C. #include搜索範圍比#include “filename.h”小

D. 兩者可能等價

16. 類定義的外部，可以被訪問的成員有( )。

A. 所有類成員B. private 或protected 的類成員

C. public 的類成員D. public 或private 的類成員

17. 下列的模板説明中，正確的有( )( 兩個答案)。

A. templateB. template

C. templateD. template

18. 中斷響應時間是指( )。

A. 從中斷處理開始到中斷處理結束所用的時間

B. 從發出中斷請求到中斷處理結束所用的時間

C. 從發出中斷請求到進入中斷處理所用的時間

D. 從中斷處理結束到再次中斷請求的時間

19. ( )面向對象程序設計語言不同於其他語言的主要特點。

A. 繼承性B. 消息傳遞C. 多態性D. 封裝性

20. TCp/Ip 模型的體系結構中，ICMp 協議屬於( )。

A. 應用層B. 網絡層C. 數據鏈路層D. 傳輸層

第二、填空題。(每空4 分，總計40 分)

1. 閲讀下列説明和流程圖，將應填入(n)的字句寫在答題紙的對應欄內。

【説明】

正弦函數可以用如下的泰勒級數展開式來計算：

下面的流程圖描述了利用上述展開式計算並打印sin (x )的近似值的過程，其中用ε>0)表示誤差要求，小於該誤差即可結束計算，打印結果。

【流程圖】

2. 閲讀下列函數説明和C 代碼，將應填入(n)處的字句寫在答題紙的對應欄內。

【説明】設有一個帶表頭結點的雙向循環鏈表L,每個結點有4 個數據成員：指向前驅結點

的指針prior、指向後繼結點的指針next、存放數據的成員data 和訪問頻度freq。所有結點

的freq 初始時都為0.每當在鏈表上進行一次te(x)操作時，令元素值x 的結點的訪

問頻度freq 加1，並將該結點前移，鏈接到現它的訪問頻度相等的結點後面，使得鏈表中所

有結點保持按訪問頻度遞減的順序排列，以使頻繁訪問的結點總是靠近表頭。

【函數】

void Locate(int &x)

{ <結點類型説明>

*p=first->next;

while(p!=first && 1 ) p=p->next;

if (p!=first)

{ 2 ;

<結點類型説明>

*current=p;

current->prior->next=current->next;

current->next->prior=current->prior;

p=current->prior;

while(p!=first && 3 ) p=p->prior;

current->next= 4 ;

current->prior=p;

p->next->prior=current;

p->next= 5 ;

}

else

printf(“Sorry. Not find!n”); *沒找到*

}

第三、附加題(30 分)

“揹包問題”的基本描述是：有一個揹包，能盛放的物品總重量為S,設有N 件物品，其重

量分別為w1，w2，…，wn，希望從N 件物品中選擇若干物品，所選物品的重量之和恰能

放入該揹包，即所選物品的重量之和等於S。遞歸和非遞歸解法都能求得“揹包問題”的一

組解，試寫出“揹包問題”的非遞歸解法。

騰訊筆試題目zz

1、請定義一個宏，比較兩個數a、b 的大小，不能使用大於、小於、if 語句

2、如何輸出源文件的標題和目前執行行的行數

3、兩個數相乘，小數點後位數沒有限制，請寫一個高精度算法

4、寫一個病毒

5、有A、B、C、D 四個人，要在夜裏過一座橋。他們通過這座橋分別需要耗時1、2、5、10

分鐘，只有一支手電，並且同時最多隻能兩個人一起過橋。請問，如何安排，能夠在17 分

鍾內這四個人都過橋?

2.如何輸出源文件的標題和目前執行行的行數(不曉得怎麼搞，在等兄弟給我答案在!)

3.兩個數相乘，小數點後位數沒有限制，請寫一個高精度算法算法提示：

//想法來自北師大一個同學給我看的另一個題目以及他的java 程序。

輸入string a, string b; 計算string c=a*b; 返回c;

1， 紀錄小數點在a,b 中的位置l1,l2， 則需要小數點後移動位置數為

l=length(a)+length(b)-l1-l2-2;

2， 去掉a,b 中的小數點，(a,b 小數點後移，使a,b 變為整數)

3， 計算c=a*b; (要麼用java 的BigInterger 搞, 要麼自己用C++寫高精度數乘法，超

過百萬位，用FFT,我就不細説，這都預先寫過就別做了)

4， 輸出c,(注意在輸出倒數第l 個數時，輸出一個小數點。若是輸出的數少於l 個，

就補0)

4.寫一個病毒(沒搞過，^_^)

5.讓你在100000000 個浮點數中找出最大的10000 個，要求時間複雜度優。

//本算法使用快排，O(n*lg(n))

//最低可以找到線性算法，使用預先區域統計劃分!類試於構造Quad Trees! 寫起來代碼

會長些!

#include

#include

#define Max 100000000

int a[Max+10];

int cmp(const void *a, const void *b)

{

int *x = (int *) a;

int *y = (int *) b;

return *x-*y;

}

int main()

{

int n=0;

while(scanf("%d",&a[n])==1) n++;

qsort(a,n,4,cmp);

for(int i=0;i<3;i++) printf("%d",a);

return 1;

}

5、有A、B、C、D 四個人，要在夜裏過一座橋。他們通過這座橋分別需要耗時1、2、5、10分鐘，只有一支手電，並且同時最多隻能兩個人一起過橋。請問，如何安排，能夠在17 分鐘內這四個人都過橋?

Solution:

The First Time： A(1)和B(2)過橋，A(1)返回Cost：1+2

The Second Time： C(5)和D(10)過橋，B(2)返回Cost：10+2

The Third Time A(1)和B(2)過橋Cost：2

Total Time Cost： (1+2)+(10+2)+2=17 minutes

1、請定義一個宏，比較兩個數a、b 的大小，不能使用大於、小於、if 語句

#define Max(a,b) ( a/b)?a:b

2、如何輸出源文件的標題和目前執行行的行數

int line = __LINE__;

char *file = __FILE__;

cout<<"file name is "<<(file)<<",line is "<

3、兩個數相乘，小數點後位數沒有限制，請寫一個高精度算法

4、寫一個病毒

while (1)

{

int *p = new int[10000000];

}

5、不使用額外空間,將A,B 兩鏈表的元素交*歸併

6、將樹序列化轉存在數組或鏈表中

struct st{

int i;

short s;

char c;

};

sizeof(struct st);

7、

char * p1;

void * p2;

int p3