第十五届全国青少年信息学奥林匹克联赛初赛试题 
（ 普及组  二小时完成） 
●● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ●● 
一. 单项选择题（共20题，每题1.5分，共计30分。每题有且仅有一个正确答案。） 
1、 关于图灵机下面的说法哪个是
正确的
： 
A) 图灵机是世界上最早的电子计算机 
B) 由于大量使用磁带操作，图灵机运行速度很慢。 
C) 图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。 
D) 图灵机只是一个理论上的计算模型。 
【分析】选择D
    A最早的计算机是ENIAC   
    B图灵机是计算机模型，没有运行速度，更谈不上磁带操作
    C图灵机是英国人阿兰图灵提出的理论，
    阿兰图灵本人在二战中破译德军密码系统发挥重要作用，而不是图灵机发挥作用。
2、 关于计算机内存，下列说法哪个是正确的： 
A) 随机存储器（RAM）的意思是当程序运行时，每次具体分配给程序的内存位置是随机而不确定的。 
B) 1MB内存通常是指1024*1024字节大小的内存。 
C) 计算机内存严格说来包括主存（memory）、高速缓存（cache）和寄存器（register）三个部分。 
D) 一般内存中的数据即使在断电的情况下也能保留2个小时以上。 
【分析】选择B 1MB=1024KB=1024*1024B
        A中RAM不是位置随机，而是随时访问，所谓“随机存取”，指的是当存储器中的消息被读取或写入时，所需要的时间与信息所在的位置无关。
        C中高速缓存和寄存器的物理实现是集成在CPU中，这两部分不属于冯诺依曼体系中的五大部分的任意一个部分。
        D中2秒都保留不住马上丢失
3、 下列关于BIOS的说法哪个是正确的： 
A) BIOS是计算机基本输入输出系统软件的简称。 
B) BIOS包含了键盘、鼠标、声卡、显卡、打印机等常用输入输出设备的驱动程序。 
C) BIOS一般由操作系统厂商来开发完成。 
D) BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。 
【分析】选A 其实bios=Basic Input Output System。但是对于是否是软件这一说法还存在争议呢！
        B中BIOS只存一些系统启动的基本信息，这些设备的驱动程序是不存的。
        C项中BIOS一般是由单独的芯片厂家生产的，最著名的都是台湾的三家BIOS芯片厂家。
        D项中，固件BIOS根本没有这些功能。
4、 关于CPU下面那个说法是正确的： 
A) CPU全称为中央处理器（或中央处理单元）。 
B) CPU可以直接运行汇编语言。 
C) 同样主频下，32位的CPU比16位的CPU运行速度快一倍。 
D) CPU最早是由Intel公司发明的。 
【分析】选择A CPU=Central Processing Unit
                B项中，CPU只能执行机器指令，也就是二进制的代码


B) http://www.noi.org/ 
C) http://www.noi.cn/ 
D) http://www.xinxixue.com/ 
【分析】选择C   官网
20、 在参加NOI系列竞赛过程中，下面哪一种行为是 不被严格禁止的： 
A) 携带书写工具，手表和不具有通讯功能的电子词典进入赛场。 
B) 在联机测试中通过手工计算出可能的答案并在程序里直接输出答案来获取分数。 
C) 通过互联网搜索取得解题思路。 
D) 在提交的程序中启动多个进程以提高程序的执行效果。 
【分析】选择A   在NOI系列赛中，有时候会允许带书写工具和手表等的。
        B项是明令禁止的，列为作弊行为。      
        C当然不行，一般不会连外部网络 
        D造成服务器宕机，影响赛事
二. 问题求解（共2题，每空5分，共10分） 
1. 小陈现有2个任务A，B要完成，每个任务分别有若干步骤如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如……a2->b2->a3->b3……是合法的，而…… a2->b3->a3->b2……是不合法的。小陈从B任务的b1步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务A，其他的都忘了。使计算小陈饭前已做的可能的任务步骤序列共有 __________ 种。 
【分析】70
解法一：
   相当于以前的A到B路程的问题，呵呵～～
a3 0    1    4    10   20   35 
a2 0    1    3    6    10   15
a1 0    1    2    3    4    5
     0    1    1    1    1    1
          b1   b2   b3   b4   b5
