第五年全国青少年信息学(计算机)奥林匹克分区联赛普及组复赛试题

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

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

3、全国统一评测时采用的机器配置为：Intel(R) Core(TM) i7-****************，内存32GB。

上述时限以此配置为准。

4、只提供Linux格式附加样例文件。

5、特别提醒：评测在当前最新公布的NOI Linux下进行，各语言的编译器版本以其为准。

1. 标题统计(title.cpp/c/pas)【问题描述】凯凯刚写了一篇美妙的作文，请问这篇作文的标题中有多少个字符？注意：标题中可能包含大、小写英文字母、数字字符、空格和换行符。

统计标题字符数时，空格和换行符不计算在内。

【输入格式】输入文件名为title.in。

输入文件只有一行，一个字符串s。

【输出格式】输出文件名为title.out。

输出文件只有一行，包含一个整数，即作文标题的字符数（不含空格和换行符）。

见选手目录下的title/title1.in和title/title1.ans。

【输入输出样例1说明】标题中共有3个字符，这3个字符都是数字字符。

见选手目录下的title/title2.in和title/title2.ans。

【输入输出样例2说明】标题中共有5个字符，包括1个大写英文字母，1个小写英文字母和2个数字字符，还有1个空格。

由于空格不计入结果中，故标题的有效字符数为4个。

【数据规模与约定】规定|s|表示字符串s的长度（即字符串中的字符和空格数）。

对于40%的数据，1≤|s|≤5，保证输入为数字字符及行末换行符。

对于80%的数据，1≤|s|≤5，输入只可能包含大、小写英文字母、数字字符及行末换行符。

对于100%的数据，1≤|s|≤5，输入可能包含大、小写英文字母、数字字符、空格和行末换行符。

全国青少年信息学奥林匹克竞赛联赛试题大纲一、试题形式每次联赛的试题分四组：普及组初赛题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．信息技术的新发展、新特点、新应用等。

NOIP2002普及组解题报告题一：级数求和[问题描述]：：Sn=1+1/2+1/3+…+1/n。

显然对于任意一个整数K，当n足够大的时候，Sn大于K。

现给出一个整数K〔1<=K<=15〕，要求计算出一个最小的n，使得Sn>K[问题分析]：这道题目非常简单，题目的意思已经把该题的算法描述得再清楚不过了，初始时Sn=0,n=0,然后每次循环n←n+1,Sn←Sn+1/n,，直到Sn大于K，最后输出K。

另外实型(Real 是最慢的，建议用Extended)的运算速度不是很快，而K为1~15之间的整数，所以最后可以交一张表〔常量数组〕，以达到最好的效果[参考程序]：programc1;varK:Byte;n:Longint;Sn:Extended;beginReadln(K);Sn:=0;n:=0;RepeatInc(n);Sn:=Sn+1/n;UntilSn>k;Writeln(n);end.题二：选数[问题描述]：n〔1<=n<=20〕个整数x1,x2,…,xn〔1<=xi<=5000000〕，以及一个整数k〔k<n〕。

从n 个整数中任选k个整数相加，可分别得到一系列的和。

现在，要求你计算出和为素数共有多少种。

[问题分析]：此题动态规划无从下手，也无数学公式可寻，看来只能搜索〔组合的生成算法〕，其实1<=n<=20这个约束条件也暗示我们此题搜索是有希望的，组合的生成可用简单的DFS来实现，既搜索这k个整数在原数列中的位置，由于组合不同于排列，与这k个数的排列顺序无关，所以我们可以令a[I]<a[I+1]〔a[I]表示第I个数在原数列中的位置〕，这个组合生成算法的复杂度大约为C(n,k)，下面给出递归搜索算法的框架：接下来的问题就是判断素数，判断一个整数P(P>1)是否为素数最简单的方法就是看是否存在一个素数a(a<=sqrt(P))是P的约数，如果不存在，该数就为素数，由于在此题中1<=xi<=5000000,n<=20,所以要判断的数P不会超过100000000，sqrt(p)<=10000，因此，为了加快速度，我们可以用筛选法将2…10000之间的素数保存到一个数组里〔共1229个〕，这样速度估计将提高5~6倍。

复赛模拟试题一（3小时,满分400分）说明：1.严格按照题目所要求的格式进行输入、输出，否则严重影响得分。

2.题目测试数据有严格的时间限制5s，超时不得分。

3.输入文件格式不用判错;从输入文件读入数据，输入文件名在程序中从键盘读入，计算结果输出到屏幕。

4.程序完成后，要按指定的提交文件名编译成EXE文件，指定的文件名如下：问题A: 天使的起誓（TENSHI NO YUBIKILI）问题描述：TENSHI非常幸运的被选为掌管智慧之匙的天使。

在正式任职之前，她必须和其他新当选的天使一样，要宣誓。

宣誓仪式是每位天使各自表述自己的使命，她们的发言稿被放在N个呈圆形排列的宝盒中。

这些宝盒按顺时针方向被编上号码１、２、３……、N-1、N。

一开始天使们站在编号为N的宝盒旁。

她们各自手上都有一个数字，代表她们自己的发言稿所在的盒子是从１号盒子开始按顺时针方向的第几个。

