騰訊筆試題2014

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

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

3、 5 4 7 3一組數(shù)采用堆排序，當建堆（小根堆）完畢時，堆所對應的二叉樹中序遍歷序列為：（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 當n=5時，下列函數(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共有兩個區(qū)，人口比例為3：5，據(jù)歷史統(tǒng)計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)中，哪些可以用于進程間的通信？（BCD）ASocket       B共享內存       C消息隊列       D信號量8 靜態(tài)變量通常存儲在進程哪個區(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是一個（B）類IP地址。

8、AA           BB             CC               DD11 下推自動識別機的語言是：（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時表示：（B）A 找不到該頁面B 禁止訪問C

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

12、160;D915 某段文本中各個字母出現(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分別對應了OSI中的哪幾層？（CD）A  Application layerB  Presentation layerC  Transport layerD  Network l

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

15、0;      Bdata section        Cregister set     Dfile fd19 對于派生類的構造函數(shù)，在定義對象時構造函數(shù)的執(zhí)行順序為？（D）1：成員對象的構造函數(shù)2：基類的構造函數(shù)3：派生類本身的構造函數(shù)A123          

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

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

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

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

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

21、。N2，NL,NR、N0都是全局量，且在調用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分），選作題，不計入總分）1 請設計一個排隊系統(tǒng)，能夠讓每個進入隊伍的用戶都能看到自己在隊列中所處

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

24、0;假設函數(shù)f1的時間復雜度O(n)，那么f1*f1的時間復雜度為（）A.  O(n)B.  O(n*n)C.  O(n*log(n)D.  以上都不對 3.   對下列四種排序方法，在排序中關鍵字比較次數(shù)與記錄初始化順序無關的是（）A.  直接排序B.  二分法插入C.  快速排序D.  歸并排序 4.   已知一段文本有1382個字符，使用了1382個字節(jié)存儲，這段文本全部

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

26、斷單鏈表有沒有環(huán)的算法中，至少需要幾個指針（）A.  1 B.   2C.  3 D.  4 6.   在編譯過程中，產生Parse  tree的過程是（）A.  語法分析B.   語義分析階段C.  詞法分析D.  目標代碼生成階段 7.   閱讀下面代碼，程序會打印出來的值是（） 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.復制代碼A.  123  B.  abc  C.  456  D.  3  8.

29、   Char p1 = “Tencent”, void p2= malloc(10)在32位機器上sizeof(p1)和sizeof(p2)對應的值是（）A.  8：0B.   4：10 C.  8：4D.  4：4 9.   現(xiàn)在有以下兩個函數(shù)，調用test的結果是（）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.  復制代碼A.  hello B.   無輸出C.  H

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

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

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

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

35、; UDP D.  ICMP協(xié)議 19.下列哪些sql是等價的（）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.某一磁盤請求序列(磁道號):98、 183、37、122、14、124、 65、 61，按照先來先服務FCFS磁盤調度對磁盤進行請求服務，假設當前磁頭在53道上，則磁臂總移動道數(shù)為：（）A、169        B、208       

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

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