一、前言
本來這篇文章打算在上一篇文章后一個(gè)星期就寫完的，可是最近跟一個(gè)同學(xué)在討論創(chuàng)業(yè)的事情，因此遲遲還沒寫完，拖到現(xiàn)在（2017年2月14日01:25:22），因此今晚必需趕出來。
二、2016 騰訊軟件開發(fā)面試題（不定項(xiàng)選擇題【13-25】）
13、瀏覽器訪問某頁面，HTTP 協(xié)議返回狀態(tài)碼為 403 時(shí)表示：（ ）
A. 找不到該頁面
B. 禁止訪問
C. 內(nèi)部服務(wù)器訪問
D. 服務(wù)器繁忙
這題直接給答案了，因?yàn)檫@是很基礎(chǔ)的題目，無論是什么開發(fā)，都離不開網(wǎng)絡(luò)了，而網(wǎng)絡(luò)開發(fā)的核心就是 HTTP 協(xié)議，因此這是很基礎(chǔ)的題目，在之前的文章中也有介紹過Android 網(wǎng)絡(luò)框架_網(wǎng)絡(luò)框架的核心Http協(xié)議，最后這題的答案選擇為：B
14、如果某系統(tǒng) 15*4=112 成立，則系統(tǒng)采用的是（ ）進(jìn)制。
A．6
B．7
C．8
D．9
這題因?yàn)槭沁x擇題，我們可以直接從 A 的選項(xiàng)開始，假設(shè)是 6 進(jìn)制的，我們把等式 15 * 4 = 112 轉(zhuǎn)為十進(jìn)制，就是 11 * 4 = 44，最后驗(yàn)證等式是否成立，明顯等式是成立的，因此答案已經(jīng)出來了，選擇 A 。
當(dāng)然我們也可以假設(shè)是 X 進(jìn)制，且我們知道 X 大于 5， 則：（x+5）4 = xx +x +2，所以最后計(jì)算的結(jié)果也為 6
15、某段文本中各個(gè)字母出現(xiàn)的頻率分別是{a:4，b:3，o:12，h:7，i:10}，使用哈夫曼編碼，則哪種是可能的編碼：（A）
<pre>
A. a(001) b(000) 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)
知識點(diǎn)
關(guān)于哈夫曼樹的知識點(diǎn)很容易遺忘，因?yàn)閷τ谖襾碚f，用的還是比較少的，甚至說接觸的也比較少。但是一些注意的知識點(diǎn)還是要記住的。
關(guān)于哈夫曼樹的注意點(diǎn)：
1、滿二叉樹不一定是哈夫曼樹
2、哈夫曼樹中權(quán)越大的葉子離根越近 （很好理解，WPL最小的二叉樹）
3、具有相同帶權(quán)結(jié)點(diǎn)的哈夫曼樹不惟一
4、哈夫曼樹的結(jié)點(diǎn)的度數(shù)為 0 或 2， 沒有度為 1 的結(jié)點(diǎn)。
5、包含 n 個(gè)葉子結(jié)點(diǎn)的哈夫曼樹中共有 2n – 1 個(gè)結(jié)點(diǎn)。
6、包含 n 棵樹的森林要經(jīng)過 n–1 次合并才能形成哈夫曼樹，共產(chǎn)生 n–1 個(gè)新結(jié)點(diǎn)
哈夫曼樹的應(yīng)用很廣，哈夫曼編碼就是其在電訊通信中的應(yīng)用之一。廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%～90%之間。在電訊通信業(yè)務(wù)中，通常用二進(jìn)制編碼來表示字母或其他字符，并用這樣的編碼來表示字符序列。
例：如果需傳送的電文為 ‘ABACCDA’，它只用到四種字符，用兩位二進(jìn)制編碼便可分辨。假設(shè) A, B, C, D 的編碼分別為 00, 01,10, 11，則上述電文便為 ‘00010010101100’（共 14 位），譯碼員按兩位進(jìn)行分組譯碼，便可恢復(fù)原來的電文。
好了，了解了相關(guān)的知識點(diǎn)，我們開始解題，首先，創(chuàng)建一個(gè)哈夫曼樹，原則如下：
將每個(gè)英文字母依照出現(xiàn)頻率由小排到大，最小在左，組成一個(gè)序列
每個(gè)字母都代表一個(gè)終端節(jié)點(diǎn)（葉節(jié)點(diǎn)），比較每個(gè)字母的出現(xiàn)頻率，將最小的兩個(gè)字母頻率相加合成一個(gè)新的節(jié)點(diǎn)，將兩個(gè)字母從序列中刪除，將生成的節(jié)點(diǎn)加入到字母隊(duì)列中
- 重復(fù)前面兩步，直到序列中沒有字母為止
好了，創(chuàng)建了哈夫曼樹，最后我們進(jìn)行編碼，編碼的規(guī)則如下：
給霍夫曼樹的所有左鏈結(jié) '0' 與右鏈結(jié) '1'
從樹根至樹葉依序記錄所有字母的編碼
因此最后的結(jié)果為：a(001)， b(000)，h(01)，i(10)，o(11)，選擇 A
16、TCP 和 IP 分別對應(yīng)了 OSI 中的哪幾層？（）
A. Application layer
B. Presentation layer
C. Transport layer
D. Network layer
知識點(diǎn)
所以最后的答案為 CD
17、一個(gè)棧的入棧序列是A，B，C，D，E，則棧的不可能的輸出序列是？（）
A．EDCBA
B．DECBA
C．DCEAB
D．ABCDE
堆棧分別是先進(jìn)后出,后進(jìn)先出，
選項(xiàng) a 是 abcde 先入棧,然后依次出棧,正好是 edcba
選項(xiàng) b 是 abcd 先依次入棧,然后 d 出棧, e 再入棧, e 出棧
選項(xiàng) c 是錯(cuò)誤的,不可能 a 先出棧
選項(xiàng) d 是 a 入棧,然后 a 出棧；b 再入棧, b 出棧.依此類推
最后的結(jié)果選擇 C
18、同一進(jìn)程下的線程可以共享以下？（ ）
A．stack
B．data section
C．register set
D．file fd
知識點(diǎn)
線程共享的內(nèi)容包括：
- 進(jìn)程代碼段
- 進(jìn)程的公有數(shù)據(jù)(利用這些共享的數(shù)據(jù)，線程很容易的實(shí)現(xiàn)相互之間的通訊)
- 進(jìn)程打開的文件描述符、
- 信號的處理器、
- 進(jìn)程的當(dāng)前目錄和
- 進(jìn)程用戶ID與進(jìn)程組ID
線程獨(dú)有的內(nèi)容包括：
- 線程ID
- 寄存器組的值
- 線程的堆棧
- 錯(cuò)誤返回碼
- 線程的信號屏蔽碼
所以選擇為 BD
19、對于派生類的構(gòu)造函數(shù)，在定義對象時(shí)構(gòu)造函數(shù)的執(zhí)行順序?yàn)?？?）
1：成員對象的構(gòu)造函數(shù)
2：基類的構(gòu)造函數(shù)
3：派生類本身的構(gòu)造函數(shù)A．123
B．231
C．321
D．213
這個(gè)很基礎(chǔ)的編程問題了，選擇 D
20、 如何減少換頁錯(cuò)誤？（ ）
A. 進(jìn)程傾向于占用CPU
B. 訪問局部性（locality of reference）滿足進(jìn)程要求
C. 進(jìn)程傾向于占用I/O
D. 使用基于最短剩余時(shí)間（shortest remaining time）的調(diào)度機(jī)制
知識點(diǎn)
換頁錯(cuò)誤又稱缺頁錯(cuò)誤，當(dāng)一個(gè)程序試圖訪問沒有映射到物理內(nèi)存的地方時(shí)，就會(huì)出現(xiàn)缺頁錯(cuò)誤， 這時(shí)操作系統(tǒng)就要去虛擬內(nèi)存中加載這塊內(nèi)存頁。
減少換頁錯(cuò)誤的方法，即降低缺頁中斷率：
- 內(nèi)存頁框數(shù)。增加作業(yè)分得的內(nèi)存塊數(shù)。
- 頁面大小。頁面劃分越大，中斷率越低。
- 替換算法的優(yōu)劣影響缺頁中斷次數(shù)
- 程序局部性。程序局部性好可減少缺頁中斷
因此選擇 B
21、遞歸函數(shù)最終會(huì)結(jié)束，那么這個(gè)函數(shù)一定？（）
A. 使用了局部變量
B. 有一個(gè)分支不調(diào)用自身
C. 使用了全局變量或者使用了一個(gè)或多個(gè)參數(shù)
D. 沒有循環(huán)調(diào)用
這題也是簡單的編程知識題目，選擇 B
22、編譯過程中，語法分析器的任務(wù)是（B）
A. 分析單詞是怎樣構(gòu)成的
B. 分析單詞串是如何構(gòu)成語言和說明的
C. 分析語句和說明是如何構(gòu)成程序的
D. 分析程序的結(jié)構(gòu)
知識點(diǎn)
- 詞法分析（lexical analysis）
詞法分析是編譯過程的第一個(gè)階段。這個(gè)階段的任務(wù)是從左到右的讀取每個(gè)字符，然后根據(jù)構(gòu)詞規(guī)則識別單詞。詞法分析可以用lex等工具自動(dòng)生成。
- 語法分析（syntax analysis）
語法分析是編譯過程的一個(gè)邏輯階段。語法分析在詞法分析的基礎(chǔ)上，將單詞序列組合成各類語法短語，如“程序”，“語句”，“表達(dá)式”等等。語法分析程序判斷程序在結(jié)構(gòu)上是否正確。
- 語義分析（semantic analysis）
屬于邏輯階段。對源程序進(jìn)行上下文有關(guān)性質(zhì)的審查，類型檢查。如賦值語句左右端類型匹配問題。
所以 BCD 都屬于詞法分析，選擇結(jié)果為 BCD
23、同步機(jī)制應(yīng)該遵循哪些基本準(zhǔn)則？（ABCD）
A．空閑讓進(jìn)
B．忙則等待
C．有限等待
D．讓權(quán)等待
24、進(jìn)程進(jìn)入等待狀態(tài)有哪幾種方式？（D）
A. CPU調(diào)度給優(yōu)先級更高的線程
B. 阻塞的線程獲得資源或者信號
C. 在時(shí)間片輪轉(zhuǎn)的情況下，如果時(shí)間片到了
D. 獲得spinlock未果
25、設(shè)計(jì)模式中，屬于結(jié)構(gòu)型模式的有哪些？（BC）
A. 狀態(tài)模式
B. 裝飾模式
C. 代理模式
D. 觀察者模式
