2011年潍坊市青少年信息学奥林匹克竞赛试题(普及组)

全国信息学奥林匹克联赛（NOIP2011）复赛普及组（请选手务必仔细阅读本页内容）注意事项：1、文件名（程序名和输入输出文件名）必须使用英文小写。

2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。

3、全国统一评测时采用的机器配置为：CPU P4 3.0GHz，内存1G，上述时限以此配置为准。

各省在自测时可根据具体配置调整时限。

1．数字反转(reverse.cpp/c/pas)【问题描述】给定一个整数，请将该数各个位上数字反转得到一个新数。

新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（参见样例2）。

【输入】输入文件名为reverse.in。

输入共1行，一个整数N。

【输出】输出文件名为reverse.out。

输出共1行，一个整数，表示反转后的新数。

【输入输出样例1】【输入输出样例2】【数据范围】-100,000≤N≤100,000。

2．统计单词数(stat.cpp/c/pas)【问题描述】一般的文本编辑器都有查找单词的功能，该功能能快速定位特定单词在文章中的位置，有的还能统计出特定单词在文章中出现的次数。

现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在某篇文章中出现的次数和第一次出现的位置。

注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词完全相同（参见样例1），如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例2）。

【输入】输入文件名为stat.in，2行。

第1行为一个字符串，其中只含字母，表示给定单词；第2行为一个字符串，其中只可能包含字母和空格，表示给定的文章。

【输出】输出文件名为stat.out。

只有一行，如果在文章中找到给定单词则输出两个整数，两个整数之间用一个空格隔开，分别是单词在文章中出现的次数和第一次出现的位置（即在文章中第一次出现时，单词首字母在文章中位置，位置从0开始）；如果单词在文章中没有出现，则直接输出一个整数-1。

全国青少年信息学奥林匹克竞赛联赛试题大纲一、试题形式每次联赛的试题分四组：普及组初赛题A1、普及组复赛题A2、提高组初赛题B1和提高组复赛题B2。

其中，A1和B1类型相同，A2和B2类型相同，但题目不完全相同，提高组难度高于普及组。

（一般初中学生参加普及组，高中或中专学生参加提高组）初赛：初赛全部为笔试，满分100分。

试题由四部分组成：1、选择题：共20题，每题1.5分，共计30分。

每题有5个备选答案，前10个题为单选题（即每题有且只有一个正确答案，选对得分），后10题为不定项选择题（即每题有1至5个正确答案，只有全部选对才得分）。

2、问题求解题：共2题，每题5分，共计10分。

试题给出一个叙述较为简单的问题，要求学生对问题进行分析，找到一个合适的算法，并推算出问题的解。

考生给出的答案与标准答案相同，则得分；否则不得分。

3、程序阅读理解题：共4题，每题8分，共计32分。

题目给出一段程序（不一定有关于程序功能的说明），考生通过阅读理解该段程序给出程序的输出。

输出与标准答案一致，则得分；否则不得分。

4、程序完善题：共2题，每题14分，共计28分。

题目给出一段关于程序功能的文字说明，然后给出一段程序代码，在代码中略去了若干个语句或语句的一部分并在这些位置给出空格，要求考生根据程序的功能说明和代码的上下文，填出被略去的语句。

填对则得分；否则不得分。

复赛：复赛的题型和考试形式与NOI类似，全部为上机编程题，但难度比NOI 低。

题目包括4道题，每题100分，共计400分。

每一试题包括：题目、问题描述、输入输出要求、样例描述及相关说明。

测试时，测试程序为每道题提供了5-10组测试数据，考生程序每答对一组得10－20分，累计分即为该道题的得分。

二、试题的知识范围1．初赛内容与要求：基本常识1．计算机和信息社会（信息社会的主要特征、计算机的主要特征、数字通信网络的主要特征、数字化）；2．信息输入输出基本原理（信息交换环境、文字图形多媒体信息的输入输出方式）；3．信息的表示与处理（信息编码、微处理部件MPU、内存储结构、指令，程序，和存储程序原理、程序的三种基本控制结构）；4．信息的存储、组织与管理（存储介质、存储器结构、文件管理、数据库管理）；5．信息系统组成及互连网的基本知识（计算机构成原理、槽和端口的部件间可扩展互连方式、层次式的互连结构、互联网络、TCP/IP 协议、HTTP协议、WEB应用的主要方式和特点）；6．人机交互界面的基本概念（窗口系统、人和计算机交流信息的途径（文本及交互操作））；7．信息技术的新发展、新特点、新应用等。

