天天看點
傳回

騰訊2014校園招聘軟體開發類筆試緣由不定項選擇題填空題其他方向簡答題

緣由

主要參考了部落格：

  1. 筆試面試（1）騰訊2014校園招聘軟體開發類筆試試題
  2. 我的解法是我自己做的，不表示正确答案。
  3. 考試時長：120分鐘

不定項選擇題

（共25題，每題4分，共100分，少選、錯選、多選均不得分）

第一題

1 已知一棵二叉樹，如果先序周遊的節點順序是：ADCEFGHB，中序周遊是：CDFEGHAB，則後序周遊結果為：（）

A．CFHGEBDA   B．CDFEGHBA   C．FGHCDEBA   D．CFHGEDBA

參考解答：

解析：由先序周遊序列和中序周遊序列可以唯一确定樹的結構

步驟： 由先序序列确定根節點；按根節點把中序序列分為兩端，前面的是左子樹，後面的是右子樹；對左右子樹重複前面的步驟 

騰訊2014校園招聘軟體開發類筆試緣由不定項選擇題填空題其他方向簡答題

後續周遊序列：CFHGEDBA   

答案選 D

我的解答：

先序周遊：根、左、右

中序：左、根、右

後序：左、右、根

顯然可以畫出具體的全部的排序，但是這樣解題速度慢，是以我決定采用一些技巧。首先可以知道先序的A在最前面，是以根肯定是A，而中序以AB結尾。是以後序的肯定以BA相連，并且在最後面，是以排除A。

對于左子樹，先序：DCEFGH。中序：CDFEGH。D肯定是左子樹的根，C是左子樹的左孩子。是以我想肯定C肯定是後序的開頭。是以選D。

第二題

2 下列哪兩個資料結構，同時具有較高的查找和删除性能？（）

A．有序數組     B．有序連結清單      C．AVL樹        D．Hash表

參考解答

騰訊2014校園招聘軟體開發類筆試緣由不定項選擇題填空題其他方向簡答題

由上圖可見，平衡二叉樹的查找，插入和删除性能都是O(logN)，其中查找和删除性能較好；哈希表的查找、插入和删除性能都是O(1)，都是最好的。

答案：CD    

我的解答

排除法。可以知道選CD。因為數組在删除的時候需要移動的數組元素。而有序連結清單在查找的時候需要周遊。AVL是自平衡二叉查找樹，而紅黑樹就一種自平衡二叉查找樹。Hash表就不說了。

第三題

3 下列排序算法中，哪些時間複雜度不會超過nlogn？（）

A．快速排序     B．堆排序        C．歸并排序      D．冒泡排序

參考解答

幾種常見的排序算法對比：

騰訊2014校園招聘軟體開發類筆試緣由不定項選擇題填空題其他方向簡答題

穩定的排序：冒泡，插入，基數，歸并

答案：BC

我的解答

BC，因為快速排序在最壞的情況的時間複雜度是n^2,而冒泡排序的時間複雜度無論在什麼情況下都是n^2。

第四題

4 初始序列為1 8 6 2 5 4 7 3一組數采用堆排序，當建堆（小根堆）完畢時，堆所對應的二叉樹中序周遊序列為：（）

A．8 3 2 5 1 6 4 7

B．3 2 8 5 1 4 6 7

C．3 8 2 5 1 6 7 4

D．8 2 3 5 1 4 7 6

參考解答

沒有找到别人的答案，自己看了書之後做出來了，選A

書中建大堆的過程

騰訊2014校園招聘軟體開發類筆試緣由不定項選擇題填空題其他方向簡答題

我的解答

過程

騰訊2014校園招聘軟體開發類筆試緣由不定項選擇題填空題其他方向簡答題

我的解答

建堆過程？我突然感覺不會了。那麼我用排除法選B，因為A、D以8開頭，這顯然是不可能的，怎麼最左的元素是8呢？而且C的3、8排序肯定也是不對的。但是B選項3、2、8也讓我覺得不太對。

第五題

5 當n=5時，下列函數的傳回值是：（）

int foo(int n)  

{  

    if(n<2)return n;  

    return foo(n-1)+foo(n-2);  

}  

A．5           B．7               C．8             D．10

參考解答

直接給了答案A。

我的解答

從1開始就好了。

Foo(0)=0

Foo(1)=1

