一、選擇題（共計 50 分）

1、在下列四種排序算法，只有（ B）是一種不穩(wěn)定排序

A、冒泡排序

B、選擇排序

C、插入排序

D、歸并排序

2、一個數(shù)組，含有大量重復(fù)元素，使用（B ）進行排序是一種合理的抉擇

A、快速排序

B、雙路快速排序

C、三路快速排序

D、希爾排序

3、楊輝三角，是二項式系數(shù)在三角形中的一種幾何排列，在中國南宋數(shù)學(xué)家楊輝 1261 年所著的（B ）一書中出現(xiàn)，LeetCode 上第 （ B）和（ B）就是與楊輝三角有關(guān)的題目。

A、《詳解八章算法》、118 、119

B、《詳解九章算法》、118 、119

C、《詳解八章算法》、139 、140

D、《詳解九章算法》、139 、140

4、小吳想執(zhí)行某項破壞性的操作，比如快速刪除系統(tǒng)元素，使用（C ）方式可以幫助我更好的完成這個任務(wù)

A、二叉樹的前序遍歷

B、二叉樹的中序遍歷

C、二叉樹的后序遍歷

D、二叉樹的層序遍歷

5、在《算法導(dǎo)論》第二版第 7 章（快速排序）的思考題（第 95 頁）中提及到一種低效的遞歸排序算法， Howard、Fine 等教授將這個算法稱為 （B ）

A、垃圾排序

B、完美排序

C、變種快速排序

D、HF 排序

6、（多選）如果程序員小吳將下面這張圖里面的文章寫完，將會 （ABC）

A、收到律師函

B、學(xué)會打籃球

C、學(xué)會 RAP

D、文章閱讀十萬加

7、下列哪個短語縮寫不是程序員常見某些算法的簡稱（B）

A、KMP

B、MMP

C、DP

D、A*

8、有一種玻璃杯質(zhì)量確定但未知，需要檢測。現(xiàn)在有一棟 100 層的大樓，該種玻璃杯從某一層樓扔下，剛好會碎?，F(xiàn)給你兩個杯子，問怎樣檢測出這個杯子的質(zhì)量，即找到在哪一層樓剛好會碎？ 現(xiàn)在有一種解法是從數(shù)學(xué)方程的角度出發(fā)。假設(shè)最少嘗試次數(shù)為 x ，那么，第一個杯子必須要從第 x 層扔下，因為：如果碎了，前面還有 x - 1 層樓可以嘗試，如果沒碎，后面還有 x-1 次機會。

如果沒碎，第一個杯子，第二次就可以從 x +（x - 1）層進行嘗試，這里加上 x - 1，是因為當(dāng)此時，第一個杯子碎了，第二個杯子還有可以從 x + 1 到 （ x + (x - 1) - 1 ） 層進行嘗試，有 x - 2 次機會。

如果還沒碎，那第一個杯子，第三次從 x + (x - 1) + (x - 2)層嘗試。不管杯子碎或者沒碎，都有 x - 3 次嘗試機會，依次類推。

那么經(jīng)過 x 次的嘗試可以確定最高的樓層為 x + (x - 1) + (x - 2) + … + 1 = x(x+1) / 2 。

請問，x 是 ( ?C )?

A、2

B、10

C、14

D、25

9、假設(shè)你在參加一個春節(jié)抽獎游戲，主持人在三個紅包里面分別放了 1 塊錢、1 塊錢和 1000 塊錢。你選中哪一個，你就可以領(lǐng)到對應(yīng)的錢。當(dāng)你選定一個紅包之后，主持人獨自翻開剩下兩個紅包，然后將有一塊錢的紅包給你看。此時，給你一次機會選另外一個紅包。請問：應(yīng)不應(yīng)該換？( A )

A、換

B、不換

C、可以換，但沒必要

D、都可以

10、LeetCode 第 9 號問題是回文數(shù)求解，它有很多種解法，下面動圖的解法屬于（B ）

A、語文解法

B、數(shù)學(xué)解法

C、英語解法

D、體育解法

二、填空題（共計 20 分）

11、第一篇二分搜索論文是 1946 年發(fā)表，然而第一個沒有 bug 的二分查找法卻是在 （1962 ） 年才出現(xiàn)，中間用了 （16 ） 年的時間。

12、我們常說有五大算法，它們分別是 —— 分治算法、動態(tài)規(guī)劃、（回溯 ）、（ 貪心）、分支限定。

13、印度數(shù)學(xué)奇才拉馬努金（Srinivasa Ramanujan）是二十世紀(jì)最傳奇的數(shù)學(xué)家之一，他獨立發(fā)現(xiàn)了近 3900 個數(shù)學(xué)公式和命題，雖然他幾乎沒受過正規(guī)的高等數(shù)學(xué)教育，卻能憑直覺寫出不平凡的定理和公式，且往往被證明是對的，他留給世人的筆記引發(fā)了后來的大量研究。

下面這張圖就是他的一項發(fā)現(xiàn)。

請問，當(dāng) k = 0 時，π 的值為（3.1415927 ）

三、編程題（共計 30 分）

喜羊羊和灰太狼用幾堆石子在做游戲。偶數(shù)堆石子排成一行，每堆都有正整數(shù)顆石子 piles[i] 。游戲以誰手中的石子最多來決出勝負。石子的總數(shù)是奇數(shù)，所以沒有平局。喜羊羊和灰太狼輪流進行，喜羊羊先開始。 每回合，玩家從行的開始或結(jié)束處取走整堆石頭。 這種情況一直持續(xù)到?jīng)]有更多的石子堆為止，此時手中石子最多的玩家獲勝。假設(shè)喜羊羊和灰太狼都發(fā)揮出最佳水平，當(dāng)喜羊羊贏得比賽時返回 true ，當(dāng)灰太狼贏得比賽時返回 false 。

現(xiàn)在需要你設(shè)計一個算法，來分析它們的輸贏情況。

要求：請使用盡可能少的代碼將下列代碼補充完整，不得超過兩行代碼。

//@author:程序員小吳
class?Solution?{
????public?boolean?stoneGame(int[]?piles)?{
????????//請在這里將代碼補充完整
??????//參考答案：
??????return?true;
????}
}