騰訊筆試3(1)正式版

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