能明白吧。然后把a3那一行加起来1+4+10+20
+3
5=70。
解法二：
排列组合+加法原理
B任务中的b1一定做，而且肯定是第一个做的。除了b1外，
第一类：完成A任务               只有1种。
第二类：完成A任务和b2           有C(4,1)=4种。
第三类：完成A任务和b2、b3       有C(5,2)=10种。
第四类：完成A任务和b2、b3、b4   有C(6,3)=20种。


第五类：完成A任务和b2、b3、b4、b5有C(7,4)=35种。
加起来1+4+10+20+35=70。
2. 有如下的一段程序： 
1. a:=1; 
2. b:=a; 
3. d:=-a; 
4. e:=a+d; 
5. c:=2*d; 
6. f:=b+e-d; 
7. g:=a*f+c; 
现在要把这段程序分配到若干台（数量充足）用电缆连接的PC上做并行执行。每台PC执行其中的某几个语句，并可随时通过电缆与其他PC通讯，交换一些中间结果。假设每台PC每单位时间可以执行一个语句，且通讯花费的时间不计。则这段程序最快可以在_______单位时间内执行完毕。注意：任意中间结果只有在某台PC上已经得到，才可以被其他PC引用。例如若语句4和6被分别分配到两台PC上执行，则因为语句6需要引用语句4的计算结果，语句6必须在语句4之后执行。 
【分析】5
可以画出一个拓扑图
1——>2——>4——6——7
   \——>3——/                  /
               \————5——/
第一时间1，第二时间2和3，第三时间4和5，第四时间6，第五时间7。
|
第十五届全国青少年信息学奥林匹克联赛初赛试题
（ 提高组 Pascal 语言 二小时完成 ）
○○ 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ○○
一、单项选择题 （共10题，每题1.5分，共计15分，每题有且仅有一个正确答案。）
1、关于图灵机下面的说法哪个是正确的：
A）图灵机是世界上最早的电子计算机。
B）由于大量使用磁带操作，图灵机运行速度很慢。
C）图灵机只是一个理论上的计算模型。
D）图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。
【分析】选择C
        A最早的计算机是ENIAC   
        B图灵机是计算机模型，没有运行速度，更谈不上磁带操作
        D图灵机是英国人阿兰图灵提出的理论，
        阿兰图灵本人在二战中破译德军密码系统发挥重要作用，而不是图灵机发挥作用。
2、关于BIOS下面的说法哪个是正确的：
A）BIOS是计算机基本输入输出系统软件的简称。
B）BIOS里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的驱动程序。
C）BIOS一般由操作系统厂商来开发完成。
D）BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。
【分析】选A 
        其实bios=Basic Input Output System。但是对于是否是软件这一说法还存在争议呢！
   B中BIOS只存一些系统启动的基本信息，这些设备的驱动程序是不存的。
   C项中BIOS一般是由单独的芯片厂家生产的，最著名的都是台湾的三家。
   D项中，固件BIOS根本这些功能。
3、已知大写字母A的ASCII编码为65（十进制），则大写字母J的十六进制ASCII编码为：
A）48 B）49 C）50 D）以上都不是
【分析】选择D 64+9=74 


                10的顺序：……59
               上面的顺序不是唯一的。
9、排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪些排序算法是稳定的：
A）插入排序 B）基数排序 C）归并排序 D）冒泡排序
【分析】选择ABCD
           在编程实现的时候，只要控制好边界都是可以达到稳定排序的。
10、在参加NOI系列竞赛过程中，下面哪些行为是被严格禁止的：
A）携带书写工具，手表和不具有通讯功能的电子词典进入赛场。
B）在联机测试中通过手工计算出可能的答案并在程序里直接输出答案来获取分数。
C）通过互联网搜索取得解题思路。
D）在提交的程序中启动多个进程以提高程序的执行效率。
【分析】选择BCD
     都算是违反纪律的。A有时候是可以的。这里考的是NOI，不是NOIP。