Foo(2)=1

Foo(3)=2

Foo(4)=3

Foo(5)=5

固選A。

第六題

6  S市A，B共有兩個區，人口比例為3：5，據曆史統計A的犯罪率為0.01%，B區為0.015%，現有一起新案件發生在S市，那麼案件發生在A區的可能性有多大？（）

A．37.5%       B．32.5%          C．28.6%          D．26.1%

參考解答

犯罪率可以了解為AB兩區的犯罪人數與總人口數的比。由此不難列出下式：

( 3*0.01% ) / ( 3*0.01% + 5*0.015% ) = 0.2587 = 28.6%

答案：C

我的解答

S市共有8千人，3000人在A區，5000人在B區，A區有罪犯3人，B區有7.5人。如果一起犯罪，那麼在是這3個人中的一個的機率是：3/3+7.5 = 0.286.是以選C。

第七題

7  Unix系統中，哪些可以用于程序間的通信？（）

A．Socket       B．共享記憶體       C．消息隊列       D．信号量

參考解答

（1）管道（Pipe）：管道可用于具有親緣關系程序間的通信，允許一個程序和另一個與它有共同祖先的程序之間進行通信。

（2）命名管道（named pipe）：命名管道克服了管道沒有名字的限制，是以，除具有管道所具有的功能外，它還允許無親緣關系程序間的通信。命名管道在檔案系統中有對應的檔案名。命名管道通過指令mkfifo或系統調用mkfifo來建立。

（3）信号（Signal）：信号是比較複雜的通信方式，用于通知接受程序有某種事件發生，除了用于程序間通信外，程序還可以發送信号給程序本身；linux除了支援Unix早期信号語義函數sigal外，還支援語義符合Posix.1标準的信号函數sigaction（實際上，該函數是基于BSD的，BSD為了實作可靠信号機制，又能夠統一對外接口，用sigaction函數重新實作了signal函數）。

（4）消息（Message）隊列：消息隊列是消息的連結表，包括Posix消息隊列system V消息隊列。有足夠權限的程序可以向隊列中添加消息，被賦予讀權限的程序則可以讀走隊列中的消息。消息隊列克服了信号承載資訊量少，管道隻能承載無格式位元組流以及緩沖區大小受限等缺

（5）共享記憶體：使得多個程序可以通路同一塊記憶體空間，是最快的可用IPC形式。是針對其他通信機制運作效率較低而設計的。往往與其它通信機制，如信号量結合使用，來達到程序間的同步及互斥。

（6）記憶體映射（mapped memory）：記憶體映射允許任何多個程序間通信，每一個使用該機制的程序通過把一個共享的檔案映射到自己的程序位址空間來實作它。

（7）信号量（semaphore）：主要作為程序間以及同一程序不同線程之間的同步手段。

（8）套接口（Socket）：更為一般的程序間通信機制，可用于不同機器之間的程序間通信。起初是由Unix系統的BSD分支開發出來的，但現在一般可以移植到其它類Unix系統上：Linux和System V的變種都支援套接字。

答案：ABCD

我的解答

ABD肯定可以，C我有點不确定。Unix裡面有消息隊列麼？有點忘了。

第八題

8 靜态變量通常存儲在程序哪個區？（）

A．棧區        B．堆區           C．全局區         D．代碼區

參考解答

騰訊2014校園招聘軟體開發類筆試緣由不定項選擇題填空題其他方向簡答題

其中動态配置設定的資料是指：經常直到程式實際運作的時候，才知道某個資料結構的大小。在linux中，主要是用malloc和free函數來完成動态配置設定。用malloc配置設定的記憶體就是從堆中取得。（摘自 深入了解計算機系統）

答案：C

我的解答

顯然B區。另外有全局區這樣的說法？

第九題

9 查詢性能（）

A． 在Name字段上添加主鍵

B． 在Name字段上添加索引

C． 在Age字段上添加主鍵

D． 在Age字段上添加索引

這題應該是問：為了提高查詢性能，可以（）。

别人的解答

索引：對資料庫表中一列或多列的值進行排序（或構成特定的資料結構，如樹或哈希表）的一種結構，使用索引可快速通路資料庫表中的特定資訊。

