騰訊筆試題2014

1、騰訊2014校園招聘軟件開發(fā)類筆試試題考試時(shí)長：120分鐘一 不定項(xiàng)選擇題（共25題，每題4分，共100分，少選、錯(cuò)選、多選均不得分）1 已知一棵二叉樹，如果先序遍歷的節(jié)點(diǎn)順序是：ADCEFGHB，中序遍歷是：CDFEGHAB，則后序遍歷結(jié)果為：（D）ACFHGEBDA   BCDFEGHBA   CFGHCDEBA   DCFHGEDBA2 下列哪兩個(gè)數(shù)據(jù)結(jié)構(gòu)，同時(shí)具有較高的查找和刪除性能？（CD）A有序數(shù)組     B有序

2、鏈表      CAVL樹        DHash表3 下列排序算法中，哪些時(shí)間復(fù)雜度不會(huì)超過nlogn？（BC）A快速排序     B堆排序        C歸并排序      D冒泡排序4 初始序列為1 8 6 2

3、 5 4 7 3一組數(shù)采用堆排序，當(dāng)建堆（小根堆）完畢時(shí)，堆所對應(yīng)的二叉樹中序遍歷序列為：（A）A8 3 2 5 1 6 4 7B3 2 8 5 1 4 6 7C3 8 2 5 1 6 7 4D8 2 3 5 1 4 7 65 當(dāng)n=5時(shí)，下列函數(shù)的返回值是：（A）in

4、t foo(int n)      if(n<2)return n;     return foo(n-1)+foo(n-2);  A5           B7            

5、0;  C8             D106  S市A，B共有兩個(gè)區(qū)，人口比例為3：5，據(jù)歷史統(tǒng)計(jì)A的犯罪率為0.01%，B區(qū)為0.015%，現(xiàn)有一起新案件發(fā)生在S市，那么案件發(fā)生在A區(qū)的可能性有多大？（C）A37.5%       B32.5%         &#

6、160;C28.6%          D26.1%7  Unix系統(tǒng)中，哪些可以用于進(jìn)程間的通信？（BCD）ASocket       B共享內(nèi)存       C消息隊(duì)列       D信號(hào)量8 靜態(tài)變量通常存儲(chǔ)在進(jìn)程哪個(gè)區(qū)？（C）A棧區(qū) 

7、0;      B堆區(qū)           C全局區(qū)         D代碼區(qū)9 查詢性能（B）A 在Name字段上添加主鍵B 在Name字段上添加索引C 在Age字段上添加主鍵D 在Age字段上添加索引10  IP地址1是一個(gè)（B）類IP地址。

8、AA           BB             CC               DD11 下推自動(dòng)識(shí)別機(jī)的語言是：（C）A 0型語言    

9、B1型語言       C2型語言         D3型語言12 下列程序的輸出是：（D）#define add(a+b) a+b int main()      printf(“%dn”,5*add(3+4);     return 0;  A2

10、3           B35            C16              D1913 瀏覽器訪問某頁面，HTTP協(xié)議返回狀態(tài)碼為403時(shí)表示：（B）A 找不到該頁面B 禁止訪問C

11、0;內(nèi)部服務(wù)器訪問D 服務(wù)器繁忙14 如果某系統(tǒng)15*4=112成立，則系統(tǒng)采用的是（A）進(jìn)制。A6            B7             C8              &#

12、160;D915 某段文本中各個(gè)字母出現(xiàn)的頻率分別是a:4，b:3，o:12，h:7，i:10，使用哈夫曼編碼，則哪種是可能的編碼：（A）A  a(000)  b(001)  h(01)  i(10)  o(11)B  a(0000)  b(0001)  h(001)  o(01)  i(1)C  a(000)  b(001)  

13、;h(01)  i(10)  o(00)D  a(0000)  b(0001)  h(001)  o(000)  i(1)16  TCP和IP分別對應(yīng)了OSI中的哪幾層？（CD）A  Application layerB  Presentation layerC  Transport layerD  Network l

