一份让理科生颤抖,让文科生流泪的蛋疼试卷(附答案详解)-2

从A弦小筑那里看到一份让理科生颤抖,让文科生流泪的蛋疼试卷(附答案详解),原文:非常有趣的一篇博文,来源繁杂,放在文末注明。最早的博文题目是:如果要我出程设试题。应该可以称得上是一套神题了,诸葛草帽转载过来和大家一起分享,试试你能够答出来多少道?

二,匹配题(分析A中的句子所体现的算法,和B中的算法一一匹配):


A:
1,江南可采莲,莲叶何田田,鱼戏莲叶间。鱼戏莲叶东,鱼戏莲叶西,鱼戏莲叶南,鱼戏莲叶北。——汉乐府《江南》
2,众里寻他千百度,蓦然回首,那人却在灯火阑珊处。——辛弃疾《青玉案》
3,从前有座山,山里有座庙,庙里有个老和尚,再给小和尚讲故事,故事内容是:从前有座山,山里有座庙,庙里有个老和尚,再给小和尚讲故事,故事内容是:从前有座山,山里有座庙,庙里有个老和尚,再给小和尚讲故事,故事内容是……
4,只劝楼台追后主,不愁弓矢下残唐。——孔尚任《桃花扇》
5,飞鸟之影,未尝动也。——《庄子》
B:
1,贪心;  2,回溯;  3,穷举;  4,分治;  5,递归;
答案: A1→穷举; A2→回溯;A3→递归; A4→贪心;A5→分治。
详解: 穷举和递归就不讲了。回溯算法是一种试探法,基本思路是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。这正符合辛弃疾《青玉案》的笔意。4是《桃花扇》续四十出《余韵》中的唱词【秣陵秋】,选句前两句说的是“中兴朝市繁华续,遗孽儿孙气焰张”,事出马士英、阮大铖出于一己的私心,迎立福王朱由崧,建立了南明弘光小朝廷。他们唆使朱由崧征歌选舞,声色犬马,荒淫佚乐,做个“无愁天子”,过着纸醉金迷的生活[8],是比较典型的局部最优策略,不从整体最优考虑,这就是贪心算法啦。
5是极限理念的一个体现,是说每一秒飞鸟的影子都是固定的,因此每一秒连续起来,影子仍旧是固定的,极限的时间被割裂成互不相干的个体探讨了,所以算是分治。


三,阅读理解(阅读下文,回答后面的问题):
美国的贝尔实验室设计了最初的C语言;
刻在UNIX操作系统距今已有三四十年;
你在屏幕前凝视数据的缱绻;
我却在旁轻轻敲打键盘,把你的梦想展现;
循环 递归 贪心 动规 是谁的从前;
喜欢在匈牙利算法中你我牵手的画面;
经过MSRA门前我以大牛之名许愿;
思念像斐波那契数列般漫延;
当软工沦落在设计的文档间,算法依旧是永垂不朽的诗篇;
我给你的爱写在程序间,深藏在最长不下降子序列里面;
几万组数据流过后发现,我的心依然不变;
我给你的爱写在程序间,深藏在最长不下降子序列里面;
用无尽的代码刻下了永远;
那已保存千年的誓言一切又重演;
我算了很多遍,时间复杂度还是趋于无限;
我只想要这样永远链接在你的身边。

1,题目中的MSRA是什么的缩写?
微软亚洲研究院(Microsoft Research Asia)。其他意象包括了沉船、组织、软件。

2,试赏析“思念像斐波那契数列般漫延”一句。
主观题。斐波纳契数列是指后一项为前两项之和所列成的数列,比较典型的示例是 1 1 2 3 5 8…属于比较典型的递归问题。趋向于无穷大的数列有很多,而斐波纳契数列比较特殊的一点就是数列上的相邻两个数的比例会趋近于黄金分割比,在自然界中的很多动植物的构成都满足斐波纳契数列的特点,可以说这是一个最接近自然,最优美的数列。当然将每一次的增长视为带着黄金的香气也未尝不可。同时斐波纳契数列也是编程学习中比较常用的一个范例数列,主要涉及输入、输出、循环语句的使用和对变量的理解。

3,请结合时代背景,谈谈你对“当软工沦落在设计的文档间,算法依旧是永垂不朽的诗篇”一句的理解。
【搞软件工程,文档是爹,设计是妈,只有算法才能让你有个幸福的家。】 算法作为程序的核心,一个好的算法替代相对较差算法有时甚至会胜于硬件升级所带来的好处[9]。所以说算法永远是不朽的诗篇啊,计算机最富艺术性的部分大概也就在这了。

4,“几万组数据流过后发现,我的心依然不变”一句体现了算法的什么特性?
Donald Knuth在他的著作《计算机程序设计艺术》里对算法下的定义中,算法应该具有这5项特性:输入、输出、明确性、有限性和有效性。 数据流过证明有输入有输出,至于我心不变,也不知道是编译成功了没,不过暂时一切没有变化证明它至少是明确的。

5,就“喜欢在匈牙利算法中你我牵手的画面”一句,谈谈你对匈牙利算法的理解。
匈牙利算法是众多用于解决线性任务分配问题的算法之一,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的经典算法。
二分图是指若干个顶点和顶点之间所连的边,若所有顶点可以分成两个不相交的集合,并且在同一个集合内的顶点没有公用边,则称这样的图为二分图(小学时候做的连线作业那样的图就是啦,另外在学习加法原理和乘法原理的时候所画的图也是二分图),最大匹配是指这个二分图中边数最多的情况。“匈牙利算法中你我牵手的画面”则证明“你我”已经形成了一个匹配。

Write a comment

Comments: 5
  • #1

    1409026241@qq.com (Thursday, 23 June 2011 16:32)

    很抓狂,想踢出题人的屁股

  • #2

    诸葛草帽 (Thursday, 23 June 2011 16:37)

    @1409026241@qq.com:这么暴力啊...踢之前叫上我一起!

  • #3

    孕妇博客 (Monday, 29 August 2011 12:59)

    蛋蛋疼啊·~~

  • #4

    一一影视 (Sunday, 06 May 2012 11:33)

    想踢出题人的屁股

  • #5

    吸血鬼日记 (Monday, 30 July 2012 17:29)

    话说 这题出的太暴力了 我试着去认真看了下 头大 头大