2016騰訊軟件開發面試題(不定項選擇題【1-12】)

一、前言

2017年1月27日19:05:28，今天是年三十，首先祝大家新年快樂，之前對自己要求過，每星期一篇面試題的博客，雖然今天心裡有一萬個不願意寫，也還是得寫。這篇博客是 2016 騰訊軟件開發面試題中不定項選擇題集合中的 1 -12 題，其中後面的 13-25題在下周的博客中寫，說明一下，這篇博客跟以往的每周一題有點不同，因為如果選擇一兩題，博客的邊幅有點少，而且選擇題相對來說，難度沒那麼大，更主要的是為了讓大家全面的感受一下騰訊的面試題。

二、2016 騰訊軟件開發面試題（不定項選擇題【1-12】）

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

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

知識點

對於二叉樹的遍歷方式一般分為三種先序、中序、後序三種方式：

• 先序遍歷（根左右）
  若二叉樹為空，則不進行任何操作：否則
  1、訪問根結點。
  2、先序方式遍歷左子樹。
  3、先序遍歷右子樹。

• 中序遍歷 （左根右）
  若二叉樹為空，則不進行任何操作：否則
  1、中序遍歷左子樹。
  2、訪問根結點。
  3、中序遍歷右子樹。

• 後序遍歷 （左右根）
  若二叉樹為空，則不進行任何操作：否則
  1、後序遍歷左子樹。
  2、後序遍歷右子樹。
  3、放問根結點。

因此，根據題目給出的先序遍歷和中序遍歷，可以畫出二叉樹：

最後結果選擇： D

2、下列哪兩個數據結構，同時具有較高的查找和刪除性能？（ ）

A. 有序數組
B. 有序鏈表
C. AVL 樹
D. Hash 表

知識點

平衡二叉樹的查找，插入和刪除性能都是 O(logN) ，其中查找和刪除性能較好；哈希表的查找、插入和刪除性能都是 O(1) ，都是最好的。所以最後的結果選擇： CD

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

A. 快速排序
B. 堆排序
C. 歸並排序
D. 冒泡排序

知識點

根據上圖，觀察平均情況，最好最差情況的時間復雜度基本可以知道答案了，最後結果選擇： BC

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

初始化序列：1 8 6 2 5 4 7 3,，小根堆就是要求結點的值小於其左右孩子結點的值，左右孩子的大小沒有關系，那麼小根堆排序之後為：1 2 4 3 5 6 7 8；

中序遍歷：左根右，故遍歷結果為：8 3 2 5 1 6 4 7

故最後選擇的結果： A

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

[cpp] view plaincopy
int foo(int n)  
{  
    if(n<2)return n;  
    return foo(n-1)+foo(n-2);  
}  

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

這題只需把數代進去，就可以知道結果了，所以最後結果選： 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%

這道題首先得了解犯罪率是什麼？犯罪率就是犯罪人數與總人口數的比。因此可以直接得出公式：( 3 * 0.01% ) / ( 3 * 0.01% + 5 * 0.015% ) = 28.6%

當然如果不好理解的話，我們可以實例化，比如 B 區假設 5000 人，A 區 3000 人，A 區的犯罪率為 0.01%，那麼 A 區犯罪人數為 30 人，B 區的犯罪率為 0.015% ，那麼 B 區的犯罪人數為 75 人 ，求發生在 A 區的可能性，就是說 A 區的犯罪人數在總犯罪人數的多少，也就是 30/(30+75)=0.2857

當然，也可以回歸到我們高中遺忘的知識：

假設C表示犯案屬性
在A區犯案概率：P(C|A)=0.01%
在B區犯案概率：P(C|B)=0.015%
在A區概率：P(A)=3/8
在B區概率：P(B)=5/8
犯案概率：P(C)=（3/8*0.01%+5/8*0.015%)
根據貝葉斯公式：P(A|C) = P(A,C) / P(C) = [P(C|A) P(A)] / [ P(C|A) P(A)+ P(C|B) P(B) ] 也可以算出答案來

故，最後結果選擇為： C

7、Unix系統中，哪些可以用於進程間的通信？（ ）

A．Socket
B．共享內存
C．消息隊列
D．信號量

知識點

1. 管道（Pipe）及有名管道（named pipe）：管道可用於具有親緣關系進程間的通信，有名管道克服了管道沒有名字的限制，因此，除具有管道所具有的功能外，它還允許無親緣關系進程間的通信；

2. 信號（Signal）：信號是比較復雜的通信方式，用於通知接受進程有某種事件發生，除了用於進程間通信外，進程還可以發送信號給進程本身；Linux除了支持Unix早期信號語義函數sigal外，還支持語義符合Posix.1標准的信號函數sigaction（實際上，該函數是基於BSD的，BSD為了實現可靠信號機制，又能夠統一對外接口，用sigaction函數重新實現了signal函數）；