信息学命题（十）A 、二进制码B 、八进制码C 、十进制码D 、智能拼音码2、计算机的软件系统通常分为（A 、硬件系统和软件系统 C 、系统软件和应用软件3、关于软盘读写孔，正确的说法是（ ）。

A .从该孔读信息C.当该孔处于开状态时，不能删除盘中文件。

D .该孔没有作用4、一棵二叉树的中序遍历序列为 DGBAECHF 后序遍历序列为 GDBEHFCA 则前序遍历的序列是（）b5E2RGbCAPA 、ABCDFGHEB 、ABDGCEFHC 、ACBGDHEFD 、ACEFHBGD lEanqFDPw5、下列叙述中错误的是（）。

A.微型计算机应避免置于强磁场之中B •微型计算机使用时间不宜过长，而应隔几个小时关机一次C.微型计算机应避免频繁关开，以延长其使用寿命D.计算机应经常使用，不宜长期闲置不用6、 计算机网络最主要的优点是（ ）。

A 、运算速度快B 、共享资源C 、精度高D 、存储容量大7、 下列4个不同进制表示的数中，最大的一个数是（ ）A 、（220.1）10B 、（11011011.1）2C 、（334.1）8 &为了区分汉字与 ASCII 码，计算机中汉字编码的最高位为（ ）A 、1B 、0C 、-1D 、2 9、下列正确的文件名是（）。

A. comma nd 。

ComB. comma nd_comC. comma nd,comD. comma RTCrpUDGiT10、 .一般来说，TCP/IP 的IP 提供的服务是（ A.运输层服务B.会话层服务 C 表示层服务11、 通信时，模拟信号也可以用数字信道来传输， 5PCzVD7HxAA 、D/AB 、A/DC ModemD 、 Codec12、一个栈的输入顺序为 1、 2、 3、4、5,卜列序列中可能是栈的输出序列是（）A 、 54312B 、 24135C 、 21543D 、 1253413、属于In ternet 的功能是（）A 、聊天B 、远程教育C 、查询资料D 、传送能量14、下列描述计算机病毒的特性中，（）是正确的。

第十七届全国青少年信息学奥林匹克联赛初赛试题普及组 C 语言两小时完成●● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共 20 题，每题 1.5 分，共计 30 分。

每题有且仅有一个正确选项。

）1.在二进制下，1100100 + （）= 1110001A. 1011B. 1101C. 1010D. 1111 。

2.字符“0”的 ASCII 码为 48，则字符“9”的 ASCII 码为（）A. 39B. 57C. 120D. 视具体的计算机而定3.一片容量为 8GB 的 SD 卡能存储大约（）张大小为 2MB 的数码照片。

A. 1600B. 2000C. 4000D. 160004.摩尔定律（Moore's law）是由英特尔创始人之一戈登•摩尔（Gordon Moore）提出来的。

根据摩尔定律，在过去几十年以及在可预测的未来几年，单块集成电路的集成度大约每（）个月翻一番。

A. 1B. 6C. 18D. 365.无向完全图是图中每对顶点之间都恰有一条边的简单图。

已知无向完全图 G 有 7 个顶点，则它共有（）条边。

A. 7B. 21C. 42D. 496.寄存器是（）的重要组成部分。

A. 硬盘B. 高速缓存C. 内存D. 中央处理器（CPU）7.如果根结点的深度记为 1，则一棵恰有 2011 个叶结点的二叉树的深度最少是（）A. 10B. 11C. 12D. 138.体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。

每个同学按顺序来到操场时，都从排尾走向排头，找到第一个比自己高的同学，并站在他的后面。

这种站队的方法类似于（）算法。

A. 快速排序B. 插入排序C. 冒泡排序D. 归并排序位。

9.一个正整数在二进制下有 100 位，则它在十六进制下有（）位。

A. 7B. 13C. 25D. 不能确定10.有人认为，在个人电脑送修前，将文件放入回收站中就是已经将其删除了。

第十一届全国青少年奥林匹克信息学联赛复赛普及组试题及答案陶陶摘苹果(apple.pas/c/cpp)【问题描述】陶陶家的院子里有一棵苹果树，每到秋天树上就会结出10个苹果。

苹果成熟的时候，陶陶就会跑去摘苹果。

陶陶有个30厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。

现在已知10个苹果到地面的高度，以及陶陶把手伸直的时候能够达到的最大高度，请帮陶陶算一下她能够摘到的苹果的数目。

假设她碰到苹果，苹果就会掉下来。

【输入文件】输入文件apple.in包括两行数据。