14、ayer17 一個(gè)棧的入棧序列是A,B,C,D,E，則棧的不可能的輸出序列是？（C）AEDCBA          BDECBA          CDCEAB       DABCDE18 同一進(jìn)程下的線程可以共享以下？（BD）A stack    

15、0;      Bdata section        Cregister set     Dfile fd19 對于派生類的構(gòu)造函數(shù)，在定義對象時(shí)構(gòu)造函數(shù)的執(zhí)行順序?yàn)椋浚―）1：成員對象的構(gòu)造函數(shù)2：基類的構(gòu)造函數(shù)3：派生類本身的構(gòu)造函數(shù)A123          

16、   B231               C321           D21320 如何減少換頁錯(cuò)誤？（BC）A  進(jìn)程傾向于占用CPUB  訪問局部性（locality of reference）滿足進(jìn)程要求C  

17、進(jìn)程傾向于占用I/OD  使用基于最短剩余時(shí)間（shortest remaining time）的調(diào)度機(jī)制21 遞歸函數(shù)最終會(huì)結(jié)束，那么這個(gè)函數(shù)一定？（B）A 使用了局部變量B 有一個(gè)分支不調(diào)用自身C 使用了全局變量或者使用了一個(gè)或多個(gè)參數(shù)D 沒有循環(huán)調(diào)用22 編譯過程中，語法分析器的任務(wù)是（B）A分析單詞是怎樣構(gòu)成的B 分析單詞串是如何構(gòu)成語言和說明的C 分析語句和說明是如何構(gòu)成程序的D 分析程序的結(jié)構(gòu)23 同步機(jī)制應(yīng)該遵循哪些基本準(zhǔn)則？（ABCD）A空

18、閑讓進(jìn)        B忙則等待        C有限等待        D讓權(quán)等待24 進(jìn)程進(jìn)入等待狀態(tài)有哪幾種方式？（D）A CPU調(diào)度給優(yōu)先級(jí)更高的線程B 阻塞的線程獲得資源或者信號(hào)C 在時(shí)間片輪轉(zhuǎn)的情況下，如果時(shí)間片到了D 獲得spinlock未果25 設(shè)計(jì)模式中，屬于結(jié)構(gòu)型模式的有哪些？（

19、BC）A  狀態(tài)模式        B  裝飾模式        C 代理模式       D 觀察者模式二、填空題（共4題10個(gè)空，每空2分，共20 分）1 設(shè)有字母序列Q,D,F,X,A,P,N,B,Y,M,C,W，請寫出按二路歸并方法對該序列進(jìn)行一趟掃描后的結(jié)果為DQFXAPBNMY

20、CW。2 關(guān)鍵碼序列(Q,H,C,Y,Q,A,M,S,R,D,F,X)，要按照關(guān)鍵碼值遞增的次序進(jìn)行排序，若采用初始步長為4的Shell的排序法，則一 趟掃描的結(jié)果是QACSQDFXRHMY；若采用以第一個(gè)元素為分界元素的快速排序法，則掃描一趟的結(jié)果是FHCDQAMQRSYX。3 二進(jìn)制地址為011011110000，大小為（4）10和（16）10塊的伙伴地址分別為：_，_。4 設(shè)t是給定的一棵二叉樹，下面的遞歸程序count(t)用于求得：二叉樹t中具有非空的左、右兩個(gè)兒子的結(jié)點(diǎn)個(gè)數(shù)N2；只有非空左兒子的個(gè)數(shù)NL； 只有非空右兒子的結(jié)點(diǎn)個(gè)數(shù)NR和葉子結(jié)點(diǎn)個(gè)數(shù)N0

21、。N2，NL,NR、N0都是全局量，且在調(diào)用count(t)之前都置為0。typedef struct node     int data;     struct node *lchild,*rchild; node; int N2,NL,NR,N0; void count(node *t)     if (t->lchild!= NULL)         if (t->rchild!= NULL) N2+;         else NL+