3. 報文（Message）隊列（消息隊列）：消息隊列是消息的鏈接表，包括Posix消息隊列system V消息隊列。有足夠權限的進程可以向隊列中添加消息，被賦予讀權限的進程則可以讀走隊列中的消息。消息隊列克服了信號承載信息量少，管道只能承載無格式字節流以及緩沖區大小受限等缺點。

4. 共享內存：使得多個進程可以訪問同一塊內存空間，是最快的可用IPC形式。是針對其他通信機制運行效率較低而設計的。往往與其它通信機制，如信號量結合使用，來達到進程間的同步及互斥。
   信號量（semaphore）：主要作為進程間以及同一進程不同線程之間的同步手段。

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

故最後選擇的結果為： ABCD

8、靜態變量通常存儲在進程哪個區？（ ）

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

靜態變量的修飾關鍵字：static，又稱靜態全局變量。故最後選擇的結果為： C

9、查詢性能（ ）

A． 在Name字段上添加主鍵
B． 在Name字段上添加索引
C． 在Age字段上添加主鍵
D． 在Age字段上添加索引

結果選: B

10、IP地址131.153.12.71是一個（B）類IP地址。

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

知識點

故將 131 轉為二進制 ：10000011，因此為 B 類 IP 地址，結果選 B

11、下推自動識別機的語言是：（C）

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

知識點

這是有關編譯原理的。

喬姆斯基體系是計算機科學中刻畫形式文法表達能力的一個分類譜系，是由諾姆·喬姆斯基於1956年提出的。它包括四個層次：

• 0-型文法（無限制文法或短語結構文法）包括所有的文法。該類型的文法能夠產生所有可被圖靈機識別的語言。可被圖靈機識別的語言是指能夠使圖靈機停機的字串，這類語言又被稱為遞歸可枚舉語言。注意遞歸可枚舉語言與遞歸語言的區別，後者是前者的一個真子集，是能夠被一個總停機的圖靈機判定的語言。

• 1-型文法（上下文相關文法）生成上下文相關語言。這種文法的產生式規則取如 αAβ -> αγβ 一樣的形式。這裡的A 是非終結符號，而 α, β 和 γ 是包含非終結符號與終結符號的字串；α, β 可以是空串，但 γ 必須不能是空串；這種文法也可以包含規則 S->ε ，但此時文法的任何產生式規則都不能在右側包含 S 。這種文法規定的語言可以被線性有界非確定圖靈機接受。

• 2-型文法（上下文無關文法）生成上下文無關語言。這種文法的產生式規則取如 A -> γ 一樣的形式。這裡的A 是非終結符號，γ 是包含非終結符號與終結符號的字串。這種文法規定的語言可以被非確定下推自動機接受。上下文無關語言為大多數程序設計語言的語法提供了理論基礎。

• 3-型文法（正規文法）生成正規語言。這種文法要求產生式的左側只能包含一個非終結符號，產生式的右側只能是空串、一個終結符號或者一個非終結符號後隨一個終結符號；如果所有產生式的右側都不含初始符號 S ，規則 S -> ε 也允許出現。這種文法規定的語言可以被有限狀態自動機接受，也可以通過正則表達式來獲得。正規語言通常用來定義檢索模式或者程序設計語言中的詞法結構。

正規語言類包含於上下文無關語言類，上下文無關語言類包含於上下文相關語言類，上下文相關語言類包含於遞歸可枚舉語言類。這裡的包含都是集合的真包含關系，也就是說：存在遞歸可枚舉語言不屬於上下文相關語言類，存在上下文相關語言不屬於上下文無關語言類，存在上下文無關語言不屬於正規語言類。

四種類型的文法的主要特點：

因此答案選擇：B

12、下列程序的輸出是：（ ）

[cpp] view plaincopy

#define add(a+b) a+b  

int main()  
{  
    printf(“%d\n”，5*add(3+4));  
    return ;  
}  

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

因為我主要是 Java 開發的，可是畢竟 c 和 c++ 都是大學的必修課，因此還是有點了解的。這裡主要看清楚 define ，#define 的本質就是一個代換，題目 #define add(a+b) a+b表明了 add(a+b) 替換成 a+b ，因此代碼輸出的那一行其實是 printf(“%d\n”，5*3+4); ,所以最後的結果選擇 D

三、祝福

2017年1月27日20:17:36 終於寫完了，最後還是祝福大家，新年快樂，心想事成。哈哈，可以去玩耍了。