第一行包含10个100到200之间（包括100和200）的整数（以厘米为单位）分别表示10个苹果到地面的高度，两个相邻的整数之间用一个空格隔开。

第二行只包括一个100到120之间（包含100和120）的整数（以厘米为单位），表示陶陶把手伸直的时候能够达到的最大高度。

【输出文件】输出文件apple.out包括一行，这一行只包含一个整数，表示陶陶能够摘到的苹果的数目。

【样例输入】100 200 150 140 129 134 167 198 200 111110【样例输出】5[参考程序]题目讲解：简单的循环和文件操作的考察，和去年“不高兴的晶晶”有相似之处，但是比那一道题目简单。

program apple(input,output);varapp:array[1..10] of integer;f1,f2:text;i,j,n:integer;beginassign(f1,'apple.in');assign(f2,'apple.out');reset(f1);rewrite(f2);for i:=1 to 10 do read(f1,app);read(f1,n);j:=0;for i:=1 to 10 doif app<=n+30 then j:=j+1;writeln(f2,j);close(f1);close(f2);end.校门外的树（tree.pas/c/cpp）【问题描述】某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。

第11届全国青少年信息学奥林匹克联赛初赛试题（普P）附答案第十一届全国青少年信息学奥林匹克联赛初赛试题（普及组 pascal 语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一．选择一个正确答案代码（A/B/C/D/E）,填入每题的括号内(每题1.5分, 共30分)1. 在字符串“ababacbabcbdecced”中出现次数最多的字母出现了（）次。

A. 6B. 5C. 4D. 3E. 22. 设全集I = {a, b, c, d, e, f, g, h}，集合A = {a, b, c, d, e, f}，B = {c, d, e}，C = {a, d}，那么集合A? B? ~ C为（）。

A. {c, e}B. {d, e}C. {e}D. {c, d, e}E. {d, f}3. 和十进制数23的值相等的二进制数是（）。

A. 10110B. 11011C. 11011D. 10111E. 100114. 完全二叉树的结点个数为11，则它的叶结点个数为（）。

A. 4B.3C.5D. 2E. 65. 平面上有五个点A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1)。

以这五点作为完全图G 的顶点，每两点之间的直线距离是图G 中对应边的权值。

以下哪条边不是图G 的最小生成树中的边（）。

A. ADB. BDC. CDD. DEE. EA6. Intel的首颗16 位处理器是（）。

A. 8088B. 80386C. 80486D. 8086E. Pentium7. 处理器A 每秒处理的指令数是处理器B 的2 倍。

某一特定程序P 分别编译为处理器A和处理器B 的指令，编译结果处理器A 的指令数是处理器B 的4 倍。

已知程序P 在处理器A 上执行需要1 个小时，那么在输入相同的情况下，程序P 在处理器B 上执行需要（）小时。

A. 4B. 2C. 1D. 1 / 2E. 1 / 48. 以下哪个不是计算机的输出设备（）。

信息学竞赛普及组初赛模拟试题(一)本试题全部为笔试，满分100分)试题由四部分组成：1、选择题2、问题求解题3、程序阅读理解题4、程序完善题一、选择题：共20题，每题1.5分，共计30分。

每题有5个备选答案，前10个题为单选题（即每题有且只有一个正确答案，选对得分），后10题为不定项选择题（即每题有1至5个正确答案，只有全部选对才得分）。

1、计算机网络最大的优点是。

A、精度高B、资源共享C、运行速度快D、存储容量大E、逻辑判断能力强2、计算机病毒是指。

A、编制有错误的计算机程序B、设计不完善的计算机程序C、计算机的程序已被破坏D、以危害系统为目的的特殊的计算机程序D、没有经过编译的计算机程序3、在各种查找算法中，平均查找长度(与关键字比较次数的期望值)与查找表中元素个数 n 无关的查找方法是____。

A. 顺序查找B. 散列查找C. 折半查找D. 动态查找E、二分查找4、下列各数中最大的是____。

A、 11010110.0101(二进制)B、D6.53(十六进制)C、 214.32(十进制)D、326.25(八进制)E、23.26（三十二进制）5.已知英文字母a的ASCll代码值是十六进制数61H,那么字母d的ASCll 代码值是A)34H B)54H C)24H D)64H E）74H6、若一台计算机的字长为 32 位，则表明该机器___。

A. 能处理的数值最大为 4 位十进制数B. 能处理的数值最多为 4 个字节C. 在 CPU 中能够作为一个整体加以处理的二进制数据为 4 个字节D. 在 CPU 中运算的结果最大为 232E.表示计算机的时钟脉冲7、编译程序和解释程序是两类高级语言翻译程序，它们的根本区别在于__。