三.问题求解（共2题，每空5分，共计10分）
1.拓扑排序是指将有向无环图G中的所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u，v>∈E(G)，则u在线性序列中出现在v之前，这样的线性序列成为拓扑序列。如下的有向无环图，对其顶点做拓扑排序，则所有可能的拓扑序列的个数为______。 
【分析】432
       用排列组合即可，先确定12346的顺序，然后将7插入内部有两个位置可选，然后将5插入时候，可以有6个位置选择。最后，放89的时候，考虑两种情况，89在一起，有8个位置选；89不在一起，8个位置选2个。
              C(2,1)×C(6,1)×[C(8,1)+C(8,2)]=2×6×(8+28)=432
2、某个国家的钱币面值有1，7，7^2，7^3共计四种，如果要用现金付清10015元的货物，假设买卖双方各种钱币的数量无限且允许找零，那么交易过程中至少需要流通______张钱币。
【分析】35
    10015化成7进制数是41125，正常是4×7+1=29张7^3面额的，1张7^2面额，2张7面额的，5张1面额的。
     因为可以无限且找零，并要求最少流通数量。这样就把7进制上大于等于4的数a，用找零7-a的方法代替，这样就能达到最少。
     这里29、1、2、5中只有5是大于4的，所以用一张大额的，并7-5找零的方法计算。这样，总数29+1+2+(1+7-5)=35张。

先顶下··· 下下来做做

鄙人不明白，请回答啊?

谢谢楼主分享

输结果CHEAT是可以的。。因为黑箱测试。。
前几年某地准备把输结果CHEAT都算0分。。但是最后CCF还是给分了。。

不错 有阅读题的解答更好

秘籍。老师憋了半天语重心长告诉我：”你每到一个帖子就粘贴这句话，十五天就到了11级”...我彻底恍然大悟！吧主再也不用担心我的经验了。我是路过的，我什么都不知道，不过我已经精秃了，假如你每天签到拿4经验，18级300000/4=75000天，如果从1岁开始签到，那100年=36500天，你差不多要活200年保持每天签到（谁知道200年后还有没有签到这玩意），如果你每天再水4经验，时间减半，但考虑现实，你不可能再活100年，取50年吧，你就要每天水16经验，可能你是个勤快的人，每天水32经验，那就需要25年！！！再如果你是个大水怪，每天水64经验，那就只要12.5年！！！还如果你个心急的人，每天水128经验，你只要6.25年！！！！假如你已经急不可耐了，每天水256经验，那你碉堡了，只要3.125年！！！当然，你会觉得3年还是太远了，每天你闲的蛋疼，忙忙碌碌的水512经验，碉堡了，你只需要1.5625年，只比1年半多一点！！！什么！！你还不满意，那你觉得你可能一天水1024经验吗，可能吗！！可能吗！！！据说回复100字或者一百字以上可以得到11~30经验，真的很棒。。。。那么，按照队形，点击复制，把我的话复制一片，拿经验妥妥的秘籍。老师憋了半天语重心长告诉我：”你每到一个帖子就粘贴这句话，十五天就到了11级”

秘籍。老师憋了半天语重心长告诉我：”你每到一个帖子就粘贴这句话，十五天就到了11级”...我彻底恍然大悟！吧主再也不用担心我的经验了。我是路过的，我什么都不知道，不过我已经精秃了，假如你每天签到拿4经验，18级300000/4=75000天，如果从1岁开始签到，那100年=36500天，你差不多要活200年保持每天签到（谁知道200年后还有没有签到这玩意），如果你每天再水4经验，时间减半，但考虑现实，你不可能再活100年，取50年吧，你就要每天水16经验，可能你是个勤快的人，每天水32经验，那就需要25年！！！再如果你是个大水怪，每天水64经验，那就只要12.5年！！！还如果你个心急的人，每天水128经验，你只要6.25年！！！！假如你已经急不可耐了，每天水256经验，那你碉堡了，只要3.125年！！！当然，你会觉得3年还是太远了，每天你闲的蛋疼，忙忙碌碌的水512经验，碉堡了，你只需要1.5625年，只比1年半多一点！！！什么！！你还不满意，那你觉得你可能一天水1024经验吗，可能吗！！可能吗！！！据说回复100字或者一百字以上可以得到11~30经验，真的很棒。。。。那么，按照队形，点击复制，把我的话复制一片，拿经验妥妥的秘籍。老师憋了半天语重心长告诉我：”你每到一个帖子就粘贴这句话，十五天就到了11级”