騰訊筆試題2014

1、騰訊2014校園招聘軟件開發(fā)類筆試試題考試時長：120分鐘一不定項選擇題（共25題，每題4分，共100分，少選、錯選、多選均不得分）1已知一棵二叉樹，如果先序遍歷的節(jié)點順序是：ADCEFGHB，中序遍歷是：CDFEGHAB，則后序遍歷結(jié)果為：（D）ACFHGEBDABCDFEGHBACFGHCDEBADCFHGEDBA2下列哪兩個數(shù)據(jù)結(jié)構(gòu)，同時具有較高的查找和刪除性能？（CD）A有序數(shù)組B有序鏈表CAVL樹DHash表3下列排序算法中，哪些時間復(fù)雜度不會超過nlogn？（BC）A快速排序B堆排序C歸并排序D冒泡排序4初始序列為18625473一組數(shù)采用堆排序，當(dāng)建堆（小根堆）完畢時，堆所對應(yīng)的

2、二叉樹中序遍歷序列為：（A）A83251647B32851467C38251674D823514765當(dāng)n=5時，下列函數(shù)的返回值是：（A）intfoo(intn)if(nlchild!= NULL) if (t-rchild!= NULL) N2+; else NL+; else if (t-rchild!=NULL) NR+; else N0+; if(t-lchild!=NULL) count(t-lchild); if(t-rchild!=NULL) count(t-rchild); /* call form :if(t!=NULL) count(t);*/ 三、其他方向簡答題（共2題

3、，每題20分），選作題，不計入總分）1請設(shè)計一個排隊系統(tǒng)，能夠讓每個進入隊伍的用戶都能看到自己在隊列中所處的位置和變化，隊伍可能隨時有人加入和退出；當(dāng)有人退出影響到用戶的位置排名時需要及時反饋到用戶。2A，B兩個整數(shù)集合，設(shè)計一個算法求他們的交集，盡可能的高效。1. 關(guān)于二叉樹，下面說法正確的是（）A.對于N個節(jié)點的二叉樹，其高度為nlog2n;B. 一個具有1025個節(jié)點的二叉樹，其高度范圍在111025之間C.二叉樹的先序遍歷是EFHIGJK，中序遍歷為HFIEJKG，該二叉樹的右子樹的根為GD.二叉樹中至少有一個節(jié)點的度為22. 假設(shè)函數(shù)f1的時間復(fù)雜度O(n)，那么f1*f1的時間復(fù)雜