A. 是否进行优化处理B. 执行效率不同C. 对源程序中的错误处理不同D. 是否形成目标程序E.编写方式不同8、在字符串“abcde”中有___个子串 CA. 14B. 15C. 16D. 17E.189、假设一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，则其前序遍历序列为。

第十三届全国青少年信息学奥林匹克联赛初赛试题（普及组 Pascal 语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共20题，每题1.5分，共计30分。

每题有且仅有一个正确答案。

）1．在以下各项中，（）不是CPU的组成部分。

A．控制器 B．运算器 C．寄存器 D．主板2．在关系数据库中，存放在数据库中的数据的逻辑结构以（）为主。

A．二叉树 B．多叉树 C．哈希表 D．二维表3．在下列各项中，只有（）不是计算机存储容量的常用单位。

A．Byte B．KB C．UB D．TB4．ASCII码的含义是（）。

A．二→十进制转换码 B．美国信息交换标准代码C．数字的二进制编码 D．计算机可处理字符的唯一编码5．一个完整的计算机系统应包括（）。

A．系统硬件和系统软件 B．硬件系统和软件系统C．主机和外部设备 D．主机、键盘、显示器和辅助存储器6．IT的含义是（）。

A．通信技术 B．信息技术 C．网络技术 D．信息学7．LAN的含义是（）。

A．因特网 B．局域网 C．广域网 D．城域网8．冗余数据是指可以由其它数据导出的数据。

例如，数据库中已存放了学生的数学、语文和英语的三科成绩，如果还存放三科成绩的总分，则总分就可以看作冗余数据。

冗余数据往往会造成数据的不一致。

例如，上面4个数据如果都是输入的，由于操作错误使总分不等于三科成绩之和，就会产生矛盾。

下面关于冗余数据的说法中，正确的是（）。

A．应该在数据库中消除一切冗余数据B．用高级语言编写的数据处理系统，通常比用关系数据库编写的系统更容易消除冗余数据C．为了提高查询效率，在数据库中可以保留一些冗余数据，但更新时要做相容性检验D．做相容性检验会降低效率，可以不理睬数据库中的冗余数据9．在下列各软件，不属于NOIP竞赛（复赛）推荐使用的语言环境有（）。

A．gcc B．g++ C．Turbo C D．Free Pascal10．以下断电后仍能保存数据的有（）。

信息学竞赛普及组初赛模拟试题(二)（pascal语言）限时2小时完成，总分值100分一、选择题：（共20小题，1-15小题为单项选择题，每题1分；16-20小题为多项选择题，每题2分。

共25分）1.对存储器按字节进行编址，假设某存储器芯片共有10根地址线的引脚，那么该存储器芯片的存储容量为( 。

(A) 512B (B) 1KB (C) 2KB (D)4KB (E)8KB2.在待排序的数据表已经为有序时，以下排序算法中花费时刻反而多的是( 。

(A)堆排序 (B)希尔排序 (C)冒泡排序 (D)快速排序 (E)二分排序3.某数列有1000个各不相同的单元，由低至高按序排列，现要对该数列进行二分法检索，在最坏的情形下，需要检索( 单元。

(A)1000 (B)10 (C)100 (D)500 (E) 3004.已知数组a中，每一个元素a[i,j]在存储时要占3个字节，设i从1转变到8，j 从1转变到10，分派内存实是从地址sa开始持续按行存储分派的。

试问：a[5，8]的起始地址为( 。

(A)sa+141 (B)sa+180 (C)sa+222 (D)sa+225 (E)sa+1555.在pascal语言进程调历时，数值形参取得的是实际参数的( 。

(A) 数值 (B) 地址 (C)值 (D)变量 (E)以上都不是6.一个24*24点阵的汉字字形信息所占的字节数为( 。

(A) 2 (B) 8 (C) 24 (D) 32 (E) 727. 在微机系统中，最大体的输入输出模块BIOS寄存在( 中。

(A) RAM (B) ROM (C) 硬盘 (D)寄放器 (E)操纵器8. 十进制算术表达式:3*512+5*64+2*8+1的运算中,用二进制表示为( 。

(A)01 (B) (C) (D) (E)1110009.设栈S的初始状态为空,现对序列{1,2,3,4,5}在栈S上,依次进行如下操作(从元素1开始,出栈后再也不进栈):进栈,出栈,进栈,进栈,出栈,出栈。