優點：

  1. 通過建立唯一性索引，可以保證資料庫表中每一行資料的唯一性
  2. 可以大大加快資料的檢索速度
  3. 可以加快表與表之間的連接配接
  4. 使用分組和排序子句進行檢索時，同樣可以顯著減少查詢中分組和排序的事件
  5. 在查詢的過程中優化隐藏器，提高系統的性能

缺點：

  1. 建立和維護是以你需要耗費時間
  2. 索引需要占實體空間，如果建立聚簇索引，需要的空間更大
  3. 表的資料更新時，索引也要動态的維護

建立索引的規則：

  1. 表的主鍵、外鍵必須有索引；
  2. 資料量超過300的表應該有索引；
  3. 經常與其他表進行連接配接的表，在連接配接字段上應該建立索引；
  4. 經常出現在Where子句中的字段，特别是大表的字段，應該建立索引；
  5. 索引應該建在選擇性高的字段上；
  6. 索引應該建在小字段上，對于大的文本字段甚至超長字段，不要建索引；
  7. 複合索引的建立需要進行仔細分析；盡量考慮用單字段索引代替：
  8.    正确選擇複合索引中的主列字段，一般是選擇性較好的字段；
  9.    複合索引的幾個字段是否經常同時以AND方式出現在Where子句中？單字段查詢是否極少甚至沒有？如果是，則可以建立複合索引；否則考慮單字段索引；
  10.    如果複合索引中包含的字段經常單獨出現在Where子句中，則分解為多個單字段索引；
  11.    如果複合索引所包含的字段超過3個，那麼仔細考慮其必要性，考慮減少複合的字段；
  12.    如果既有單字段索引，又有這幾個字段上的複合索引，一般可以删除複合索引；
  13. 頻繁進行資料操作的表，不要建立太多的索引；
  14. 删除無用的索引，避免對執行計劃造成負面影響；

我的總結

索引是對資料庫表中一個或多個列（例如，employee 表的姓氏 (lname) 列）的值進行排序的結構。如果想按特定職員的姓來查找他或她，則與在表中搜尋所有的行相比，索引有助于更快地擷取資訊。

例如這樣一個查詢：select * from table1 where id=10000。如果沒有索引，必須周遊整個表，直到ID等于10000的這一行被找到為止；有了索引之後(必須是在ID這一列上建立的索引)，即可在索引中查找。由于索引是經過某種算法優化過的，因而查找次數要少的多的多。可見，索引是用來定位的。

如下圖（SQL Server的B樹結構）所示：

騰訊2014校園招聘軟體開發類筆試緣由不定項選擇題填空題其他方向簡答題

在這時比如要查詢ID=100的時候，就不用從1開始周遊了，而是由索引定位到76-100的葉節點，然後開始周遊。

反正不可能是添加主鍵吧，主鍵對性能的提升沒有用。

我的解答

選B吧。我也不太知道是什麼意思。感覺題目不太完整。

第十題

10  IP位址131.153.12.71是一個（）類IP位址。

A．A           B．B             C．C               D．D

參考解答

IP位址分類

  1.     A類網絡的IP位址範圍為1.0.0.1－127.255.255.254；
  2.     B類網絡的IP位址範圍為：128.1.0.1－191.255.255.254；
  3.     C類網絡的IP位址範圍為：192.0.1.1－223.255.255.254。
騰訊2014校園招聘軟體開發類筆試緣由不定項選擇題填空題其他方向簡答題

我的解答

好像A類是1-125。是以131我覺得是B類位址。

第十一題

11 下推自動識别機的語言是：（）

A． 0型語言    B．1型語言       C．2型語言         D．3型語言

參考解答

在自動機理論中，下推自動機（Pushdown automaton）是使用了包含資料的棧的有限自動機。使用的語言為2型語言。

我的解答

不知道

第十二題

12 下列程式的輸出是：（）

#define add(a+b) a+b  

int main()  

{  

    printf(“%d\n”,5*add(3+4));  

    return 0;  

}  

A．23           B．35            C．16              D．19

參考解答

宏是完全的文本替換，宏替換時容易犯的錯誤。使用宏時，帶上括号是安全的做法。

答案：D

我的解答

應該是19，因為5*3+4，這很顯然是因為宏define是替換，而不是真正的計算。

第十三題

13 浏覽器通路某頁面，HTTP協定傳回狀态碼為403時表示：（）

A 找不到該頁面

B 禁止通路

C 内部伺服器通路