4、度為（）A.O(n)B.O(n*n)C.O(n*log(n)D.以上都不對3. 對下列四種排序方法，在排序中關(guān)鍵字比較次數(shù)與記錄初始化順序無關(guān)的是（）A.直接排序B.二分法插入C.快速排序D.歸并排序4. 已知一段文本有1382個字符，使用了1382個字節(jié)存儲，這段文本全部是由a、b、c、d、e字符組成，a 354次，b483次，c 227次，d 96次，e 222次，對這5個字符使用哈夫曼編碼。則以下說法正確的是？（）A.使用哈夫曼編碼后，使用編碼值來存儲這段文本將花費最少的存儲空間、B. 使用哈夫曼編碼后，ab c d e 這5個字符對應(yīng)的編碼值是唯一確定的C.使用哈夫曼編碼后，ab c

5、d e 這5個字符對應(yīng)的編碼值可以有多套，但每個字符的編碼位數(shù)是確定的D.b這個字符的編碼位數(shù)最短，d這個字符的哈夫曼編碼位數(shù)應(yīng)該最長5. 判斷單鏈表有沒有環(huán)的算法中，至少需要幾個指針（）A.1 B. 2C.3 D.46. 在編譯過程中，產(chǎn)生Parsetree的過程是（）A.語法分析B. 語義分析階段C.詞法分析D.目標代碼生成階段7. 閱讀下面代碼，程序會打印出來的值是（）1. #include2. Void f(char *p)3. *p += 2;4. 5. Void main() 6. Char *a = “123”,”abc”,”456”,*p;7. p = a;8. f(p);9.

6、 printf(“%srn”,*p);10.復(fù)制代碼A.123B.abcC.456D.38. Char p1 = “Tencent”, void p2= malloc(10)在32位機器上sizeof(p1)和sizeof(p2)對應(yīng)的值是（）A.8：0B. 4：10 C.8：4D.4：49. 現(xiàn)在有以下兩個函數(shù)，調(diào)用test的結(jié)果是（）1. Char* getMem(void) Char * p = “hello world ”;2. P5 = 0x0;3. Return p;4. 5. Voidtest(void) Char *s = 0x0;6. s = getMem();7. Prin

7、tf(s);8. 復(fù)制代碼A.hello B. 無輸出C.Hello0world D.不確定10.馮諾依曼體系結(jié)構(gòu)計算機的基本原理是（）A信息存儲B 存儲智能 C 數(shù)字控制 D 存儲程序和程序控制11. 求貢獻12.下面哪種設(shè)計模式的定義為：定義對象間的一種一對多的關(guān)系，當(dāng)一個對象改變時，其他依賴于他的對象都能夠得到通知并自動更新。（）A.Visitor B.AdapterC.ObserverD.Interpreter13.請看一下這一段C+代碼，如果編譯后程序在windows下運行，則一下說話正確的是（）Char*p1 = “123456”;Char*p2 = (char*)malloc(1

8、0);A.P1 he p2都存在棧中B. P2指向的10個字節(jié)內(nèi)存在棧中C.堆和棧在內(nèi)存中的生長方向是相反的D.“123456”這6個字符存儲在棧中14.將3個球隨機放入4個杯子中，則杯子中球的最大個數(shù)為2的概率是（）A.9/16B. 3/4C.3/8 D.3/1615.對n個元素的數(shù)組進行快速排序，所需要的二外空間為（）A.O(1)B.O(n)C.O(log(2n)D.O(n2)16.下面關(guān)于編譯器與解釋器的觀點，錯誤的是（）A.解釋器不產(chǎn)生目標程序，它直接執(zhí)行源程序或者源程序的內(nèi)部形式B. 解釋程序和編譯程序的主要區(qū)別在于是否產(chǎn)生目標程序C.編譯器對高級語言程序的處理過程劃分成詞法分析、語

9、法分析、語義分析，中間代碼生成、代碼優(yōu)化、目標代碼生成幾個階段D.解釋器參與運行控制、程序執(zhí)行的速度快17.假設(shè)系統(tǒng)中有5太設(shè)備，有多個進程需要使用2個設(shè)備，假定每個進程一次只能使用一臺，則至多允許多少個進程來競爭這5個資源，而不會發(fā)生死鎖（）A.2B.3C.4 D.518.下面哪些協(xié)議，存在源端口和目的端口是（）A.IPB.TCPC.UDPD.ICMP協(xié)議19.下列哪些sql是等價的（）A.Select A.tname ,A.depart fromteacher A joincourse B on B.tno = .A.tnoB. Select A.tname ,A.depart fromt

10、eacher A whereA.tno = course.tnoC.Select A.tname ,A.depart fromteacher wheretno in (select tno from course)D.Select A.tname ,A.depart fromteacher where exsist (select * from course B where B.tno = A.tno);20.某一磁盤請求序列(磁道號):98、 183、37、122、14、124、 65、 61，按照先來先服務(wù)FCFS磁盤調(diào)度對磁盤進行請求服務(wù)，假設(shè)當(dāng)前磁頭在53道上，則磁臂總移動道數(shù)為：（）

11、A、169 B、208 C、640 D、23621.將一個C類網(wǎng)絡(luò)劃分為3個子網(wǎng)，每個子網(wǎng)最少要容納55臺主機，使用的子網(wǎng)掩碼是：（）A、48 B、24C、24D、255.255.255. 19222下列關(guān)于計算機硬件的描述，正確的是：（）A、磁盤的平均存取時間指的是磁盤的尋道時間加上磁頭在某一磁道等待記錄扇區(qū)的時間B、計算機的控制器是由多種部件組成，其中包括，指令寄存器、程序計數(shù)器和算數(shù)邏輯單元C、一臺計算機的字長是32位，表明該機器能處理的數(shù)值最多為4個字節(jié)D、系統(tǒng)總線可以分為數(shù)據(jù)總線、地址總線和控制總線三類23

12、、假設(shè)有關(guān)系模式R(A,B,C,D),其數(shù)據(jù)依賴集：F=(A,B)-C,C-D,則關(guān)系模式R的規(guī)范化程度最高達到：（）A.1NFB.2NFC.3NFD.BCNF24.以下為一段瀏覽器中可運行的Javascript 代碼，則運行該段Javascript代碼的頁面彈出框中顯示的結(jié)果是：（）Var obj = “key”:”1”,”value”:2;Var newObj = obj;newObj.value += obj.key;alert(obj.value);A、2 B、12 C、3 D、2125.有足夠量的2分、5分、1分硬幣，如果想湊齊一元錢，可以有（）種方法A、541 B、270C、102

13、4 D、128填空題（共5題，每題4分，共20分）26、閱讀下面代碼：#defineMAX_NUM 1000+1intTemp = Max_NUM*10;則Temp的值為（ ）27.某個單CPU操作系統(tǒng)搶占式進程調(diào)度策略?，F(xiàn)在有三個任務(wù)T1（優(yōu)先級高），T2（優(yōu)先級中），T3（優(yōu)先級低） 同時進入調(diào)度隊列，每個任務(wù)都需要占用CPU時間10ms,10ms,13ms,然后再用CPU時間5ms，則T3從進入調(diào)度對了到完成需要（）ms(不 考慮系統(tǒng)任務(wù)調(diào)度的開銷)28.在一個采用頁式虛擬存儲管理的系統(tǒng)中，有一用戶作業(yè)，它依次要訪問的也沒序列是1，2，3，4，1，2，5，1，2，3，4，5.假定分配給該

14、作業(yè) 的頁數(shù)為3且作業(yè)初始時未裝載頁面，那么采用FIFO調(diào)度算法產(chǎn)生的缺頁中斷數(shù)為（），采用LRU調(diào)度算法產(chǎn)生的缺頁中斷數(shù)為（）29.1. #include 2. class Base3. 4. public:5. virtual int foo(int x)return x*10;6. int foo(char x14)return sizeof(x)+10;7. ;8. class Derived:public Base9. 10.int foo(int x)return x*20;11.virtual int foo(char x10)return sizeof (x)+20;12.;13.int main(void)14.15.DerivedstDerived;16.Base * pstBase=& stDerived;17.char x10;18.printf(“%dn”,pstBase-foo(100)+pstBase-foo(x);19.return 0;20.復(fù)制代碼在32位環(huán)境下，以上程序的輸出結(jié)果是（）附加題（共2題，不計入總分）31.珠寶商甲需要去鑒定一批41克以下的寶石（可能是41克以下不包括41克的任意重量），他只能攜帶一個天平和四個砝碼去稱重，請問他會攜帶那些重量的砝碼？32.UTF-8是現(xiàn)在流行的編