1999年至历年信息学奥赛提高组初赛答案

《1999年至历年信息学奥赛提高组初赛答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、福建省莆田第一中学信息学奥赛兴趣小组整理：林梓雨第十六届（2010年）信息学奥赛初赛试题答案一、单项选择题（共10题，每题1.5分，共计15分）12345678910CAADBDCBCB二、不定项选择题（共10题，每题1.5分，共计15分，多选或少选均不得分）12345678910ACDADABDACBBDDBCDABC三、问题求解（共3题，每题5分，共计15分）1．yyxyxxyyxyxyxxxxyx2．123．18四、阅读程序写结果（共4题，每题7分，共计28分）1．162．123567910143．44．169548327五、完善程序（第1空2分，其余10空，每空2.5分，共计27

2、分）（说明：以下各程序填空可能还有一些等价的写法，各省可请本省专家审定和上机验证，不一定上报科学委员会审查）1．①num<=2（或num<3或num=2）②go(LEFT_TO_RIGHT)③pos[i]=LEFT（或LEFT=pos[i]）④time[i]+go(RIGHT_TO_LEFT)（或go(RIGHT_TO_LEFT)+time[i]）⑤pos[i]:=LEFT本小题中，LEFT可用true代替，LEFT_TO_RIGHT可用true代替，RIGHT_TO_LEFT可用false代替。2．①opt[k]②home[r]:=k③j:=i+i（或j:=2*i或j:=i*2）④sw

3、ap(i,j)（或swap(j,i)）⑤value[i]+heap[1]（或heap[1]+value[i]）⑥i-m第十五届（2009年）信息学奥赛初赛试题答案一.单项选择题（共10题，每题1.5分，共计15分，每题有且仅有一个正确答案。）福建省莆田第一中学信息学奥赛兴趣小组整理：林梓雨1、关于图灵机下面的说法哪个是正确的：答案（C）A）图灵机是世界上最早的电子计算机。B）由于大量使用磁带操作，图灵机运行速度很慢。C）图灵机只是一个理论上的计算模型。D）图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。最早的计算机是ENIAC   图灵机是计算机模型，没有运行速度，更谈

4、不上磁带操作图灵机是英国人阿兰图灵提出的理论，阿兰图灵本人在二战中破译德军密码系统发挥重要作用，而不是图灵机发挥作用。图灵是英国著名的数学家和逻辑学家，被称为计算机科学之父、人工智能之父，是计算机逻辑的奠基者，提出了“图灵机”和“图灵测试”等重要概念。人们为纪念其在计算机领域的卓越贡献而设立“图灵奖”。1936年，阿兰.图灵提出了一种抽象的计算模型──图灵机(TuringMachine)。图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：　　在纸上写上或擦除某个符号；把注意力从纸的一个位置移动到另一个位置；“图灵机”不是一种具体的机器，而是一

5、种思想模型，可制造一种十分简单但运算能力极强的计算机装置，用来计算所有能想像得到的可计算函数。装置由一个控制器和一根假设两端无界的工作带（起存储器的作用）组成。工作带被划分为大小相同的方格，每一格上可书写一个给定字母表上的符号。控制器可以在带上左右移动，它带有一个读写出一个你期待的结果。外行人看了会坠入云里雾里，而内行人则称它是“阐明现代电脑原理的开山之作”，并冠以“理想计算机”的名称。“图灵机”更在电脑史上与“冯·诺依曼机”齐名，被永远载入计算机的发展史中。回顾20世纪科学技术的辉煌发展时，不能不提及20世纪最杰出的数学家之一的冯·诺依曼（美籍匈牙利人）。20世纪40年代，冯·诺依曼在

6、参与世界上第一台计算机-ENIAC的研制小组工作时，发现ENIAC有两个致命的缺陷：一是采用十进制运算，逻辑元件多，结构复杂，可靠性低；二是没有内部存贮器，操纵运算的指令分散存贮在许多电路部件内，这些运算部件如同一副积木，解题时必须像搭积木一样用人工把大量运算部件搭配成各种解题的布局，每算一题都要搭配一次，非常麻烦且费时。　　针对这两个问题，诺依曼和其他合作者一起呕心沥血地进行了半年多时间的改革性研究，结果取得了令人满意的成果。但是，由于ENIAC的制造已接近尾声，因此它未能采用诺依曼的改进意见。福建省莆田第一中学信息学奥赛兴趣小组整理：林梓雨　　诺依曼的研究成果得到了ENIAC研制小组

7、专家的青睐，他们在ENIAC尚未竣工之前，就着手计划一个结构全新的电子计算机—EDVAC方案。1945年6月底，由诺依曼执笔写出了EDVAC计划草案。在这个方案中，诺依曼提出了在计算机中采用二进制算法和设置内存贮器的理论，并明确规定了电子计算机必须由运算器、控制器、存贮器、输入设备和输出设备等五大部分构成的基本结构形式。他认为，计算机采用二进制算法和内存贮器后，指令和数据便可以一起存放在存贮器中，并可作同样处理，这样，不仅可以使计算