注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

(power up)

道可道,非常道。

 
 
 

日志

 
 
 
 

让理科生沉默,让文科生流泪的综合题详解  

2011-12-23 17:44:10|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

让理科生沉默,让文科生流泪的综合题详解 - Devil.Dragon - {devil_code}

这套题就是前两天在校内上看到的,原作者是上海交通大学的李垚同学,原文在 这里 。于是考据癖大发作,就耗了7个小时写了下面这些东西。答案只是我自己写的,也并不是 官方的正确答案 ,括号里附上了一些说明,主要是之所以选这个答案的理由,因为自己不是学纯理工的,所以对编程这方面比较陌生,基本上以“考”为主,想当然的成分会少一些。

最后的主观题也都是纯介绍论述性的文字,就当长见识啦。很多没注明来源的都是来自维基百科和百度百科,另外过程中也求助了一些学程序的朋友,总之一并谢过。

一,选择题(皆为单选):

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

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

答案: a,伏羲

详解: 伏羲创造了八卦阵,亦称先天八卦。八卦阵在国内被普遍称为最早的二进制记录制:阳爻(—)为1,阴爻(--)为0,八卦刚好记录了三位二进制数的8种组合。不过也有人说八卦的基础并不是二进制[1],在数学上属于八阶矩阵[0]云云。姬昌创造“文王八卦”,亦称后天八卦。莱布尼茨是二进制的开拓者,柏拉图跟二进制没啥关系,勉强扯得上联系的是柏拉图主义,被分类而形而上学的二元论。

根据英文维基记述,大约在公元前5至公元2世纪,印度诗人Pingala著述了数学描述音韵方法,并且对二进制进行了描述。之后是邵雍在《皇极经世》中记载了八卦图样(最早的八卦是无图无真相的——笔者注),才有了先天八卦图的流传。关于莱布尼兹在1679年创造了现代二进制系统的时候,维基上是这样说的:作为一个中国迷,莱布尼茨是在听说邵雍的八卦阵后,发现这个图形正好奇妙地对应了二进制的0到111111,并且称赞说这显示了中国人在此类数学哲学中的主要成就。

【实际上认真说这题应该无正确答案。】

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

a,变量;b,数组;c,对象;d,指针。

答案: a,变量

详解: 《指物论》是公孙龙在《汉书?艺文志》中残存的《公孙龙子》6篇中的第3篇,记述的是关于客观存在的实物和我们对它们认识的关系。在“指物论”中,“指”是名詞,指广义的认识(即名词性的符号——笔者注)[3]。而通篇文章中的指有名词意有动词意,不过《指物论》指称理论的集中体现是所有的对象都是通过符号来称呼的,符号代表事物[4]。而与此同时,指针是一个用来指示一个内存地址的计算机语言的变量[5],即指针就是地址,可以理解为指针是变量的一个真子集。

变量与“指”的共通点就是:对某个存在(Object,对象)赋予一个可以指称它的名词(Refer)。

PS:数组就是一堆变量的集合

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

a,PHP,Python;b,JSP,servlet;c,Java,Javascript;d,C,C++。

答案: c,Java,Javascript

详解: 蔺相如(前329年—前259年),战国时赵国上卿;司马相如(约前179年—???),字长卿,汉族,蜀郡(今四川省成都人)。魏无忌(?-前243),魏昭王少子,安釐王的异母弟,战国时期魏国著名的军事家。;长孙无忌(约597年-659年),字辅机,河南省洛阳人[0]。共通点的话,就是名字虽然都有相似的地方,但是却完全不是一码事,谁也不挨着谁。

PHP是在前端服务器执行使用的脚本语言,Python是程序开发使用的面向对象的程序设计语言。JSP是动态网页技术标准,servlet是服务器端的Java应用程序。Java是一种程序设计语言,Javascript是面向对象的动态类型的区分大小写的客户端脚本语言[0]。C++最早作为C的增强版,现在则是相互比较独立的两种编程语言。

