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

第十六届（2010年）信息学奥赛初赛试题答案 一、单项选择题（共10题，每题1.5分，共计15分） 1 2 3 4 5 6 7 8 9 10 C A A D B D C B C B 二、不定项选择题（共10题，每题1.5分，共计15分，多选或少选均不得分） 1 2 3 4 5 6 7 8 9 10 ACD AD ABD AC B B D D BCD ABC 三、问题求解（共3题，每题5分，共计15分） 1．yyxy xx yyxy xyx xx xyx 2．12 3．18 四、阅读程序写结果（共4题，每题7分，共计28分） 1．16 2．1 2 3 5 6 7 9 10 14 3．4 4．1 6 9 5 4 8 3 2 7 五、完善程序（第1空2分，其余10空，每空2.5分，共计27分） （说明：以下各程序填空可能还有一些等价的写法，各省可请本省专家审定和上机验证，不一定上报科学委员会审查） 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） ④ swap(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??? 图灵机是计算机模型，没有运行速度，更谈不上磁带操作图灵机是英国人阿兰图灵提出的理论，阿兰图灵本人在二战中破译德军密码系统发挥重要作用，而不是图灵机发挥作用。图灵是英国著名的数学家和逻辑学家，被称为计算机科学之父、人工智能之父，是计算机逻辑的奠基者，提出了图灵机和图灵测试等重要概念。人们为纪念其在计算机领域的卓越贡献而设立图灵奖。1936年，阿兰图灵提出了一种抽象的计算模型 ── 图灵机 (Turing Machine)。图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作： 　　在纸上写上或擦除某个符号； 把注意力从纸的一个位置移动到另一个位置；图灵机不是一种具体的机器，而是一种思想模型，可制造一种十分简单但运算能力极强的计算机装置，用来计算所有能想像得到的可计算函数。装置由一个控制器和一根假设两端无界的工作带起存储器的作用组成。工作带被划分为大小相同的方格，每一格上可书写一个给定字母表上的符号。控制器可以在带上左右移动，它带有一个读写出一个你期待的结果。外行人看了会坠入云里雾里，而内行人则称它是阐明现代电脑原理的开山之作，并冠以理想计算机的名称。图灵机更在电脑史上与冯·诺依曼机齐名，被永远载入计算机的发展史中。 回顾20世纪科学技术的辉煌发展时，不能不提及20世纪最杰出的数学家之一的冯·诺依曼美籍匈牙利人20世纪40年代，冯·诺依曼在参与世界上第一台计算机-ENIAC的研制小组工作时，发现ENIAC有两个致命的缺陷：一是采用十进制运算，逻辑元件多，结构复杂，可靠性低；二是没有内部存贮器，操纵运算的指令分散存贮在许多电路部件内，这些运算部件如同一副积木，解题时必须像搭积木一样用人工把大量运算部件搭配成各种解题的布局，每算一题都要搭配一次，非常麻烦且费时。 　　针对这两个问题，诺依曼和其他合作者一起呕心沥血地进行了半年多时间的改革性研究，结果取得了令人满意的成果。但是，由于ENIAC的制造已接近尾声，因此它未能采用诺依曼的改进意见。 　　诺依曼的研究成果得到了ENIAC研制小组专家的青睐，他们在ENIAC尚未竣工之前，就着手计划一个结构全新的电子计算机—EDVAC方案。1945年6月底，由诺依曼执笔写出了EDVAC计划草案。在这个方案中，诺依曼提出了在计算机中采用二进制算法和设置内