D 伺服器繁忙

參考解答

  • 找不到該頁面：404
  • 禁止通路：403
  • 内部伺服器通路：500
  • 伺服器繁忙：503
騰訊2014校園招聘軟體開發類筆試緣由不定項選擇題填空題其他方向簡答題

我的解答

我還做了網頁了一段時間的網頁開發，看樣子隻能說是A了。

第十四題

14 如果某系統15*4=112成立，則系統采用的是（）進制。

A．6            B．7             C．8               D．9

參考解答

驗證A

需要注意的是，當選定六進制時，15，4 和112都應該為六進制。

15由六進制轉為十進制為11，計算方法：1*6 + 5*1 = 11

同理：4轉為十進制為4，112轉為十進制為44

是以轉換後的等式左邊為 11*4， 右邊為44。相等。

是以，答案為A。如果如何從别的進制轉到十進制，比如二進制：

用二進制： 11101.010轉為十進制表示 來舉例：

整數部分 11101=2^4+2^3+2^2+0*2^1+1=33

分數部分 0.010=0.01=0/2^1+1/2^2=0+0.25=0.25

結果是 33+0.25=33.25

那麼六進制的112的十進制應該是：1*6^2+1*6^1+2*6^0 = 44

我的解答

15+15+15+15

如果是6進制：34+15+15 –>53+15=112

一算第一個就正确了。運氣不錯。注意大于6的對應數字關系。當然要進位。

6->0 7->1 8->2 9->3 10->4 11->5 12->0

第十五題

15 某段文本中各個字母出現的頻率分别是{a:4，b:3，o:12，h:7，i:10}，使用哈夫曼編碼，則哪種是可能的編碼：（）

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)  h(01)  i(10)  o(00)

D  a(0000)  b(0001)  h(001)  o(000)  i(1)

參考解答

沒有什麼意義

我的總結

這道題肯定是用排除法無疑。因為題中已經說的很清楚可能的編碼是什麼。是以答案肯定是不唯一。我是以必須找出不對的另外三個。

B：我認為是違反了哈弗曼編碼希望編碼越來越短的原則，因為頻率最高的是o，但是o居然需要兩個數來表示，比起頻率低的i卻需要一個數字，這是必定錯誤的地方。

C：因為o(00)和a(000)容易造成混淆。00001 是表示 000 01 還是 00 001 呢？前一個表示 ai，後一個表示ob。

D：和C一樣。

下面是哈弗曼編碼的過程：

騰訊2014校園招聘軟體開發類筆試緣由不定項選擇題填空題其他方向簡答題
騰訊2014校園招聘軟體開發類筆試緣由不定項選擇題填空題其他方向簡答題

還有我畫的選項A的哈夫曼樹：

騰訊2014校園招聘軟體開發類筆試緣由不定項選擇題填空題其他方向簡答題

我的解答

考研的時候複習過，依稀記得。好像該題可以用排除法。A就行。很顯然C不行，因為o(00)和a(000)容易造成混淆。B好像是因為太長了。D和C的原因一樣。

第十六題

16  TCP和IP分别對應了OSI中的哪幾層？（）

A  Application layer

B  Presentation layer

C  Transport layer

D  Network layer

參考解答

騰訊2014校園招聘軟體開發類筆試緣由不定項選擇題填空題其他方向簡答題

我的解答

直覺傳輸層。選C

第十七題

17 一個棧的入棧序列是A,B,C,D,E，則棧的不可能的輸出序列是？（）

A．EDCBA          B．DECBA          C．DCEAB       D．ABCDE

我的解答

選C。因為此時A不可能比B先出，而D選項中，A在B前面的原因是因為A進棧就出來了。

第十八題

18 同一程序下的線程可以共享以下？（）

A． stack           B．data section        C．register set     D．file fd

參考解答

線程共享的内容包括：

  1. 程序代碼段
  2. 程序的公有資料(利用這些共享的資料，線程很容易的實作互相之間的通訊)、
  3. 程序打開的檔案描述符、
  4. 信号的處理器、
  5. 程序的目前目錄和
  6. 程序使用者ID與程序組ID   

線程獨有的内容包括：

  1. 線程ID
  2. 寄存器組的值（register set）
  3. 線程的堆棧
  4. 錯誤傳回碼
  5. 線程的信号屏蔽碼