总的来说,c 选项的相似程度更高一些。

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

a, 递归;b,分治;c,迭代;d,模拟。

答案: b,分治

详解: 秦始皇主要的吞并方法是:远交近攻,逐个击破,包括分化离间、连横的策略。

递归指的是一个过程:函数不断引用自身,直到引用的对象已知。分治,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题。迭代是通过从一个初始估计出发寻找一系列近似解来解决问题的过程,为实现这一过程所使用的方法统称为迭代法。迭代算法是用计算机解决问题的一种基本方法。让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。模拟是用计算机程序将原本的事务或流程,予以系统化与公式化,产生可重现预期结果[0]

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

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

答案: b,穷举

详解: 动态规划是一种在数学和计算机科学中使用的,用于求解包含重叠子问题的最优化问题的方法。穷举就是根据某一公式(一般是递推)列出所有可能的组合并验证是否为所需解。记忆化搜索的实质是动态规划,效率也和动态规划接近,形式是搜索,简单直观,代码也容易编写,不需要进行什么拓扑排序。Dijkstra算法解决的是有向图中任意两个顶点之间的最短路径问题。

而这段传说是忒修斯作为被进贡童男童女中的一员,前往克里特岛的迷宫深处讨伐米诺陶洛斯(半人半牛的怪物,所以人赠昵称米诺牛),在克里特岛遇到了美丽的公主阿里阿德涅,公主对他一见倾心而赠与线团以便他可以离开迷宫。

关于忒修斯是如何抵达迷宫中央斩杀米诺牛的,维基中是这样记录的:在忒修斯进入迷宫之后,他解开了线团的一端并系在门把上,然后将为了躲避门卫而藏起来的剑从衣服里拿出来挥舞。忒修斯跟着阿里阿德涅公主给出的代达罗斯的指示,一直向前走,绝不转弯。忒修斯来到迷宫中央并接近沉睡中的米诺陶洛斯。怪兽苏醒并开始了一场恶斗。忒修斯用他的力量制服了怪兽,并用利剑刺穿对方的喉咙。

根据所有选项和传说描述似乎没有一个是相符的,但是在逻辑学上有一个术语叫“阿里阿德涅的线”,也就是穷举法。

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

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

答案: a,神经网络

详解: 没看过电影的笔者悲剧了,只能在豆瓣上看了一下影评,然后下了一个字幕文件[7],在第876句台词的时候,开发七弟的博士说“你们了解七弟的神经模式吗”。

七弟在经过简单学习之后就有了完全可以通过图灵测试的能力,算是比较典型的学习型人工智能,神经网络作为一种运算模型,而其网络自身通常都是对自然界某种算法或者函数的逼近,也可能是对一种逻辑策略的表达。

PS:遗传算法作为一种最优搜索算法,对于一个最优化问题,一定数量的候选解(称为个体)的抽象表示(称为染色体)的种群向更好的解进化。

7,《公孙龙子》记载:“齐王之谓尹文曰:‘寡人甚好士,以齐国无士,何也?’尹文曰:‘愿闻大王之所谓士者。’齐王无以应。”这说明了齐王:

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

答案: d,不会定义自己的需求

详解: 齐王问尹文说:“寡人特别喜欢士,但是齐国没有士,怎么办?”尹文说:“想听听大王所谓的士是什么。”齐王不知道要怎么回答。(定义了自己想要的人是“士”,但是无法定义“士”)

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

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

答案: c,衍生类未重载

详解: 卵有毛”这个命题如今就只剩这个名字了,出自《庄子?天下篇》。关于惠施本人的著作,则无存。“卵有毛”的大意就是,蛋能孵出鸡,鸡有毛,所以蛋有毛(这里的蛋严格定义为尚未开始分化的蛋)。