22、;     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題，每題20分），選作題，不計(jì)入總分）1 請?jiān)O(shè)計(jì)一個(gè)排隊(duì)系統(tǒng)，能夠讓每個(gè)進(jìn)入隊(duì)伍的用戶都能看到自己在隊(duì)列中所處

23、的位置和變化，隊(duì)伍可能隨時(shí)有人加入和退出；當(dāng)有人退出影響到用戶的位置排名時(shí)需要及時(shí)反饋到用戶。2 A，B兩個(gè)整數(shù)集合，設(shè)計(jì)一個(gè)算法求他們的交集，盡可能的高效。1.   關(guān)于二叉樹，下面說法正確的是（）A.  對于N個(gè)節(jié)點(diǎn)的二叉樹，其高度為nlog2n;B.   一個(gè)具有1025個(gè)節(jié)點(diǎn)的二叉樹，其高度范圍在111025之間C.  二叉樹的先序遍歷是EFHIGJK，中序遍歷為HFIEJKG，該二叉樹的右子樹的根為GD.  二叉樹中至少有一個(gè)節(jié)點(diǎn)的度為2 2.  

24、0;假設(shè)函數(shù)f1的時(shí)間復(fù)雜度O(n)，那么f1*f1的時(shí)間復(fù)雜度為（）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個(gè)字符，使用了1382個(gè)字節(jié)存儲(chǔ)，這段文本全部

25、是由a、b、c、d、e字符組成，a 354次，b483次，c 227次，d 96次，e 222次，對這5個(gè)字符使用哈夫曼編碼。則以下說法正確的是？（）A.  使用哈夫曼編碼后，使用編碼值來存儲(chǔ)這段文本將花費(fèi)最少的存儲(chǔ)空間、B.   使用哈夫曼編碼后，ab c d e 這5個(gè)字符對應(yīng)的編碼值是唯一確定的C.  使用哈夫曼編碼后，ab c d e 這5個(gè)字符對應(yīng)的編碼值可以有多套，但每個(gè)字符的編碼位數(shù)是確定的D.  b這個(gè)字符的編碼位數(shù)最短，d這個(gè)字符的哈夫曼編碼位數(shù)應(yīng)該最長 5.   判

26、斷單鏈表有沒有環(huán)的算法中，至少需要幾個(gè)指針（）A.  1 B.   2C.  3 D.  4 6.   在編譯過程中，產(chǎn)生Parse  tree的過程是（）A.  語法分析B.   語義分析階段C.  詞法分析D.  目標(biāo)代碼生成階段 7.   閱讀下面代碼，程序會(huì)打印出來的值是（） 1.  #include2.  Void f

27、(char *p)3.                 *p += 2;4.  5.  Void main() 6.                 Char *a = “123”,”abc”,”456”,*p;7.                

28、p = a;8.                 f(p);9.                 printf(“%srn”,*p);10.復(fù)制代碼A.  123  B.  abc  C.  456  D.  3  8.

29、   Char p1 = “Tencent”, void p2= malloc(10)在32位機(jī)器上sizeof(p1)和sizeof(p2)對應(yīng)的值是（）A.  8：0B.   4：10 C.  8：4D.  4：4 9.   現(xiàn)在有以下兩個(gè)函數(shù)，調(diào)用test的結(jié)果是（）1.  Char* getMem(void)      Char * p = “hello world ”;2.   

30、60;   P5 = 0x0;3.        Return p;4.  5.  Voidtest(void)      Char *s = 0x0;6.        s = getMem();7.        Printf(s);8.  復(fù)制代碼A.  hello B.   無輸出C.  H

31、ello0world D.  不確定 10.  馮諾依曼體系結(jié)構(gòu)計(jì)算機(jī)的基本原理是（）A信息存儲(chǔ)  B 存儲(chǔ)智能 C 數(shù)字控制 D 存儲(chǔ)程序和程序控制  11.   求貢獻(xiàn) 12.下面哪種設(shè)計(jì)模式的定義為：定義對象間的一種一對多的關(guān)系，當(dāng)一個(gè)對象改變時(shí)，其他依賴于他的對象都能夠得到通知并自動(dòng)更新。（）A.  Visitor B.  Adapter C.  Observer D. 

