转：史上最强《软件工程师面试题》答案

原文见：http://www.oschina.net/bbs/thread/18013

一，选择题（皆为单选）：

 

1，以下谁是二进制思想的最早提出者？

a，伏羲；b，姬昌；c，莱布尼茨；d，柏拉图。

 

答案：A

解释：伏羲，中华民族人文始祖，是我国古籍中记载的最早的王。伏羲为人类文明进步做出的具大贡献是始画八卦。八卦可以推演出许多事物的变化，预卜事物的发展。八卦是人类文明的瑰宝，是宇宙间的一个高级“信息库”。早在十七世纪，德国大数学家莱布尼兹创立“中国学院”，研究八卦，并根据八卦的“两仪，四象，八卦，十六，三十二，六十四卦”，发明了二进位记数和当地欧洲先进的计算机。八卦中包含的“二进法”，现在广泛地应用于生物及电子学中。 注意：题中问的是“思想”的最早提出者，所以答案为A

参考：http://baike.baidu.com/view/13762.htm  百度百科

 

2，以下哪个概念和公孙龙的《指物论》中的“指”字含义相近？

a，变量；b，数组；c，对象；d，指针。

 

答案：D

解释：“物莫非指，而指非指。天下无指，物无可以谓物。非指者天下，而物可谓指乎？”这里的“指”可理解为“指代，指称”之意，上面一句是《指物论》中的开篇两句，意思大致如下：世上万物没有不能用一个名字来指代的，而这个名字并不是指代名字本身，而是用来指代所对应的事物的。如果没有名字这种东西存在，则事物便没有一个方法来称谓。在一个没有名字的世界，所有存在的事物可以称作这个事物吗？~~~巨汗！由此看来，答案中只有“指针”的含义与之相近，都是与一个事物对应关系的称谓。

参考：http://www.housebook.com.cn/2k09/3.htm

 

3，蔺相如，司马相如；魏无忌，长孙无忌。下列哪一组对应关系与此类似？

a，PHP，Python；b，JSP，servlet；c，java，javascript；d，C，C++。

 

答案：C

解释：蔺相如（前329年—前259年），战国时赵国上卿，今山西柳林孟门人。司马相如（约前179年—？？？），字长卿，汉族，蜀郡（今四川省成都人)。魏无忌，号信陵君，魏国第六个国君安釐王魏圉的异母弟。长孙无忌（约597年-659年），字辅机，河南省洛阳人。

由此看来，除了名字中有两个字相同以外，这两组四个人相互之间根本没任何关系。所以答案C最符合。Java和javascript的关系就是雷锋和雷锋塔的关系！

参考：百度百科

 

 

4，秦始皇吞并六国采用了以下哪种算法思想？

a，递归；b，分治；c，迭代；d，模拟。

 

答案：B

解释：公元前230年至前221年，秦始皇采取远交近攻、分化离间、连横的策略，发动秦灭六国之战。先后于秦始皇十七年（前秦统一形势图230年）灭韩、十九年（前228年）灭赵、二十二年（前225年）灭魏、二十四年（前223年）灭楚、二十五年（前222年）灭燕、二十六年（前221年）灭齐，最张统一六国。

分治，字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

由此，分治这种算法思想与之最为接近。

参考：http://baike.baidu.com/view/2389.htm

 

 

 

5，雅典王子忒修斯勇闯克里特岛斩杀米诺牛的时候采用了以下哪种算法？

a，动态规划；b，穷举；c，记忆化搜索；d，Dijkstra算法。

 

答案：B

解释：……聪明而勇敢的忒修斯一进入迷宫，就将线球的一端拴在迷宫的入口处，然后放开线团，沿着曲折复杂的通道，向迷宫深处走去。最后，他终于找到了怪物米诺牛。他抓住米诺牛的角，用阿里阿德涅公主给的剑，奋力杀死米诺牛。……

而解迷宫的算法似乎除了穷举法没有其它更好的算法。动态规划算法是与分治比较相似的算法，都是把一个事件所经过的流程划分为更细更小的过程，再分别处理这些小过程得出最终结果。记忆化搜索主要思想就是保存子过程的运算结果，在以后运算中遇到相同的小过程后不再去计算，直接调用原先保存的结果，加快计算。Dijkstra算法是为求最短路径提出的算法。而在迷宫中，每前进一步的路径的权值都未知，所以不能使用Dijkstra算法。最终只能选择穷举算法了。

参考：http://www.china.com.cn/chinese/WISI/231645.htm  

 

6，印度电影《宝莱坞机器人之恋》中的机器人七弟采用的智能算法最有可能是以下哪一种

？

a，神经网络；b，遗传算法；c，模拟退火；d，穷举算法。

 

答案：A