例如：有７个盒子，那么如果TENSHI手上的数字为９，那么她的发言稿所在盒子就是第２个。

现在天使们开始按照自己手上的数字来找发言稿，先找到的就可以先发言。

TENSHI一下子就找到了，于是她最先上台宣誓：“我将带领大家开启NOI之门……”TENSHI宣誓结束以后，陆续有天使上台宣誓。

可以有一位天使找了好久都找不到她的发言稿，原来她手上的数字M非常大，她转了好久都找不到她想找的宝盒。

任务：请帮助这位天使找到她想找的宝盒的编号。

输入格式：输入文件有两行分别正整数N和M，其中N、M满足81000 2 ≤ N ≤ 10，2 ≤ M ≤ 10输出格式：文件只有一行即宝盒的编号样例一样例二问题B: 步步高升（Step by Step）问题描述：春节的时候TENSHI去逛花市。

她来到一个卖盆竹的摊位，看到一盆叫做“步步高升”的盆竹。

“步步高升，步步高升……”学习就是要一步一步来，不能急，要打好基础。

在稳固的基础上才谈得上步步高升！TENSHI若有所思。

她看到这盆东西好意头，于是想买下。

全国青少年信息学奥林匹克联赛初赛练习卷（八）(普及组PASCAL语言二小时完成)●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共10题，每题1.5分，共计15分。

每题有且仅有一个正确答案）1.微机内的存储器的地址是以（）编址的。

A．二进制位B．字长C．字节D．微处理器的型号2.下列诸因素中,对微机工作影响最小的是（）。

A．尘土B．噪声C．温度D．湿度3.在24*24 点阵的字库中，汉字“一”与“编”的字模占用字节数分别是（）。

A．32、32 B．32、72 C．72、72 D．72、324.计算机能直接执行的指令包括两部分，它们是（）。

A．源操作数与目标操作数B．操作码与操作数C．ASCII码与汉字代码D．数字与字符5.在微机中，通用寄存器的位数是（）。

A．8位B．16位C．计算机字长D．32位6.在计算机中，ASCII码是（）位二进制代码。

A．8 B．7 C．12 D．167.计算机中的数有浮点与定点数两种，其中用浮点数表示的数，通常由（）这两部分组成。

A．指数与基数B．尾数与小数C．阶码与尾数D．整数与小数8.启动计算机引导DOS是将操作系统（）。

A．从磁盘调入中央处理器B．从内存储器调入高速缓冲存储器C．从软盘调入硬盘D．从系统盘调入内存储器9.不同的计算机，其指令系统也不相同，这主要取决于（）。

A．所用的操作系统B．系统的总体结构C．所用的CPU D．所用的程序设计语言10.在有N个叶子节点的哈夫曼树中，其节点总数为（）。

A. 不确定B. 2N-1C. 2N+1D. 2N二、不定项选择题（共10题，每题1.5分，共计15分。

多选或少选均不得分）。

11.假设我们用d=（a1, a2, …, a5）来表示无向图G的5个顶点的度数，下面给出的哪（些）组d值合理（）。

A) {5，4，4，3，1} B) {4，2，2，1，1} C) {3，3，3，2，2}D) {5，4，3，2，1} E) {2，2，2，2，2}注意：一个顶点的度数不可能超过4；另外，所有顶点的度数之和应该是偶数。

第十一届全国青少年信息学奥林匹克联赛初赛试题（普及组pascal&C 语言二小时完成）●● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●由OIFans（）整理一．选择一个正确答案代码（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}，那么集合C B A ~ Ç Ç 为（）。

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. 以下哪个不是计算机的输出设备（）。

第十一届全国青少年信息学奥林匹克联赛初赛试题（普及组pascal&C 语言二小时完成）●● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●由OIFans（）整理一．选择一个正确答案代码（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}，那么集合C B A ~ Ç Ç 为（）。

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. 以下哪个不是计算机的输出设备（）。

第五届全国青少年信息学（计算机）奥林匹克分区联赛小学教育其他考试卷与考试题姓名:_____________ 年级:____________ 学号:______________【题目】辽宁赛区小学组初赛试卷 将下列英语单词或缩写在计算机知识中所代表的意义写在括弧中。

WINDOWS（___________________）DOS （___________________）CPU （___________________）CD-ROM （___________________）INTERNET （___________________）UCDOS （___________________）LOGO （___________________）CAI （_________l 请写出实现下列功能的DOS 命令。

列出磁盘文件目录（___________________）清屏幕（___________________）拷贝文件（___________________）删除文件（___________________）建立子目录（___________________）进入指定的子目录（___________________） 参考答案：, , , , , （本题2分）【题目】请写出你知道的计算机输入设备（三种）和输出设备（两种）。

输入设备：_________________________________________________________输出设备：______________________________________参考答案：, , , , （本题1分）【题目】计算机的信息存储容量的基本单位是字节，常用B 表示，还有千字节（KB ）、兆字节（MB ）、千兆字节（GB ）等单位（分别简称为：K 、M 、G ）。

这些单位也用来表示文件的大小。

请回答下列问题：一个文件的大小为：2K=___________________B一个硬盘的存储容量为：6.4G=___________________M一台计算机的内存为：16M=___________________K参考答案：, , （本题2分）【题目】写出能画出下列图形的命令组。