答案：BD

我的解答

選個BD。A太誇張了。C不知道是什麼東西。

第十九題

19 對于派生類的構造函數，在定義對象時構造函數的執行順序為？（）

1：成員對象的構造函數

2：基類的構造函數

3：派生類本身的構造函數

A．123             B．231               C．321           D．213

參考解答

當派生類中不含對象成員時

  1. 在建立派生類對象時,構造函數的執行順序是：基類的構造函數→派生類的構造函數；
  2. 在撤消派生類對象時,析構函數的執行順序是：派生類的構造函數→基類的構造函數。

當派生類中含有對象成員時

  1. 在定義派生類對象時，構造函數的執行順序：基類的構造函數→對象成員的構造函數→派生類的構造函數；
  2. 在撤消派生類對象時，析構函數的執行順序：派生類的構造函數→對象成員的構造函數→基類的構造函數。

答案：D

我的解答

直覺B

第二十題

20 如何減少換頁錯誤？（）

A  程序傾向于占用CPU

B  通路局部性（locality of reference）滿足程序要求

C  程序傾向于占用I/O

D  使用基于最短剩餘時間（shortest remaining time）的排程機制

參考解答

參考一下：如何減少換頁錯誤？

答案：BD

我的總結

其實選D我還是有點印象的：

就是這個B:實際上就說是通路局部性，也就是程式的局部性原理，即程式的位址通路流有很強的時序相關性，未來的通路模式與最近已發生的通路模式相似。根據這一局部性原理，把主存儲器中通路機率最高的内容存放在Cache中，當CPU需要讀取資料時就首先在Cache中查找是否有所需内容，如果有則直接從Cache中讀取；若沒有再從主存中讀取該資料，然後同時送往CPU和Cache。

關鍵就是說如果程序滿足了局部性的要求，那麼在一定的時間和空間内都是由這個程序來占用記憶體和cpu，那麼肯定減少了換頁錯誤（在一定時間内沒有别的程序來幹擾）。

我的解答

有點暈，選D

第二十一題

21 遞歸函數最終會結束，那麼這個函數一定？（）

A 使用了局部變量

B 有一個分支不調用自身

C 使用了全局變量或者使用了一個或多個參數

D 沒有循環調用

參考答案

直接排除AD，注意力集中在B和C。

B肯定是對的，隻有一次循環滿足某個條件，不調用自己就傳回，遞歸才會一層一層向上傳回。

那麼C呢，想一下，全局變量和參數确實可以用來控制遞歸的結束與否。

該不該選C呢？再仔細看一下題目（說實話，我很讨厭這種文字遊戲），“這個函數一定...“，是以，問題集中在，是否是一定會使用這兩種方式呢？

顯然不是的。除了C中提到的兩種情況外，還有如下控制遞歸的方式：

局部靜态變量是可以控制遞歸函數最終結束的

可能通過異常來控制遞歸的結束。

可以利用BIOS或OS的一些資料或一些标準庫的全局值來控制遞歸過程的終止。

可以把一些資料寫入到BIOS或OS的系統資料區，也可以把資料寫入到一個檔案中，以此來控制遞歸函數的終止。

是以，答案為B

我的解答

B不是一定，而C是一定的。不然真的沒法結束了。

第二十二題

22 編譯過程中，文法分析器的任務是（）

A分析單詞是怎樣構成的

B 分析單詞串是如何構成語言和說明的

C 分析語句和說明是如何構成程式的

D 分析程式的結構

參考答案

文法分析器（Parser）通常是作為編譯器或解釋器的元件出現的，它的作用是進行文法檢查、并建構由輸入的單詞組成的資料結構（一般是文法分析樹、抽象文法樹等階層化的資料結構）。

我的總結

其實我做的時候應該深入的猜一下的。

因為：

A:顯然不可能，因為從二十六個字母的角度分析如何形成單詞？

C：太大的了，和文法無關

D：更大了，和文法無關。

我的解答

不用猜了，完全不知道了。

第二十三題

23 同步機制應該遵循哪些基本準則？（）

A．空閑讓進        B．忙則等待        C．有限等待        D．讓權等待

參考答案

