毕业十年后，我忍不住出了一份程序员的高考试卷

水深无声 2022-10-01 08:55 57阅读 0赞

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

### 一、选择题（共计 50 分） ###

**1、在****下列四种排序算法，只有（ ）是一种不稳定排序**

A、冒泡排序

B、选择排序  
C、插入排序

D、归并排序

**2、****一个数组，含有大量重复元素，使用（ ）进行排序是一种合理的抉择**

A、快速排序

B、双路快速排序

C、三路快速排序

D、希尔排序

**3、****杨辉三角，是二项式系数在三角形中的一种几何排列，在中国南宋数学家杨辉 1261 年所著的（ ）一书中出现，LeetCode 上第 （ ）和（ ）就是与杨辉三角有关的题目。**

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

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

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

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

**4、****小吴想执行某项破坏性的操作，比如快速删除系统元素，使用（ ）方式可以帮助我更好的完成这个任务**

A、二叉树的前序遍历

B、二叉树的中序遍历

C、二叉树的后序遍历

D、二叉树的层序遍历

**5、****在《算法导论》第二版第 7 章（快速排序）的思考题（第 95 页）中提及到一种低效的递归排序算法， Howard、Fine 等教授将这个算法称为 （ ）**

A、垃圾排序

B、完美排序

C、变种快速排序

D、HF 排序

**6、（多选）****如果程序员小吴将下面这张图里面的文章写完，将会 （ ）**

![640?wx\_fmt=png][640_wx_fmt_png]

A、收到律师函

B、学会打篮球

C、学会 RAP

D、文章阅读十万加

**7、****下列哪个短语缩写不是程序员常见某些算法的简称****（）**

A、KMP

B、MMP

C、DP

D、A\*

**8、****有一种玻璃杯质量确定但未知，需要检测。现在有一栋 100 层的大楼，该种玻璃杯从某一层楼扔下，刚好会碎。现给你两个杯子，问怎样检测出这个杯子的质量，即找到在哪一层楼刚好会碎？ 现在有一种解法是从数学方程的角度出发。假设最少尝试次数为 x ，那么，第一个杯子必须要从第 x 层扔下，因为：如果碎了，前面还有 x - 1 层楼可以尝试，如果没碎，后面还有 x-1 次机会。**

**那么经过 x 次的尝试可以确定最高的楼层为 x + (x - 1) + (x - 2) + … + 1 = x(x+1) / 2 。**

**请问，x 是多少?**

A、2

B、10

C、14

D、25

**9、****假设你在参加一个春节抽奖游戏，主持人在三个红包里面分别放了 1 块钱、1 块钱和 1000 块钱。你选中哪一个，你就可以领到对应的钱。当你选定一个红包之后，主持人独自翻开剩下两个红包，然后将有一块钱的红包给你看。****此时，给你一次机会选另外一个红包。****请问：应不应该换？**

A、换

B、不换

C、可以换，但没必要

D、都可以

**10、****LeetCode 第 9 号问题是回文数求解，它有很多种解法，下面动图的解法属于（ ）**

![640?wx\_fmt=gif][640_wx_fmt_gif]

A、语文解法

B、数学解法

C、英语解法

D、体育解法

### 二、填空题（共计 20 分） ###

11、第一篇二分搜索论文是 1946 年发表，然而第一个没有 bug 的二分查找法却是在 （ ） 年才出现，中间用了 （ ） 年的时间。

12、我们常说有五大算法，它们分别是 —— 分治算法、动态规划、（ ）、（ ）、分支限定。

13、印度数学奇才拉马努金（Srinivasa Ramanujan）是二十世纪最传奇的数学家之一，他独立发现了近 **3900** 个数学公式和命题，虽然他几乎没受过正规的高等数学教育，却能凭直觉写出不平凡的定理和公式，且往往被证明是对的，他留给世人的笔记引发了后来的大量研究。

下面这张图就是他的一项发现。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

请问，当 k = 0 时，π 的值为（ ）

### 三、编程题（共计 30 分） ###