32、0;Interpreter 13.請看一下這一段C+代碼，如果編譯后程序在windows下運(yùn)行，則一下說話正確的是（）Char*p1 = “123456”;Char*p2 = (char*)malloc(10);A.  P1 he p2都存在棧中B.   P2指向的10個(gè)字節(jié)內(nèi)存在棧中C.  堆和棧在內(nèi)存中的生長方向是相反的D.  “123456”這6個(gè)字符存儲(chǔ)在棧中 14.將3個(gè)球隨機(jī)放入4個(gè)杯子中，則杯子中球的最大個(gè)數(shù)為2的概率是（）A.  9/16 B.

33、60;  3/4C.  3/8 D.  3/16 15.對n個(gè)元素的數(shù)組進(jìn)行快速排序，所需要的二外空間為（）A.  O(1)B.  O(n)C.  O(log(2n)D.  O(n2) 16.下面關(guān)于編譯器與解釋器的觀點(diǎn)，錯(cuò)誤的是（）A.  解釋器不產(chǎn)生目標(biāo)程序，它直接執(zhí)行源程序或者源程序的內(nèi)部形式B.   解釋程序和編譯程序的主要區(qū)別在于是否產(chǎn)生目標(biāo)程序C.  編譯器對高級(jí)語言程序的處

34、理過程劃分成詞法分析、語法分析、語義分析，中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成幾個(gè)階段D.  解釋器參與運(yùn)行控制、程序執(zhí)行的速度快17.假設(shè)系統(tǒng)中有5太設(shè)備，有多個(gè)進(jìn)程需要使用2個(gè)設(shè)備，假定每個(gè)進(jìn)程一次只能使用一臺(tái)，則至多允許多少個(gè)進(jìn)程來競爭這5個(gè)資源，而不會(huì)發(fā)生死鎖（）A.  2 B.  3 C.  4 D.  5 18.下面哪些協(xié)議，存在源端口和目的端口是（）A.  IP B.  TCP C. 

35、; UDP D.  ICMP協(xié)議 19.下列哪些sql是等價(jià)的（）A.  Select A.tname ,A.depart fromteacher A joincourse B on B.tno = .A.tnoB.   Select A.tname ,A.depart fromteacher A whereA.tno = course.tnoC.  Select A.tname ,A.depart fromteacher wheretno in (select tno from co

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

37、;C、640        D、23621.將一個(gè)C類網(wǎng)絡(luò)劃分為3個(gè)子網(wǎng)，每個(gè)子網(wǎng)最少要容納55臺(tái)主機(jī)，使用的子網(wǎng)掩碼是：（）  A、48   B、24  C、24  D、255.255.255. 19222下列關(guān)于計(jì)算機(jī)硬件的描述，正確的是：（）A、磁盤的平均存取時(shí)間指的是磁盤的尋道時(shí)間加上磁頭在某一磁道等待記錄扇區(qū)的時(shí)間B、計(jì)算機(jī)的控制器是由多種部件組成，其中包括，指令寄存器

38、、程序計(jì)數(shù)器和算數(shù)邏輯單元C、一臺(tái)計(jì)算機(jī)的字長是32位，表明該機(jī)器能處理的數(shù)值最多為4個(gè)字節(jié)D、系統(tǒng)總線可以分為數(shù)據(jù)總線、地址總線和控制總線三類23、假設(shè)有關(guān)系模式R(A,B,C,D),其數(shù)據(jù)依賴集：F=(A,B)->C,C->D,則關(guān)系模式R的規(guī)范化程度最高達(dá)到：（）A.1NFB.2NFC.3NFD.BCNF24.以下為一段瀏覽器中可運(yùn)行的Javascript 代碼，則運(yùn)行該段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分硬幣，如果想湊齊一元錢，