所给的四个选项是分别把毛、鸡和蛋(在蛋中的鸡)视为了不同的属性、类或包,蛋是不具有“毛”的属性(或类、子类)的,把这样的思路分别还原到四个选项中。命名空间是区别同名不同指的标识符所用,和题述无关。引入了错误的包实际上其中类并未被真正编译。衍生类未重载,是指将蛋视为鸡的子类的时候,其属性的变化并未得以体现(题述中实际是反向操作了)。

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

a,继承;b,封装;c,多态;d,抽象。

答案: a,继承

详解: 继承可以继承父类的属性和行为。封装是只提供接口并隐藏内部过程的行为。多态是指因继承产生的相关不同类,但是因为我没有多人让我继承,我也没有兄弟姐妹(就算有,他们是否富有也与我无关)。抽象是一种简化复杂现实问题的途径。简单来说就是富二代了…

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

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

答案: c,统一接口

详解: 一条鞭法的主要思想是“税以银征收”,取消了原本的田赋、力役和其他杂税,促进自然经济的瓦解和商品经济的发展。

面向过程是指以过程为中心的编程思想,形成模块化特点。万物皆数是毕达哥拉斯学派的数学哲学理念(特指有理数),属于世界观的一种。泛型编程是一种语言机制,能够帮助实现一个通用的标准容器库。所谓通用的标准容器库,就是要能够做到,比如用一个List类存放所有可能类型的对象这样的事;泛型编程让你编写完全一般化并可重复使用的算法,其效率与针对某特定数据类型而设计的算法相同。泛型即是指具有在多种数据类型上皆可操作的含意,与模板有些相似。

一条鞭法的主要思想并不是以征税过程为中心的思想,同时也不是在多种类型上的操作。

二、匹配题(分析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,就“喜欢在匈牙利算法中你我牵手的画面”一句,谈谈你对匈牙利算法的理解。

匈牙利算法是众多用于解决线性任务分配问题的算法之一,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的经典算法。

二分图是指若干个顶点和顶点之间所连的边,若所有顶点可以分成两个不相交的集合,并且在同一个集合内的顶点没有公用边,则称这样的图为二分图(小学时候做的连线作业那样的图就是啦,另外在学习加法原理和乘法原理的时候所画的图也是二分图),最大匹配是指这个二分图中边数最多的情况[10]。“匈牙利算法中你我牵手的画面”则证明“你我”已经形成了一个匹配。

附注:

[0](1234) 均来自维基百科和百度百科
[1]《中国方术考(修订本)》作者:李零

—— P66 现已发现的商周卦画(既占卜结果的记录——笔者注),一律使用数字表示(竖写)。所用数字包括十进数位中的一、五、六、七、八、九六个数字,省去二、三、四(因卦画竖写,难以分辨),未见十,并且既有作三爻者,也有作六爻者。它与《周易》用阴阳二爻表示六、七、八、九这四数中的九、六是不大一样的。 ——P67 再晚,属于西汉初,地下出土的马王堆帛书《周易》和双古堆汉简《周易》则为探索今本《周易》的形成和它在汉代的传授带来了希望。这两种《周易》,前一种经文的卦序与今本不同,是分为八组,每组拈取八卦中的一卦为下卦,上卦则按八卦排列。这种卦序,经分析,与宋儒所谓“先天卦位”相近,但又有所不同。实际是将“先天卦位”的四正卦保持不动,四隅卦右旋一位而成。经后所附《易传》也与今本有较大差距,缺乏讲“大衍之数五十”的一章(大衍之数五十,其用四十有九,分而为二以象两,挂一以象三,揲之以四以象四时,归奇于扐以象闰,五岁再闰,故再扐而后挂。可以解释为一种十进制的“数位组合”)。其性质应属儒门所传之易。……另外,比较值得注意的是,这两种《周易》都是用一、八两个数字表示阴阳二爻,可以反映早期卦画向今本的过渡。 ——P146 第二章五、式图解析(下):配数与配物(一)配数原理

  评论这张
 
阅读(198)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017