騰訊筆試3(1)正式版

騰訊筆試題(三)騰訊2009校園招聘軟件開發(fā)職位方向筆試試題（A1卷）考試時長：120分鐘第一、單項選擇題。（每個選項3分，20個選項，共60分）1.在一個單鏈表中，若p所指的結點不是最后結點，在p所指結點之后插入s所指結點，則應執(zhí)行操作（）。A.s→link=p;p→link=sB.s→link=p→link;p→link=sC.s→link=p→link;p=sD.p→link=s;s→link=p2.在下列排序方法中，不穩(wěn)定的方法有（）。A.歸并排序與基數排序B.插入排序與希爾排序C.堆排序與快速排序D.選擇排序與冒泡排序3.在多級存儲體系中，“Cache-主存”結構的作用是解決（）的問題。A.主存容量不足B.輔存與CPU速度不匹配C.主存與輔存速度不匹配D.主存與CPU速度不匹配4.在需要經常查找結點的前驅與后繼的場合中，使用（）比較合適。A.單鏈表B.循環(huán)鏈表C.鏈棧5.帶頭結點的單鏈表head為空的判斷條件（）。A.head=NULLB.head→next=NULLC.head→next=headD.head<>NULL6.將一個遞歸算法改為對應的非遞歸算法時，通常需要使用（）。A.優(yōu)先隊列B.隊列C.循環(huán)隊列D.棧7.下列描述的不是鏈表的優(yōu)點是（）。A.邏輯上相鄰的結點物理上不必鄰接B.插入、刪除運算操作方便，不必移動結點C.所需存儲空間比線性表節(jié)省D.無需事先估計存儲空間的大小8.SQL語言集數據查詢、數據操作、數據定義和數據控制功能于一體，語句INSERT、DELETE、UPDATE實現（）功能。A.數據查詢B.數據控制C.數據定義D.數據操作9.設某種二叉樹有如下特點：每個結點要么是葉子結點，要么有2棵子樹。如果一棵這樣的二叉樹中有m（m>0）個葉子結點，那么該二叉樹上的結點總數為（）。A.2m+1B.2m-1C.2(m-1)D.2m10.TCP/IP協(xié)議棧的網絡層的主要功能是通過（）來完成的。A.IP協(xié)議B.TCP協(xié)議C.以太網協(xié)議D.IGP協(xié)議11.實現不同的作業(yè)處理方式（如：批處理、分時處理、實時處理等），主要是基于操作系統(tǒng)對（）管理采取了不同的策略。A.處理機B.存儲C.數據庫D.文件12.下面關于編譯系統(tǒng)和解釋系統(tǒng)的觀點中，錯誤的是（）。A.解釋程序不產生目標代碼，它直接執(zhí)行源程序或源程序的內部形式B.使用編譯系統(tǒng)時會區(qū)分編譯階段和運行階段C.一般來說，解釋系統(tǒng)比編譯系統(tǒng)復雜，但是可移植性好D.一般來說，建立在編譯基礎上的系統(tǒng)在執(zhí)行速度上要優(yōu)于建立在解釋執(zhí)行基礎上的系統(tǒng)13.散列文件使用散列函數將記錄的關鍵字值計算轉化為記錄的存放地址。因為散列函數不是一對一的關系，所以選擇好的（）方法是散列文件的關鍵。A.散列函數B.除余法中的質數C.沖突處理D.散列函數和沖突處理14.衡量查找算法效率的主要標準是（）。A.元素個數B.所需的存儲量C.平均查找長度D.算法難易程度15.對于#include<filename.h>和#include“filename.h”，以下說法錯誤的是（）。A.#include<filename.h>只搜索標準庫路徑B.#include“filename.h”只搜索用戶工作路徑C.#include<filename.h>搜索范圍比#include“filename.h”小D.兩者可能等價16.類定義的外部，可以被訪問的成員有（）。A.所有類成員B.private或protected的類成員C.public的類成員D.public或private的類成員17.下列的模板說明中，正確的有（）（兩個答案）。A.template<typenameT1，typenameT2>B.template<classT1,T2>C.template<classT1,classT2>D.template<typenameT1;typenameT2>18.中斷響應時間是指（）。A.從中斷處理開始到中斷處理結束所用的時間B.從發(fā)出中斷請求到中斷處理結束所用的時間C.從發(fā)出中斷請求到進入中斷處理所用的時間D.從中斷處理結束到再次中斷請求的時間19.（）面向對象程序設計語言不同于其他語言的主要特點。A.繼承性B.消息傳遞C.多態(tài)性D.封裝性20.TCP/IP模型的體系結構中，ICMP協(xié)議屬于（）。A.應用層B.網絡層C.數據鏈路層D.傳輸層第二、填空題。（每空4分，總計40分）1.閱讀下列說明和流程圖，將應填入（n）的字句寫在答題紙的對應欄內?！菊f明】正弦函數可以用如下的泰勒級數展開式來計算：下面的流程圖描述了利用上述展開式計算并打印sin(x)的近似值的過程，其中用ε>0）表示誤差要求，小于該誤差即可結束計算，打印結果?！玖鞒虉D】2.閱讀下列函數說明和C代碼，將應填入（n）處的字句寫在答題紙的對應欄內。【說明】設有一個帶表頭結點的雙向循環(huán)鏈表L,每個結點有4個數據成員：指向前驅結點的指針prior、指向后繼結點的指針next、存放數據的成員data和訪問頻度freq。所有結點的freq初始時都為0.每當在鏈表上進行一次L.Locate（x）操作時，令元素值x的結點的訪問頻度freq加1，并將該結點前移，鏈接到現它的訪問頻度相等的結點后面，使得鏈表中所有結點保持按訪問頻度遞減的順序排列，以使頻繁訪問的結點總是靠近表頭?！竞瘮怠縱oidLocate(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;}elseprintf(“Sorry.Notfind!\n”);\*沒找到*\}第三、附加題（30分）“背包問題”的基本描述是：有一個背包，能盛放的物品總重量為S,設有N件物品，其重量分別為w1，w2，…，wn，希望從N件物品中選擇若干物品，所選物品的重量之和恰能放入該背包，即所選物品的重量之和等于S。遞歸和非遞歸解法都能求得“背包問題”的一組解，試寫出“背包問題”的非遞歸解法。騰訊筆試題目zz1、請定義一個宏，比較兩個數a、b的大小，不能使用大于、小于、if語句2、如何輸出源文件的標題和目前執(zhí)行行的行數3、兩個數相乘，小數點后位數沒有限制，請寫一個高精度算法4、寫一個病毒5、有A、B、C、D四個人，要在夜里過一座橋。他們通過這座橋分別需要耗時1、2、5、10分鐘，只有一支手電，并且同時最多只能兩個人一起過橋。請問，如何安排，能夠在17分鐘內這四個人都過橋？2.如何輸出源文件的標題和目前執(zhí)行行的行數（不曉得怎么搞，在等兄弟給我答案在?。?.兩個數相乘，小數點后位數沒有限制，請寫一個高精度算法算法提示：//想法來自北師大一個同學給我看的另一個題目以及他的java程序。輸入stringa,stringb；計算stringc=a*b;返回c;1，紀錄小數點在a,b中的位置l1,l2，則需要小數點后移動位置數為l=length(a)+length(b)-l1-l2-2;2，去掉a,b中的小數點，（a,b小數點后移，使a,b變?yōu)檎麛担?，計算c=a*b;（要么用java的BigInterger搞,要么自己用C++寫高精度數乘法，超過百萬位，用FFT,我就不細說，這都預先寫過就別做了）4，輸出c,（注意在輸出倒數第l個數時，輸出一個小數點。若是輸出的數少于l個，就補0）4.寫一個病毒(沒搞過，^_^)5.讓你在100000000個浮點數中找出最大的10000個，要求時間復雜度優(yōu)。//本算法使用快排，O(n*lg(n))//最低可以找到線性算法，使用預先區(qū)域統(tǒng)計劃分！類試于構造QuadTrees!寫起來代碼會長些！#include<stdio.h>#include<stdlib.h>#defineMax100000000inta[Max+10];intcmp(constvoid*a,constvoid*b){int*x=(int*)a;int*y=(int*)b;return*x-*y;}intmain(){intn=0;while(scanf("%d",&a[n])==1)n++;qsort(a,n,4,cmp);for(inti=0;i<3;i++)printf("%d",a);return1;}5、有A、B、C、D四個人，要在夜里過一座橋。他們通過這座橋分別需要耗時1、2、5、10分鐘，只有一支手電，并且同時最多只能兩個人一起過橋。請問，如何安排，能夠在17分鐘內這四個人都過橋？Solution:TheFirstTime：A(1)和B(2)過橋，A(1)返回Cost：1+2TheSecondTime：C(5)和D(10)過橋，B(2)返回Cost：10+2TheThirdTimeA(1)和B(2)過橋Cost：2TotalTimeCost：(1+2)+(10+2)+2=17minutes1、請定義一個宏，比較兩個數a、b的大小，不能使用大于、小于、if語句#defineMax(a,b)(a/b)?a:b2、如何輸出源文件的標題和目前執(zhí)行行的行數intline=__LINE__;char*file=__FILE__;cout<<"filenameis"<<(file)<<",lineis"<3、兩個數相乘，小數點后位數沒有限制，請寫一