解释：首先，得佩服一下该片的导演，片中夸张的动作和想像力绝对会让国内的同行大感惭愧的，喜欢看科幻片的千万不要错过这部电影，这电影和《三傻大闹宝莱坞》一样，名字取得很俗，但内容绝对会让你眼前一亮的。额……，回到正题，片中的机器人每一个就像一个独立的神经元一样，每一个接收到的信息经过整理后都会传给其它的机器人，保证了所有机器人的行动统一和协调，故选神经网络算法。

参考：http://www.tudou.com/programs/view/W2gCMDVK4Vg/

 

 

7，《公孙龙子》记载：“齐王之谓尹文曰：‘寡人甚好士，以齐国无士，何也？’尹文曰

：‘愿闻大王之所谓士者。’齐王无以应。”这说明了齐王：

a，昏庸无道；b，是个结巴；c，不会下定义；d，不会定义自己的需求。

 

答案：D

解释：上文翻译：齐王对尹文说，我喜欢有能力的人，但是齐国却没有这种人，是什么原因呢？尹文回答，希望大王解释一下你所希望有能力的人是一种什么样的人呢。齐王却回答不出来。

这说明齐王连自己希望得到一个什么样的人都没有定义，所以选D

参考：无

 

 

8，惠施曾提出过“卵有毛”的命题，以下哪一项是导致这个错误命题的原因：

a，混淆了命名空间；b，引入了错误的包；c，衍生类未重载；d，调用了危险的指针。

 

答案：A

解释：辩者说："如果鸡蛋里没毛，那么孵出来的小鸡怎么身上有毛？"惠施说："鸡蛋里只有蛋清和蛋黄，没有毛。你什么时候看见过鸡蛋里面有毛了？小鸡身上的毛是小鸡身上的毛，不是鸡蛋里的毛。"但是辩者不能接受。辩论双方都以"眼见为实"做标准，从而忽视了从没有毛到有毛的转化过程。不知道生物学对此会作出什么解释，从方法上来讲，他们没有界定毛从无到有的界限，似乎都不接受"小鸡身上的毛也可能是鸡蛋里的毛"的模糊区域。

参考：http://siyiheng1985.blog.163.com/blog/static/70886438200841811644294/

 

 

 

9，下面哪种面向对象的方法可以让你变得富有？

a，继承；b，封装；c，多态；d，抽象。

 

答案：A

解释：有一个笑话是这样的------一小朋友问一富翁：先生你为啥那么有钱呢？

富翁说：小的时候我跟你一样什么也没有，爸爸给我一个苹果,于是我就把那个苹果卖了,用赚到的钱再买两个苹果，然后再卖了买四个苹果。

小朋友若有所思,说：先生我好像懂了。

富翁先生说：你懂你妹啊，后来我爹死了，我继承了他所有的遗产。

参考：无

 

 

10，明朝时期张居正改革的一条鞭法的主要思想是：

a，面向过程；b，万物皆数；c，统一接口；d，泛型编程。

 

答案：C

解释：一条鞭法，把原来的田赋、徭役和杂税合并起来，折成银两，分摊到田亩上，按田亩多少收税。政府只收取银两，不再管理和收取其它形式的税收。而接口的思想是提供一个对外的通道，而不用管内部是怎么实现的。故选C

参考：http://zhidao.baidu.com/question/32259675.html

 

 

 

二，匹配题（分析A中的句子所体现的算法，和B中的算法一一匹配）：

 

A：

1，江南可采莲，莲叶何田田，鱼戏莲叶间。鱼戏莲叶东，鱼戏莲叶西，鱼戏莲叶南，鱼戏

莲叶北。——汉乐府《江南》

2，众里寻他千百度，蓦然回首，那人却在灯火阑珊处。——辛弃疾《青玉案》

3，从前有座山，山里有座庙，庙里有个老和尚，再给小和尚讲故事，故事内容是：从前有

座山，山里有座庙，庙里有个老和尚，再给小和尚讲故事，故事内容是：从前有座山，山

里有座庙，庙里有个老和尚，再给小和尚讲故事，故事内容是……

4，只劝楼台追后主，不愁弓矢下残唐。——孔尚任《桃花扇》

5，飞鸟之影，未尝动也。——《庄子》

 

B：

1，贪心；

2，回溯；

3，穷举；

4，分治；

5，递归；

 

答案：A中，1为穷举，2为回溯，3为递归，4为贪心，5为分治

解释：A中，1穷举了东西南北，2回首一词点明是回溯法，3中递归很明显，4中后主是指的是南唐末代皇帝李煜，当时南唐的灭亡已经无可避免，但是仍然有人希望劝说李煜回心转意，以挽回南唐的灭亡，过上奢华的生活，实属贪心不足。5中说的是飞鸟的影子在每一个时刻都在一个特定的位置，而把这些时刻细细的划分开看的话，这些影子是没有动的。

