下载文档原格式
2017年NOIP普及组第2题—图书管理员问题描述图书馆中每本书都有一个图书编码，可以用于快速检索图书，这个图书编码是一个正整数。
每位借书的读者手中有一个需求码，这个需求码也是一个正整数。
如果一本书的图书编码恰好以读者的需求码结尾，那么这本书就是这位读者所需要的。
小D刚刚当上图书馆的管理员，她知道图书馆里所有书的图书编码，她请你帮她写一个程序，对于每一位读者，求出他所需要的书中图书编码最小的那本书，如果没有他需要的书，请输出-1。
输入格式：第一行，包含两个正整数 n , q以一个空格分开，分别代表图书馆里书的数量和读者的数量。
接下来的 n行，每行包含一个正整数，代表图书馆里某本书的图书编码。
接下来的 q行，每行包含两个正整数，以一个空格分开，第一个正整数代表图书馆里读者的需求码的长度，第二个正整数代表读者的需求码。
输出格式：q行，每行包含一个整数，如果存在第 i个读者所需要的书，则在第 i行输出第 i个读者所需要的书中图书编码最小的那本书的图书编码，否则输出-1。
输入样例：5 5212311232324242 233 1233 1242 122 12输出样例：231123-1-1-1说明【数据规模与约定】对于 20%的数据，1 ≤ n ≤ 2。
另有 20%的数据，q = 1。
另有 20%的数据，所有读者的需求码的长度均为 1。
另有 20%的数据，所有的图书编码按从小到大的顺序给出。
对于 100%的数据，1 ≤ n ≤1,000,1 ≤ q ≤ 1,000，所有的图书编码和需求码均不超过 10,000,000。
问题分析：这道题是一个纯模拟题。
思路如下：要求对于每一位读者，求出他所需要的书中图书编码最小的那本书，所以我们可以先把图书编码进行从小到大的排序，方便查找。
定义变量k，k表示读者需求码的位数，(图书编码)%(10的k 次方)是求当前图书编码的后k位是多少，然后判断是否与当前读者需求码一致，如果相同，则输出该图书编码,接着判断下一个读者。
第十五届全国青少年信息学奥林匹克联赛初赛试题（普及组 C++语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一．单项选择题（共20题，每题1.5分，共计30分。
每题有且仅有一个正确答案。
）1、关于图灵机下面的说法哪个是正确的：A)图灵机是世界上最早的电子计算机。
B)由于大量使用磁带操作，图灵机运行速度很慢。
C)图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。
D)图灵机只是一个理论上的计算模型。
2、关于计算机内存下面的说法哪个是正确的：A)随机存储器（RAM）的意思是当程序运行时，每次具体分配给程序的内存位置是随机而不确定的。
B)1MB内存通常是指1024*1024字节大小的内存。
C)计算机内存严格说来包括主存（memory）、高速缓存（cache）和寄存器（register）三个部分。
D)一般内存中的数据即使在断电的情况下也能保留2个小时以上。
3、关于BIOS下面说法哪个是正确的：A)BIOS是计算机基本输入输出系统软件的简称。
B)BIOS里包含了键盘、鼠标、声卡、显卡、打印机等常用输入输出设备的驱动程序。
C)BIOS一般由操作系统厂商来开发完成。
D)BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。
4、关于CPU下面哪个说法是正确的：A)CPU全称为中央处理器（或中央处理单元）。
B)CPU可以直接运行汇编语言。
C)同样主频下，32位的CPU比16位的CPU运行速度快一倍。
D)CPU最早是由Intel公司发明的。
5、关于ASCII，下面哪个说法是正确的：A)ASCII码就是键盘上所有键的唯一编码。
B)一个ASCII码使用一个字节的内存空间就能够存放。
C)最新扩展的ASCII编码方案包含了汉字和其他欧洲语言的编码。
D)ASCII码是英国人主持制定并推广使用的。
6、下列软件中不是计算机操作系统的是：A) Windows B) Linux C) OS/2 D) WPS7、关于互联网，下面的说法哪一个是正确的：A)新一代互联网使用的IPv6标准是IPv5标准的升级与补充。
noip普及组初赛试题及答案一、选择题（每题5分，共50分）1. 在计算机科学中，以下哪个选项是数据结构中常用的数据类型？A. 整数B. 浮点数C. 字符串D. 所有选项答案：D2. 下列哪种排序算法的时间复杂度为O(nlogn)？A. 冒泡排序B. 插入排序C. 快速排序D. 选择排序答案：C3. 在C++中，以下哪个关键字用于声明一个类？A. structB. classC. enumD. union答案：B4. 在计算机编程中，以下哪个选项是递归算法的典型应用？A. 计算阶乘B. 打印输出C. 循环遍历D. 数据输入答案：A5. 在数据库管理系统中，SQL语言用于执行哪种类型的操作？A. 存储数据B. 检索数据C. 修改数据D. 所有选项答案：D6. 在计算机科学中，算法的时间复杂度通常用来描述什么？A. 算法的运行时间B. 算法的执行步骤C. 算法的内存使用量D. 算法的效率答案：D7. 在编程语言中，以下哪个选项不是控制结构？A. 条件语句B. 循环语句C. 函数定义D. 异常处理答案：C8. 在操作系统中，进程和线程的主要区别是什么？A. 进程是资源分配的单位，线程是执行的单位B. 进程是执行的单位，线程是资源分配的单位C. 进程和线程没有区别D. 进程和线程是同一种概念答案：A9. 在计算机网络中，HTTP协议通常用于什么？A. 文件传输B. 电子邮件传输C. 网页浏览D. 远程登录答案：C10. 以下哪种数据结构最适合实现一个不重复元素集合？A. 数组B. 链表C. 栈D. 哈希表答案：D二、填空题（每题5分，共30分）1. 在C++中，用于定义常量的关键字是________。
答案：const2. 一个算法的空间复杂度是指算法在执行过程中所需的________。
答案：存储空间3. 在数据结构中，________是一种可以存储多个数据元素的线性结构。
答案：数组4. 在计算机程序设计中，________是一种将复杂问题分解为更小、更易于管理的部分的方法。
noip普及组初赛试题及答案1.在8位二进制补码中，表示的数是十进制下的( )。
A。
43 B。
-85 C。
-43 D。
-842.计算机存储数据的基本单位是( )。
A。
bit B。
Byte C。
GB D。
KB3.下列协议中与电子邮件无关的是( )。
A。
POP3 B。
SMTP C。
WTO D。
IMAP4.分辨率为800x600、16位色的位图，存储图像信息所需的空间为( )。
A。
900KB B。
1200KB C。
2400KB D。
2880KB5.计算机应用的最早领域是( )。
A。
数值计算 B。
人工智能 C。
机器人 D。
过程控制6.下列不属于面向对象程序设计语言的是( )。
A。
C B。
C++ C。
Java D。
C#7.NOI的中文意思是( )。
A。
中国信息学联赛 B。
全国青少年信息学奥林匹克竞赛C。
中国青少年信息学奥林匹克竞赛 D。
XXX8.2017年10月1日是星期日，1999年10月1日是( )。
A。
星期三 B。
星期日 C。
星期五 D。
星期二9.甲、乙、丙三位同学选修课程，从4门课程中，甲选修2门，乙、丙各选修3门，则不同的选修方案共有( )种。
A。
36 B。
48 C。
96 D。
19210.设G是有n个结点、m条边(n ≤m)的连通图，必须删去G的( )条边，才能使得G变成一棵树。
A。
n-1 B。
m-n C。
m+n+1 D。
m+1-n11.对于给定的序列{ak}，我们把(i。
j)称为逆序对当且仅当i。
aj。
那么序列1.7.2.3.5.4的逆序对数为()个。
A。
4 B。
5 C。
6 D。
712.表达式a * (b + c) * d的后缀形式是()。
A。
abcd*+* B。
abc+*d* C。
a*bc+*d D。
b+c*a*d13.向一个栈顶指针为hs的链式栈中插入一个指针s指向的结点时，应执行( )。
A。
hs->next=s。
s->next=hs。
hs=s;B。
s->next=hs。
【NOIP2017普及组】棋盘题目描述有一个m×m的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的。
你现在要从棋盘的最左上角走到棋盘的最右下角。
任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的），你只能向上、下、左、右四个方向前进。
当你从一个格子走向另一个格子时，如果两个格子的颜色相同，那你不需要花费金币；如果不同，则你需要花费 1个金币。
另外，你可以花费 2 个金币施展魔法让下一个无色格子暂时变为你指定的颜色。
但这个魔法不能连续使用，而且这个魔法的持续时间很短，也就是说，如果你使用了这个魔法，走到了这个暂时有颜色的格子上，你就不能继续使用魔法；只有当你离开这个位置，走到一个本来就有颜色的格子上的时候，你才能继续使用这个魔法，而当你离开了这个位置（施展魔法使得变为有颜色的格子）时，这个格子恢复为无色。
现在你要从棋盘的最左上角，走到棋盘的最右下角，求花费的最少金币是多少？输入格式第一行包含两个正整数m,n以一个空格分开，分别代表棋盘的大小，棋盘上有颜色的格子的数量。
接下来的n行，每行三个正整数x,y,c分别表示坐标为(x,y)的格子有颜色c。
其中c=1代表黄色，c=0代表红色。
相邻两个数之间用一个空格隔开。
棋盘左上角的坐标为(1,1)，右下角的坐标为(m,m)。
棋盘上其余的格子都是无色。
保证棋盘的左上角，也就是(1,1)一定是有颜色的。
输出格式一个整数，表示花费的金币的最小值，如果无法到达，输出−1。
数据范围对于 30%的数据, 1≤m≤5,1≤n≤10。
对于 60%的数据, 1≤m≤20,1≤n≤200。
对于 100%的数据, 1≤m≤100,1≤n≤1,000。
题解这道题写起来还是挺有意思的。
我们根据题目不难得出要用一个二维数组来记录棋盘的状态。
我们更习惯于用0来表示没有或空，而不是用0表示红色，这只需要在输入的时候略处理一下即可（把0变成2）。
很明显是要从左上角做到右下角，花费尽可能少。
17届NOIP（C语言）普及组初赛试题一、单项选择题（共20题，每题1.5分，共计30分。
每题有且仅有一个正确选项。
）1．在二进制下，1101001 + （）= 1110110。
A. 1011B. 1101C. 1010D. 11112．字符“0”的ASCII码为48，则字符“9”的ASCII码为（）。
A. 39B. 57C. 120D. 视具体的计算机而定3．一片容量为8GB的SD卡能存储大约（）张大小为2MB的数码照片。
A. 1600 B. 2000 C. 4000 D. 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．有人认为，在个人电脑送修前，将文件放入回收站中就是已经将其删除了。
这种想法是（）。
A. 正确的，将文件放入回收站意味着彻底删除、无法恢复B. 不正确的，只有将回收站清空后，才意味着彻底删除、无法恢复C. 不正确的，即使将回收站清空，文件只是被标记为删除，仍可能通过恢复软件找回D. 不正确的，只要在硬盘上出现过的文件，永远不可能被彻底删除11．广度优先搜索时，需要用到的数据结构是（）。
第十六届全国青少年信息学奥林匹克联赛初赛试题（普及组C++语言两小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共20题，每题1.5分，共计30分。
每题有且仅有一个正确选项。
）1．2E+03表示（）。
A．2.03B．5C．8D．20002．一个字节（byte）由（）个二进制位组成。
A．8B．16C．32D．以上皆有可能3．以下逻辑表达式的值恒为真的是（）。
A．PV(?PΛQ)V(?PΛQ)B．QV(?PΛQ)V(PΛ?Q)C．PVQV(PΛ?Q)V(?PΛQ)D．PV?QV(PΛ?Q)V(?PΛ?Q)4．Linux下可执行文件的扩展名为（）。
A．exeB．comC．dllD．以上都不是5．如果树根算第1层，那么一棵n层的二叉树最多有（）个结点。
A．2n-1B．2n C．2n+1D．2n+16．提出“存储程序”的计算机原理的是（）。
A．克劳德·香农B．戈登·摩尔C．查尔斯·巴比奇D．冯·诺依曼7．设X、Y、Z分别代表三进制下的一位数字，若等式XY+ZX=XYX在三进制下成立，那么同样在三进制下，等式XY*ZX=()也成立。
A．YXZB．ZXYC．XYZD．XZY8．Pascal语言、C语言和C++语言都属于（）。
A．面向对象语言B．脚本语言C．解释性语言D．编译性语言9．前缀表达式“+3*2+512”的值是（)。
A．23B．25C．37D．6510．主存储器的存取速度比中央处理器（CPU）的工作速度慢得多，从而使得后者的效率受到影响。
而根据局部性原理，CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。
于是，为了提高系统的整体执行效率，在CPU中引入（）。
A．寄存器B．高速缓存C．闪存D．外存11．一个字长为8位的整数的补码是11111001，则它的原码是（）。
A．00000111B．01111001C．11111001D．1000011112．基于比较的排序时间复杂度的下限是（），其中n表示待排序的元素个数。
NOIP2017普及组初赛解析
纯原创+手打，求轻喷，如果觉得对你有帮助，点个赞吧，如果能打赏一下，你问我兹不兹瓷，我肯定是兹瓷的！
初步评价，整体来说，难度比2016增大了，倒并不是说题目思维难度加大很多，而是直接了当的题目少了一些，有10%左右分值的题目是有坑的，一不小心就错了。
基本结论：得分难度加大了，但是不能算是思维“非常难”级别。
如果心态平和，做完选择题之后，后面的题目都回归常规了，还是能够比较顺畅地解题，理论上应该得到比较理想的分数的。
今年无论是提高组还是普及组，数学味道都非常浓，计算机科学的基础学科是数学，所以我们要重视数学学科的学习，尤其是与计算机科学相关的组合数学、概率论、离散数学、数列等知识的学习，在OI中，这些知识与数奥的方向并不完全一致，所以对于普及组打基础的小朋友来说，没学过数奥的也不要方！。
第二十三届全国青少年信息学奥林匹克联赛初赛 普及组C++语言试题 竞赛时间： 2017 年 10 月 14 日 14:30~16:30
选手注意: •式题纸共有7页，答题纸共有 2页，满分100分。请在答题纸上作答，写在试题纸上 的一律无效。
•不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。
一、单项选择题（共 20题，每题1.5分，共计30分；每题有且仅有一个正确选项） 1•在8位二进制补码中，10101011表示的数是十进制下的（ ）。 A. 43 B. -85 C. -43 D. -84
2•计算机存储数据的基本单位是（ ）。 A. bit B. Byte C. GB D. KB
3•下列协议中与电子邮件无关的是（ ）。 A. POP3 B. SMTP C. WTO D. IMAP
4. 分辨率为800x600、16位色的位图，存储图像信息所需的空间为（ ）。
5. 计算机应用的最早领域是（）。 A.数值计算 B.人工智能 C.机器人
6. 下列不属于面向对象程序设计语言的是（ ）。 A. C B. C++ C. Java D. C#
7. NOI的中文意思是（）。 A.中国信息学联赛 B.全国青少年信息学奥林匹克竞赛 C.中国青少年信息学奥林匹克竞赛 D.中国计算机协会
8. 2017年10月1日是星期日，1999年10月1日是（）。 A.星期三 B.星期日 C.星期五 D.星期二
A. 937.5KB B. 4218.75KB C. 4320KB D. 2880KB D.过程控制 9•甲、乙、丙三位同学选修课程，从 4门课程中，甲选修 2门，乙、丙各选修 3门，则不 同的选修方案共有（）种。 A. 36 B. 48 C. 96 D. 192
10. 设G是有n个结点、m条边（n < m的连通图，必须删去 G的（）条边，才能使 得G变成一棵树。 A. m -n + 1 B. m - n C. m + n + 1 D. n -m + 1
11. 对于给定的序列｛ak｝，我们把（i, j）称为逆序对当且仅当 i < j且ai > aj。那么 序列1,7, 2, 3, 5, 4的逆序对数为（）个。 A. 4 B. 5 C. 6 D. 7
12. 表达式a * （b + c） * d的后缀形式是（）。 A. a b c d * + * B. a b c + * d * C. a * b c + * d D. b + c * a * d
13. 向一个栈顶指针为 hs的链式栈中插入一个指针 s指向的结点时，应执行（ ）。
A. hs->n ext = s; B. s->next = hs; hs = s; C. s->n ext = hs->n ext; hs->n ext = s; D. s->n ext = hs; hs = hs->n ext;
14. 若串S = “ copyright其子串的个数是（）。 A. 72 B. 45 C. 46 D. 36
15. 十进制小数13.375对应的二进制数是（）。 A. 1101.011 B. 1011.011 C. 1101.101 D. 1010.01
16.对于入栈顺序为 a, b, c, d, e, f, g的序列，下列（ ）不可能是合法的出栈序 列。
A. a, b, c, d, e, f, g B. a, d, c, b, e, g, f C. a, d, b, c, g, f, e D. g, f, e, d, c, b, a 17. 设A和B是两个长为n的有序数组，现在需要将 A和B合并成一个排好序的数组， 任何以元素比较作为基本运算的归并算法在最坏情况下至少要做（ ）次比较。
A.n2 B. n log n C. 2n D. 2n - 1
18. 从（）年开始，NOIP竞赛将不再支持 Pascal语言。 A. 2020 B.2021 C.2022 D.2023
19. 一家四口人，至少两个人生日属于同一月份的概率是（ ）（假定每个人生日属于每个月 份的概率相同且不同人之间相互独立） 。
A. 1/12 B. 1/144 C. 41/96 D. 3/4
20. 以下和计算机领域密切相关的奖项是（ ）。 A.奥斯卡奖 B.图灵奖 C.诺贝尔奖 D.普利策奖
二、问题求解（共 2题，每题5分，共计10分） 1. 一个人站在坐标（0, 0）处，面朝x轴正方向。第一轮，他向前走 1单位距离，然后右 转；第二轮，他向前走2单位距离，然后右转；第三轮，他向前走3单位距离，然后右转… 他一直这么走下去。请问第 2017轮后，他的坐标是：（ _____________________ , _________ ）。（请在答 题纸上用逗号隔开两空答案）
2. 如下图所示，共有 13个格子。对任何一个格子进行一次操作，会使得它自己以及与它上
下左右相邻的格子中的数字改变（由 1变0，或由0变1）。现在要使得所有的格子中的 数字都变为 0,至少需要 ____________ 次操作。
三、阅读程序写结果（共 4题，每题8分，共计32分） 1. # in elude using n amespace std; int main（） { int t[256]; string s; int i; cin >> s; for （i = 0; i < 256; i++） t[i] = 0; for （i = 0; i < s.le ngth（）; i++） t[s[i]]++; for (i = 0; i < s.length(); i++) if (t[s[i]] == 1) { cout << s[i] << en dl; retur n 0; } cout << "no" << en dl; retur n 0;
}
输入：xyzxyw 输出： _________
2. # in clude using n amespace std; int g(i nt m, int n, int x) { int ans = 0; int i; if (n == 1) return 1; for (i = x; i <= m / n; i++) ans += g(m - i, n - 1, i); retur n an s; } int main() { int t, m, n; cin >> m >> n; cout << g(m, n, 0) << en dl; retur n 0; }
输入：7 3 输出： _________
3. # in clude using n amespace std; int mai n() { string ch; int a[200]; int b[200]; int n, i, t, res; cin >> ch; n = ch.len gth(); for (i = 0; i < 200; i++) b[i] = 0; for (i = 1; i <= n; i++) { a[i] = ch[i - 1] - '0'; b[i] = b[i - 1] + a[i]; } res = b[n]; t = 0; for (i = n; i > 0; i--) { if (a[i] == 0) t++; if (b[i - 1] + t < res) res = b[i - 1] + t; } cout << res << en dl; retur n 0;
输入： 100110101100110110101111000
1 输出:
4. # in elude using n amespace std; int main() { int n, m; cin >> n >> m; int x = 1; int y = 1; int dx = 1; int dy = 1; int ent = 0; while (ent != 2) { ent = 0; x= x + dx; y= y + dy; if (x == 1 || x == n) { ++c nt; dx = -dx; } if (y == 1 || y == m) { ++c nt; dy = -dy; } } cout << x << " " << y << en dl; retur n 0;
}
输入 1: 4 3 输出 1: （3 分） 输入 2: 2017 1014
输出 2: （5分）
四、完善程序（共 2题，每题14分，共计28分） 1.（快速幕）请完善下面的程序，该程序使用分治法求 xp mod m的值。（第一空2分，其 余3分） 输入：三个不超过 10000的正整数 x, p, m。 输出：xp mod m 的值。
提示：若 p 为偶数，xp=(x2)p/2 ;若 p 为奇数，xp=x*(x2)(p-1)/2。 #in elude using n amespace std;
int x, p, m, i, result; int mai n() {
cin >> x >> p >> m; result = (1) 5
while ( (2) ){ if (p % 2 == =1)
result = (3) 5
p /= 2; x = (4) 5
} cout << (5) << en dl; return 0; }
2.(切割绳子)有 n 条绳子, 每条绳子的长度已知且均为正整数。绳子可以以任意正整数 长度切割，但不可以连接。现在要从这些绳子中切割出 m条长度相同的绳段，求绳段的最 大长度是多少。(第一、二空2.5分，其余3分)
输入：第一行是一个不超过 100的正整数n，第二行是n个不超过106的正整数，表示 每条绳子的长度，第三行是一个不超过 108的正整数 m。 输出：绳段的最大长度，若无法切割，输出 Failed。
#in clude using n amespace std; int n, m, i, lbo und, ubo und, mid, count; in t le n[ 100]; // 绳子长度
int main() { cin >> n; count = 0; for (i = 0; i < n; i++) { cin >> len [i]; (1) ;