同步機制應該遵循的基本準則

  • 空閑讓進：當無程序處于臨界區時，表明臨界資源處于空閑狀态，允許一個請求進入臨界區的程序立即進入臨界區，以有效利用臨界資源
  • 忙則等待：當已有程序處于臨界區時，表明臨界資源正在被通路，因而其他試圖進入臨界區的程序必須等待，以保證對臨界資源的互斥通路
  • 有限等待：對要求通路臨界資源的程序，應保證在有限時間内能進入自己的臨界區，以免陷入“死等”狀态
  • 讓權等待：當程序不能進入自己的臨界區時，應立即釋放處理機，以免程序陷入“忙等”狀态

我的解答

ABCD全選依稀記得。

第二十四題

24 程序進入等待狀态有哪幾種方式？（）

A CPU排程給優先級更高的線程

B 阻塞的線程獲得資源或者信号

C 在時間片輪轉的情況下，如果時間片到了

D 獲得spinlock未果

參考解答

等待狀态應該是我們說的阻塞态，因為一般阻塞态是在等待某一觸發時間的發生，才能進入就緒狀态。

spinlock就是一種鎖。

是以答案：D

我的總結

由于該題所謂的“等待狀态”應該還是有歧義的，因為我們隻知道 運作、就緒、阻塞狀态，而且這個三個狀态很好的和英文單詞相對應：running、ready、blocked

我的解答

選擇AC。B應該是不會的，隻會讓阻塞的線程進準備狀态。

第二十五題

25 設計模式中，屬于結構型模式的有哪些？（）

A  狀态模式        B  裝飾模式        C 代理模式       D 觀察者模式

參考答案

建立型模式

前面講過，社會化的分工越來越細，自然在軟體設計方面也是如此，是以對象的建立和對象的使用分開也就成為了必然趨勢。因為對象的建立會消耗掉系統的很多資源，是以單獨對對象的建立進行研究，進而能夠高效地建立對象就是建立型模式要探讨的問題。這裡有6個具體的建立型模式可供研究，它們分别是：

  1. 簡單工廠模式（Simple Factory）；
  2. 工廠方法模式（Factory Method）；
  3. 抽象工廠模式（Abstract Factory）；
  4. 建立者模式（Builder）；
  5. 原型模式（Prototype）；
  6. 單例模式（Singleton）。

說明：嚴格來說，簡單工廠模式不是GoF總結出來的23種設計模式之一。

結構型模式

在解決了對象的建立問題之後，對象的組成以及對象之間的依賴關系就成了開發人員關注的焦點，因為如何設計對象的結構、繼承和依賴關系會影響到後續程式的維護性、代碼的健壯性、耦合性等。對象結構的設計很容易展現出設計人員水準的高低，這裡有7個具體的結構型模式可供研究，它們分别是：

  1. 外觀模式（Facade）；
  2. 擴充卡模式（Adapter）；
  3. 代理模式（Proxy）；
  4. 裝飾模式（Decorator）；
  5. 橋模式（Bridge）；
  6. 組合模式（Composite）；
  7. 享元模式（Flyweight）。

行為型模式

在對象的結構和對象的建立問題都解決了之後，就剩下對象的行為問題了，如果對象的行為設計的好，那麼對象的行為就會更清晰，它們之間的協作效率就會提高，這裡有11個具體的行為型模式可供研究，它們分别是：

  1. 模闆方法模式（Template Method）；
  2. 觀察者模式（Observer）；
  3. 狀态模式（State）；
  4. 政策模式（Strategy）；
  5. 職責鍊模式（Chain of Responsibility）；
  6. 指令模式（Command）；
  7. 通路者模式（Visitor）；
  8. 調停者模式（Mediator）；
  9. 備忘錄模式（Memento）；
  10. 疊代器模式（Iterator）；
  11. 解釋器模式（Interpreter）。

故答案：BC

我的解答

不知道！居然學了那麼久的設計模式。哎。。沒想到這一點會單獨出題。

填空題

（共4題10個空，每空2分，共20 分）

第一題

1 設有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W}，請寫出按二路歸并方法對該序列進行一趟掃描後的結果為       。

我的總結

我暈，我居然把希爾和二路歸并記混了。歸并就是相連的兩個先排序，而希爾是跳着來的。

是以我很快的寫出了答案：DQFXAPBNMYCW

我的解答

記不得歸并算法了。

第二題