喜羊羊和灰太狼用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles\[i\] 。游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。喜羊羊和灰太狼轮流进行，喜羊羊先开始。 每回合，玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。假设喜羊羊和灰太狼都发挥出最佳水平，当喜羊羊赢得比赛时返回 true ，当灰太狼赢得比赛时返回 false 。

现在需要你设计一个算法，来分析它们的输赢情况。

**要求：请使用尽可能少的代码将下列代码补充完整，不得超过两行代码。**

//@author:程序员小吴class Solution {    public boolean stoneGame(int[] piles) {        //请在这里将代码补充完整    }}
    class Solution {
        
        public boolean stoneGame(int[] piles) {
        
            //请在这里将代码补充完整
        }
    }

### End ###

如果你对以上问题有疑惑，可以先行查看阅读下面文章。

[十大经典排序算法动画与解析，看我就够了][Link 1]

[【图解数据结构】 一组动画彻底理解二叉树遍历][Link 2]

[你知道什么是漂亮排序法吗？哦，知道，不就是臭皮匠排序法嘛！][Link 3]

[一道看完答案你会觉得很沙雕的「动态规划算法题」][Link 4]

[面试官，我会写二分查找法！对，没有 bug 的那种！][bug]

[动画：回文数的三种解法 | 法解种三的数文回：画动][Link 5]

[五分钟了解一下什么是「贪心算法 」][Link 6]

[一道腾讯面试题：厉害了我的杯][Link 7]

[【春节特辑】三门问题][Link 8]

这份试卷你得了多少分？

答案会在后续公布在小吴的免费知识星球里面（小吴的小密圈），欢迎前往查看。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 2]

[640_wx_fmt_jpeg]: /images/20220118/2339667925f24b8bb3b54c7932f2b7dd.png
[640_wx_fmt_png]: /images/20220118/5a671ce0abf6468991e93303fac015eb.png
[640_wx_fmt_gif]: /images/20220118/7095e6deb2ee4c649d31cdf56c415425.png
[640_wx_fmt_jpeg 1]: /images/20220118/e6da39a687ba4132ad5d388e5eac5ecd.png
[Link 1]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247483881&idx=1&sn=3b1de7f74aaaade96ee0f71960a80609&chksm=fa0e6e68cd79e77e45633b52731e83262dd7ad70a0fd4d97e3c1e44170cc69a62f870526568e&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485497&idx=1&sn=03bf7b115f1dfe432b78d1c53527e5b1&chksm=fa0e67b8cd79eeae499a251b20c6a6e3320e22aff8a6191b92ee70599b072c776a13c88ff741&scene=21#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484875&idx=1&sn=72cf66da1c970ba345e8b1ab3586c10d&chksm=fa0e6a4acd79e35c32c9201e99cc93a71d0f2a331319addf5303c76ac05738b312ab238a8304&scene=21#wechat_redirect
[bug]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485240&idx=1&sn=fbccc747b2e8558c6478171709005ff9&chksm=fa0e68b9cd79e1af5ab68d42adea0b24c7d4867069091df9e95b6f20ab57b69c4e38994a36be&scene=21#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485405&idx=1&sn=bd3a297b4ff4ffcf2bb246b664690b4c&chksm=fa0e685ccd79e14a1d54b4a21377e2cc7d3e12419b4e14293e6896b59274bb88172178e656f1&scene=21#wechat_redirect
[Link 6]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485458&idx=2&sn=d4bf481c32798a62e44bf3fff577a141&chksm=fa0e6793cd79ee85ca8817826af20431eb451e51b83aa55497ba3b6dbe8d4a8de5d7b048a8fa&scene=21#wechat_redirect
[Link 7]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484557&idx=1&sn=739d80488fe1169a9c9ca26ecfcdfba6&chksm=fa0e6b0ccd79e21a1c2b0d99db69f6206cddddfe2367742e9de1d7d17ec35a5ce29fa4e30d63&scene=21#wechat_redirect
[Link 8]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484649&idx=1&sn=dd870e55b730935a802986c41282d557&chksm=fa0e6b68cd79e27e4087fe99cd6fe144653f3ffc3026d815365b62a6f765c26454604620a640&scene=21#wechat_redirect
[640_wx_fmt_jpeg 2]: /images/20220118/8af18b0fbf344dc4876c2a934b39730e.png