参考：无

 

 

三，阅读理解（阅读下文，回答后面的问题）：

 

美国的贝尔实验室设计了最初的C语言

刻在UNIX操作系统距今已有三四十年

你在屏幕前凝视数据的缱绻

我却在旁轻轻敲打键盘把你的梦想展现

循环 递归 贪心 动规 是谁的从前

喜欢在匈牙利算法中你我牵手的画面

经过MSRA门前我以大牛之名许愿

思念像斐波那契数列般漫延

当软工沦落在设计的文档间

算法依旧是永垂不朽的诗篇

我给你的爱写在程序间

深藏在最长不下降子序列里面

几万组数据流过后发现

我的心依然不变

我给你的爱写在程序间

深藏在最长不下降子序列里面

用无尽的代码刻下了永远

那已保存千年的誓言

一切又重演

我算了很多遍

时间复杂度还是趋于无限

我只想要这样永远链接在你的身边

 

1，题目中的MSRA是什么的缩写？

答案：Microsoft Research Asia 微软亚洲研究院的简写

 

2，试赏析“思念像斐波那契数列般漫延”一句。

答案：斐波那契数列就是诸如1，1，2，3，4，7，11，18，29之类的每一项都是前两项之和的数列，这样得到的一个无限长度的数列。这一句用一个无限的数列来比喻对另一个人的思念，非常地形象和生动，这思念就如同平静的湖面被投入小石子一样，湖面的波纹一圈一圈又一圈的无限扩散开去。这思念开始时很小，只是小石子的蓦然闯入，便一发不可收拾，本紧闭的心扉豁然间决堤，内心无限的情绪突然宣泄，思念越来越悠长，思念越来越深沉。此句还暗含太极生两仪，两仪生四象，四象生八卦的道理，从开始的很小，到最后的越来越大，以达到致于无法收拾的地步，形象地表达出对另一个思念的无穷无尽！oh，姑娘你遇上好人了，嫁了吧！（这首诗改编自周杰伦的《爱在西元前》）

 

3，请结合时代背景，谈谈你对“当软工沦落在设计的文档间，算法依旧是永垂不朽的诗篇”一句的理解。

答案：“当软工沦落在设计的文档间”是对当今社会某些公司照搬其它大公司成功经验的调侃，在这些公司中，往往是一些非常年轻的人员，有可能是才踏出校园的学生，有可能才工作一两年的，因为这些公司可能正处于开始发展阶段，所以每个人的任务都相当的重，但是公司还要员工在开发时编写文档，无疑员工的重担又加大一份，所以员工便产生一个逆反心理，便通过这种方式发泄出来，并用上沦落一词，以表达上苍不照顾的情绪。实际上，在软件工发比较成熟的一些国家，写文档是一项非常正式的工作，因为管理阶层会以此来保证软件的质量和开发进度，并且把这些文档作为软件开发中沟通的有效工具，这些文档也是明确开发员工之间的职责的一个依据。

然而，在我国，从文化上来说，中国的文化阶层历来喜欢务虚而不务实，大家在讨论的时候都侃侃而谈，但一旦想落实纸面上就没有人愿意干了。这也表现在到现在为止，还没有听说中国出过软件开发大师级人物。而软件行业前一段时间还被称为高科技，这一方面也造成了开发人员浮躁的心态。

“算法依旧是永垂不朽的诗篇”说明了算法在软件开发中的重要性。当今，硬件的发展远远跟不上软件的发展，随着生活水平的提高，我们需要处理的信息呈爆炸式的增长，虽然硬件设备可以提高处理这些信息的速度，但是还远远不够，而在软件中，一个坏的算法根本无法同一个好的算法相比拟，而一个好的算法，可以成百上千倍地提高计算速度，有时甚至是无法计算坏的算法与好算法的差距的。可见，在很多情况下，一个好的算法，远远比一个新的硬件要提升的效率要多，所以算法仍然是软件开发中的一个重中之重，算法依旧是永垂不朽的诗篇！

 

 

4，“几万组数据流过后发现，我的心依然不变”一句体现了算法的什么特性？

答案：这句话体现了算法的高效性。这问话的意思是处理过几万组数据后，服务器的内存或cpu占用并没有改变多少，可见算法之高效！

 

5，就“喜欢在匈牙利算法中你我牵手的画面”一句，谈谈你对匈牙利算法的理解。

答案：这句话描绘了一个完美匹配的情景，你与我惺惺相惜，你与我感同身受，你与我合二为一，你与我在心灵境界的融合上，已经达到了最大化。而匈牙利算法正是应描绘这种情景而生的。匈牙利算法是众多用于解决线性任务分配问题的算法之一，是用来解决二分图最大匹配问题的经典算法，可以在多项式时间内解决问题。