2 關鍵碼序列(Q,H,C,Y,Q,A,M,S,R,D,F,X)，要按照關鍵碼值遞增的次序進行排序，若采用初始步長為4的Shell的排序法，則一趟掃描的結果是                   ；若采用以第一個元素為分界元素的快速排序法，則掃描一趟的結果是               。

我的總結

重寫希爾：

1 2 3 4 5 6 7 8 9 10 11 12  

Q,H,C,Y,Q,A,M,S,R, D, F, X

過程如下：

  1. 1-5-9:不變
  2. 2-6-10: Q,A,C,Y,Q,D,M,S,R, H, F, X
  3. 3-7-11: Q,A,C,Y,Q,D,F,S,R, H, M, X
  4. 4-8-12: Q,A,C,S,Q,D,F,X,R, H, M, Y
  5. 最終結果：Q,A,C,S,Q,D,F,X,R, H, M, Y

按照資料結構高分筆記208頁的模式從寫快速排序：

騰訊2014校園招聘軟體開發類筆試緣由不定項選擇題填空題其他方向簡答題
騰訊2014校園招聘軟體開發類筆試緣由不定項選擇題填空題其他方向簡答題
  1. 起始：Q,H,C,Y,Q,A,M,S,R, D, F, X
  2. 将第一個Q存入臨時表示：F,H,C,Y,Q,A,M,S,R, D,  , X
  3. F,H,C, ,Q,A,M,S,R, D, Y , X
  4. F,H,C,D ,Q,A,M,S,R, , Y , X
  5. F,H,C,D ,Q,A,M, ,R,S , Y , X
  6. 将放在臨時變量内的Q放在最終位置：F,H,C,D ,Q,A,M, Q,R,S , Y , X

我的解法不能說錯了，隻是和某種做法不一樣而已，好像下面的做法是C語言程式設計裡面的寫法。

我的解答

Shell：

Q,H,C,Y,Q,A,M,S,R,D,F,X

第一趟掃描結果：C,H,Q,Y,A,M,Q,R,D,F,R,X

快速排序：

Q,H,C,Y,Q,A,M,S,R,D,F,X

Q,H,C, F,Q,A,M,D,R,S,Y ,X

Q,H,C, F,Q,A,M,D,R,S,Y ,X

D,H,C, F,Q,A,M, Q ,R,S,Y ,X

是以第一輪排序結果：D,H,C, F,Q,A,M, Q ,R,S,Y ,X

第三題

3.二進制位址為011011110000，大小為（4）10和（16）10塊的夥伴位址分别為：_________，_________。

參考解答

位址011011110000，可以被2^(2+1）整除，是以夥伴位址是其下半部，加4就行，是以答案是011011110100;

16大小時，不能被2^(4+1)整除，是以夥伴位址是其上半部，位址減去16，結果為0110 1110 0000。至于為什麼這樣整除決定，請檢視夥伴位址定義。

我的解答

不懂夥伴位址

第四題

4.設t是給定的一棵二叉樹，下面的遞歸程式count(t)用于求得:二叉樹t中具有非空的左,右兩個兒子的結點個數N2;隻有非空左兒子的個數NL;隻有非空右兒子的結點個數NR和葉子結點個數N0。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 (1)___ N2++; 
else NL++; 
else  if (2)___ NR++; else  (3)__  
if(t->lchild!=NULL)(4)____; if (t->rchild!=NULL) (5)____; }

參考解答 

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++;  
    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);*/

我的解答

(1)： (t->rchild!=NULL) 
(2)：(t->rchild!=NULL)
(3)：N0++
(4)： count(t->lchild) 
(5)： count(t-> rchild)

其他方向簡答題

（共2題，每題20分），選作題，不計入總分）

第一題

1 請設計一個排隊系統，能夠讓每個進入隊伍的使用者都能看到自己在隊列中所處的位置和變化，隊伍可能随時有人加入和退出；當有人退出影響到使用者的位置排名時需要及時回報到使用者。

參考我的另一篇部落格：http://blog.csdn.net/zy825316/article/details/33727855

第二題

2、A，B兩個整數集合，設計一個算法求他們的交集，盡可能的高效。

參考我的另一篇部落格： 求兩個整數集合的交集（Java代碼，索引法）

算法 騰訊 面試 筆試 校招 實習
上一篇: 常用限流政策之漏桶和令牌桶
下一篇: 基于信号量和令牌桶算法的限流

繼續閱讀