下载文档原格式
第二十四届全国青少年信息学奥林匹克联赛初赛普及组C++语言试题竞赛时间：2018年10月13日14:30~16:30选手注意：●试题纸共有7页，答题纸共有2页，满分100分。
请在答题纸上作答，写在试题纸上的一律无效。
●不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。
一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）1.以下哪一种设备属于输出设备：（）A.扫描仪B.键盘C.鼠标D.打印机解析：这是一道送分题，会就会，不会就不会。
所以选D。
2.下列四个不同进制的数中，与其它三项数值上不相等的是（）。
A.(269)16B.(617)10C.(1151)8D．(1001101011)2解析：这题考核的是进制转换。
（269）16=2*16^2+6*16^1+9*16^0=617，(1151)8=1*8^3+1* 8^2+5*8^1+1*8^0=617，而(1001101011)2=619。
所以选D。
3.1MB等于（）。
A.1000字节B.1024字节C.1000X1000字节D.1024X1024字节1KB=1024B1MB=1024KB解析：这题考核的是字节之间的转换。
1MB=1024KB=1024*1024B。
所以选D。
4.广域网的英文缩写是（）。
NB．WANC．MAND．LNA解析：这题是送命题，，会就会，不会就不会。
WAN全称为Wide Area Network。
所以选B。
5.中国计算机学会于（）年创办全国青少年计算机程序设计竞赛。
A.1983B.1984C.1985D.1986解析：这题是送命题，会就会，不会就不会。
NOI是全国青少年信息学奥林匹克竞赛(National Olympiad in Informatics)的简称。
NOI是国内包括港澳在内的省级代表队最高水平的大赛，自1984年至今，在国内包括香港、澳门组织竞赛活动。
所以选B。
6.如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、字母键A、字母键S、字母键D、字母键F的顺序循环按键，即CapsLock、A、S、D、F、CapsLock、A、S、D、F、……，屏幕上输出的第81个字符是字母（）。
全国青少年信息学奥林匹克竞赛联赛试题大纲一、试题形式每次联赛的试题分四组：普及组初赛题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．初赛内容及要求：2、复赛内容及要求：在初赛的内容上增加以下内容。
2023年全国中学生信息学奥赛试题及解析概述本文档为2023年全国中学生信息学奥赛试题及解析的内容。
试题及解析以下是2023年全国中学生信息学奥赛的部分试题及其解析：试题一问题描述：给定一个整数数组，找出其中和最大的连续子数组，并返回其和。
示例：输入：[-2,1,-3,4,-1,2,1,-5,4]输出：6解释：连续子数组 [4,-1,2,1] 的和最大，为 6。
解析：此问题可以使用动态规划的思想来解决。
定义一个变量`maxSum` 存储最大和，初始值为数组的第一个元素。
遍历数组，如果当前元素之前的子数组和为正数，则将当前元素加入子数组中，并更新 `maxSum` 的值。
如果当前元素之前的子数组和为负数，则将当前元素作为新的子数组的起点，并重新计算子数组的和。
遍历完成后，`maxSum` 即为所求的最大和。
试题二问题描述：给定一个字符串，找到最长的不含重复字符的子串的长度。
示例：输入：abcabcbb输出：3解释：最长的不含重复字符的子串是 "abc"，其长度为 3。
解析：此问题可以使用滑动窗口的思想来解决。
定义一个变量`maxLen` 存储最长子串的长度，一个哈希表 `charMap` 存储字符和其在字符串中的索引位置。
遍历字符串，当遇到重复字符时，更新滑动窗口的起点为重复字符的下一个位置，并更新 `charMap` 中重复字符的索引位置。
每次遍历都计算滑动窗口的长度，如果大于`maxLen` 则更新 `maxLen` 的值。
遍历完成后，`maxLen` 即为所求的最长子串的长度。
结论本文提供了2023年全国中学生信息学奥赛的部分试题及其解析，主要涵盖了动态规划和滑动窗口两种算法思想。
NOIP2018初赛普及组C++题目+解析二十四届全国青少年信息学奥林匹克联赛初赛——普及组一、单项选择题（共15 题，每题2 分，共计30 分；每题有且仅有一个正确选项）1. 以下哪一种设备属于输出设备：（）A. 扫描仪B. 键盘C. 鼠标D. 打印机答案:D解析:扫描仪是输出设备显而易见2. 下列四个不同进制的数中，与其它三项数值上不相等的是（）。
A. (269)16B. (617)10C. (1151)8D. (1001101011)2答案: D解析：都转成二进制，然后前3个都是1001101001，跟D不同3. 1MB 等于（）。
A. 1000 字节B. 1024 字节C. 1000 X 1000 字节D. 1024 X 1024 字节答案:D解析:1 M B = 1024 K B = 1024 ∗1024 B1MB=1024KB=1024*1024B1MB=1024KB=1024∗1024B 4. 广域网的英文缩写是（）。
B. WANC. MAND. LNA广域网（英语：Wide Area Network，缩写为WAN），又称广域网、外网、公网。
是连围从几十公里到几千公里，它能连接多个地区、城市和国家，或横跨几个洲并能提供远距LAN（Local Area Network (缩写:LAN)）局域网的覆盖范围一般是方圆几千米之内，其具备的安装便捷、成本节约、扩展方便等特点使其在各类办公室内运用广泛。
局域网可以实现全，能够有效地保护资料安全，保证局域网网络能够正常稳定的运行。
答案:B A是局域网C是城域网5. 中国计算机学会于（）年创办全国青少年计算机程序设计竞赛。
A. 1983B. 1984D. 1986答案:B6. 如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、字母键A、字母键S、字母键D、字母键F 的顺序循环按键，即CapsLock、A、S、D、F、CapsLock、A、S、D、F、……，屏幕上输出的第81 个字符是字母（）。
第十八届全国青少年信息学奥林匹克竞赛初赛普及组试题和参考答案一、单项选择题（共20题，每题1.5分，共计30分，每题有且仅有一个正确答案）1、计算机如果缺少（），将无法正常启动。
A、内存B、鼠标C、U盘D、摄像头2、（）是一种先进先出的线性表。
A、栈B、队列C、哈希表D、二叉树3、目前计算机芯片（集成电路）制造的主要原料是（），它是一种能从沙子中提炼出来的物质。
A、硅B、铜C、锗D、铝4、十六进制数9A在（）进制下是232。
A、四B、八C、十D、十二5、（）不属于操作系统。
A、WindowsB、DOSC、PhotoshopD、NOI Linux6、如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是（）。
A、ABCB、CBAC、ACBD、BAC7、目前个人电脑的（）市场占有率最靠前的厂商包括Intel、AMD等公司。
A、显示器B、CPUC、内存D、鼠标8、使用冒泡排序对序列进行升序排序，每执行一次交换操作将会减少1个逆序对，因此序列5、4、3、2、1需要进行（）次交换，才能完成冒泡排序。
A、0B、5C、10D、159、1946年诞生于美国宾夕法尼亚大学的ENIAC属于（）计算机。
A、电子管B、晶体管C、集成电路D、超大规模集成电路10、无论是TCP/IP模型，还是OSI模型，都可视为网络的分层模型，每个网络协议都可以被归为某一层中，如果用现实生活中的例子来比喻这些“层”，以下最恰当的是（）。
11、矢量图图形文件所占的存储空间较小，并且不论如何放大、缩小或旋转等都不会失真，是因为它（）A、记录了大量像素块的色彩值来表示图像B、用点、直线或多边形等基于数学方程的几何图元来表示图像C、每个像素点的颜色信息均用矢量表示D、把文件保存在互联网，采用在线浏览的方式查看图像12、如果一个栈初识时为空，且当前栈中的元素从栈底到栈顶依次为a、b、c，另有元素d已经出栈，则可能的入栈顺序是（）。
A、a、d、c、bB、b、a、c、dC、a、c、b、dD、d、a、b、c13、（）是主要用于显示网页服务器或者文件系统的HTML文件内容，并让用户和这些文件交互的一种软件。
NOIP普及组历届试题分析简介全国青少年信息学奥林匹克竞赛（National Olympiad in Informatics in Provinces，简称NOIP）是由教育部主管的我国重要的计算机竞赛之一，也是继数学、物理、化学等奥赛之后的第五个奥赛竞赛科目。
NOIP的目的是为了提高初、高中学生计算机编程能力，培养计算机及其应用等方面人才，推动计算机教学与应用的发展。
NOIP由普及组和提高组组成，普及组适合初学者，困难系数逐年递增，试题越来越难。
本文将以普及组历届试题为主，对试题进行分析，帮助初学者更好地掌握NOIP的难点和解题方法。
历届试题分析2021年2021年普及组共3道试题，分别为：•普及组-1：数论题目，给定两个数n和m，求出从1到n中可以被m整除的数的个数。
•普及组-2：暴力枚举题目，给定一个长度为n的整型数组a，请计算其中有多少个子序列满足其中的元素逆序对数量恰好等于k序列中逆序对数量的个数。
•普及组-3：贪心算法题目，有n个维度相同的矩形，每个矩形的左上和右下两个点坐标都已知，请问从这些矩形中能够组成的最大矩形的面积是多少。
，2021年的普及组试题难度适中，各个题目的知识点都不难掌握，但需要提高思维能力和编程能力。
2020年2020年普及组共3道试题，分别为：•普及组-1：模拟题目，给定一些操作，包括插入、删除、查询等操作，让我们实现对一个序列的操作。
•普及组-2：搜索算法题目，有n个物品和一个容量为v的背包，每个物品有重量w和价值c两个属性，要求将物品装入背包中，使得背包中物品的总价值最大，输出最大价值。
•普及组-3：排序算法题目，给定n个三元组(a,b,w)，要求将三元组按照a从小到大、b从小到大排序，如果a和b相等，则按照w从小到大排序。
，2020年的普及组试题相对较简单，难度偏低，但需要细致的思考和编程能力。
2019年2019年普及组共3道试题，分别为：•普及组-1：分支结构和循环结构的题目，输入一个字符串，输出字符串中包含的大写字母、小写字母、数字和空格的个数。
NOIP普及组初赛历年试题及答案求解题篇问题求解：每次共2题，每空5分，共计10分。
每题全部答对得 5 分，没有部分分。
注：答案在文末在NOIP初赛问题求解中，经常会遇到排列组合问题。
这一类问题不仅内容抽象，解法灵活，而且解题过程极易出现“重复”和“遗漏”的错误，这些错误甚至不容易检查出来，所以解题时要注意不断积累经验，总结解题规律。
解答排列组合问题，首先必须认真审题，明确是属于排列问题还是组合问题，或者属于排列与组合的混合问题，其次要抓住问题的本质特征，灵活运用基本原理和公式进行分析解答。
同时还要注意讲究一些策略和技巧，比如采用分类、分步、捆绑等方法，也可以借助表格、方程等工具，使一些看似复杂的问题迎刃而解。
NOIP2011-1. 每份考卷都有一个8位二进制序列号。
当且仅当一个序列号含有偶数个1时，它才是有效的。
例如，0000000、01010011都是有效的序列号，而11111110不是。
那么，有效的序列号共有______个。
NOIP2011-2. 定义字符串的基本操作为: 删除一个字符、插入一个字符和将一个字符修改成另外一个字符这三种操作。
将字符串A变成字符串B的最少操作步数，称为字符串A到字符串B的编辑距离。
字符串“ ABCDEFG ”到字符串“BADECG ”的编辑距离为_______。
NOIP2012-1. 如果平面上任取n 个整点(横纵坐标都是整数) ，其中一定存在两个点，它们连线的中点也是整点，那么n至少是_____。
NOIP2012-2. 在NOI期间，主办单位为了欢迎来自全国各地的选手，举行了盛大的晚宴。
在第十八桌，有5名大陆选手和5名港澳选手共同进膳。
为了增进交流，他们决定相隔就坐，即每个大陆选手左右相邻的都是港澳选手、每个港澳选手左右相邻的都是大陆选手。
那么，这一桌共有_____种不同的就坐方案。
注意：如果在两个方案中，每个选手左边相邻的选手均相同，则视为同一个方案。
NOIP2013-1. 7 个同学围坐一圈，要选2 个不相邻的作为代表，有_____种不同的选法。
第十八届全国青少年信息学奥林匹克联赛初赛（普及组Pascal语言试题）竞赛时间：2012年10月13日14:30~16:30选手注意·试题纸共有10页，答题纸共有2页，满分100分。
请在答题纸上作答，写在试题纸上一律无效。
·不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料一、单项选择题（共20题，每题1.5分，共计30分；每题且仅有一个正确选项）1. 计算机如果缺少（A），将无法正常启动。
A. 内存B. 鼠标C. U盘D. 摄像头2. （B ）是一种先进先出的线性表。
A. 栈B. 队列C. 哈希表（散列表）D. 二叉树解析：1.栈的定义(可参考：/course_ware/data_structure/web/zhanhuoduilie/zhanhuoduilie3.1.1.htm)栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。
(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。
(2)当表中没有元素时称为空栈。
(3)栈为后进先出（Last In First Out）的线性表，简称为LIFO表。
栈的修改是按后进先出的原则进行。
每次删除（退栈）的总是当前栈中"最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。
2.队列：定义：队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。
（1）允许删除的一端称为队头（Front）。
（2）允许插入的一端称为队尾（Rear）。
（3）当队列中没有元素时称为空队列。
（4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。
队列的修改是依先进先出的原则进行的。
新来的成员总是加入队尾（即不允许"加塞"），每次离开的成员总是队列头上的（不允许中途离队），即当前"最老的"成员离队。
第十届：1、一个家具公司生产桌子和椅子。
现有113个单位的木材。
每张桌子要使用20个单位的木材，售价是30元；每张椅子要用16个单位的木材，售价是20元。
使用已有的木材生产桌椅（不一定要用光木材）做多可以买__ __元钱。
2、75名儿童去游乐场玩。
他们可以骑旋转木马，坐滑行轨道，乘宇宙飞船。
已知其中20人这三种东西都玩过，55人至少．．玩过其中两种。
若每玩一样的费用为5元，游乐场总共收入700元，可知有___ __名儿童没有玩过其中任何一种。
第十一届：1. 将数组{32, 74, 25, 53, 28, 43, 86, 47}中的元素按从小到大的顺序排列，每次可以交换任意两个元素，最少需要交换_____次。
2. 有3 个课外小组：物理组，化学组和生物组。
今有张、王、李、赵、陈5 名同学，已知张、王为物理组成员，张、李、赵为化学组成员，李、赵、陈为生物组成员。
如果要在3 个小组中分别选出3 位组长，一位同学最多只能担任一个小组的组长，共有种_____选择方案。
第十二届：1．（寻找假币）现有80枚硬币，其中有一枚是假币，其重量稍轻，所有真币的重量都相同，如果使用不带砝码的天平称重，最少需要称几次，就可以找出假币？你还要指出第1次的称重方法。
请写出你的结果：_________________________________________________。
2．（取石子游戏）现有5堆石子,石子数依次为3，5，7，19，50，甲乙两人轮流从任一堆中任取（每次只能取自一堆，不能不取）, 取最后一颗石子的一方获胜。
甲先取，问甲有没有获胜策略（即无论乙怎样取，甲只要不失误，都能获胜）？如果有，甲第一步应该在哪一堆里取多少？请写出你的结果：_____________________________________。
第十三届：1．（子集划分）将n 个数{1，2，…，n}划分成r 个子集。
每个数都恰好属于一个子集，任何两个不同的子集没有共同的数，也没有空集。
信息学竞赛中问题求解常见题分析（四）（排列组合问题）一、知识点：1． 分类计数原理：做一件事情，完成它可以有n 类办法，在第一类办法中有m 1种不同的方法，在第二类办法中有m 2种不同的方法，……，在第n 类办法中有m n 。
种不同的方法，那么完成这件事共有N=m 1+m 2+…+m n 。
种不同的方法。
2． 分步计数原理：做一件事情，完成它需要分成n 个步骤，做第一步有m 1种不同的方法，做第二步有m 2种不同的方法，……，做第n 步有m n 种不同的方法，那么完成这件事有N=m 1*m 2*…m n 。
种不同的方法。
3． 排列的概念：从n 个不同元素中，任取m(m ≤n)个元素(这里的被取元素各不相同)，按照一定的顺序排成一列，叫做从n 个不同元素中取出m 个元素的一个排列。
4． 排列数的定义：从n 个不同元素中，任取m(m ≤n)个元素的所有排列的个数叫做从n 个元素中取出m 个元素的排列数，用符号m n A 表示。
5． 排列数公式：m n A =n(n-1)(n-2)…(n-m+1)(m ，n ∈N ，m ≤n)6． 阶乘：n!表示正整数l 到n 的连乘积，叫做n 的阶乘规定0!=l 。
7． 排列数的另一个计算公式：)!(!m n n A m n -= 8． 组合的概念：一般地，从n 个不同元素中取出m(m ≤n)个元素并成一组，叫做从n 个不同元素中取出m 个元素的一个组合．9． 组合数的概念：从n 个不同元素中取出m(m ≤n)个元素的所有组合的个数，叫做从n 个不同元素中取出m 个元素的组合数．用符号m n C 表示．10．组合数公式：!)1)...(2)(1(m m n n n n A A C m m m n m n+---==，或)!(!!m n m n C m n -= (n ，m ∈N ，且m ≤n) 11．组合数的性质1：m n n m n C C -=，规定：0n C ：=1； 2：11-++=m nm n m n C C C 。
第十八届全国青少年信息学奥林匹克联赛初赛（普及组Pascal语言试题）竞赛时间：2012年10月13日14:30~16:30选手注意·试题纸共有10页，答题纸共有2页，满分100分。
请在答题纸上作答，写在试题纸上一律无效。
·不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料一、单项选择题（共20题，每题1.5分，共计30分；每题且仅有一个正确选项）1. 计算机如果缺少（），将无法正常启动。
A. 内存B. 鼠标C. U盘D. 摄像头2. （）是一种先进先出的线性表。
A. 栈B. 队列C. 哈希表（散列表）D. 二叉树3. 目前计算机芯片（集成电路）制造的主要原料是（），它是一种可以在沙子中提炼出的物质。
A. 硅B. 铜C. 锗D. 铝4. 十六进制数9A在（）进制下是232.A. 四B. 八C. 十D. 十二5.（）不属于操作系统。
A. WindowsB. DOSC. PhotoshopD. NOI Linux6. 如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是（）。
A. ABCB. CBAC. ACBD. BAC7. 目前个人电脑的（）市场占有率最靠前的厂商包括Intel、AMD等公司。
A. 显示器B. CPUC. 内存D. 鼠标8. 使用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会减少1个逆序对，因此序列5,4,3,2,1需要执行（）次操作，才能完成冒泡排序。
A. 0B. 5C. 10D. 159. 1946年诞生于美国宾夕法尼亚大学的ENIAC属于（）计算机。
A. 电子管B. 晶体管C. 集成电路D. 超大规模集成电路10. 无论是TCP/IP模型还是OSI模型，都可以视为网络的分层模型，每个网络协议都会被归入某一层中。
如果用现实生活中的例子来比喻这些“层”，以下最恰当的是（）。
A. 中国公司的经理与波兰公司的经理交互商业文件B. 军队发布命令C. 国际会议中，每个人都与他国地位对等的人直接进行会谈D. 体育比赛中，每一级比赛的优胜者晋级上一级比赛11.矢量图（Vector Image）图形文件所占的贮存空间比较小，并且无论如何放大、缩小或旋转等都不会失真，是因为它（）。
历届“问题求解”解析（2013竞赛辅导）问题求解是信息学竞赛初赛中常见题型，它共两题，每题5分，共10分，十六届增加了比重，有三题，占15分。
诸如寻找假币、博弈原理、抽屉原理、容斥问题、排列组合、逻辑推理、递推关系等问题出现在问题求解中。
（相关问题的具体讲解根据需要考虑发讲义） 第一届（逻辑推理问题）1. 有标号为A 、B 、C 、D 和1、2、3、4的8个球，每两个球装一盒，分装4盒。
标号为字母的球与标号为数字的球有着某种一一对应的关系（称为匹配），并已知如下条件： ① 匹配的两个球不能在一个盒子内。
② 2号匹配的球与1号球在一个盒子里。
③ A 号和2号球在一个盒子里。
④ B 匹配的球和C 号球在一个盒子里。
⑤ 3号匹配的球与A 号匹配的球在一个盒子里。
⑥ 4号是A 或B 号球的匹配球。
⑦ D 号与1号或2号球匹配。
请写出这四对球匹配的情况。
第四届（递推、树、图）1. 已知一个数列U 1，U 2，U 3，…，U N ，… 往往可以找到一个最小的K 值和K 个数a 1，a 2，…,a n 使得数列从某项开始都满足： U N+K =a 1U N+K-1+a 2U N+K-2+……+a k U N (A)例如对斐波拉契数列1，1，2，3，5，…可以发现：当K=2，a 1 =1，a 2 =1时，从第3项起（即N>=1）都满足U n+2 =U n+1+U n 。
试对数列13，23，33，…，n 3,…求K 和a 1,a 2, …,a K 使得（A ）式成立。
当K= 4，a 1,a 2,…,a k 为a 1=4, a 2=6, a 3=4，a 4=-1对数列132333,…,n 3,…（A ）成立。
2．给出一棵二叉树的中序遍历：DBGEACHFI 与后序遍历：DGEBHIFCA 画出此二叉树。
3．用邻接矩阵表示下面的无向图：表示该无向图的邻接矩阵为 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0第五届（递推）将Ln 定义为求在一个平面中用n 条直线所能确定的最大区域数目。
第十八届全国青少年信息学奥林匹克联赛初赛（普及组C++语言试题）竞赛时间：2012年10月13日14:30~16:30选手注意：试题纸共有10页，答题纸共有2页，满分100分。
请在答题纸上作答，写在试题纸上一律无效。
不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料一、单项选择题（共20题，每题分，共计30分；每题且仅有一个正确选项）1．计算机如果缺少（），将无法正常启动。
A．内存B．鼠标C． U盘D．摄像头2．（）是一种先进先出的线性表。
A．栈B．队列C．哈希表（散列表） D．二叉树3．目前计算机芯片（集成电路）制造的主要原料是（），它是一种可以在沙子中提炼出的物质。
A．硅B．铜C．锗D．铝4．十六进制数9A在（）进制下是232。
A．四B．八C．十D．十二5．（）不属于操作系统。
A．Windows B．DOS C．Photoshop D．NOI Linux6．如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是（）。
A．ABC B．CBA C．ACB D．BAC7．目前个人电脑的（）市场占有率最靠前的厂商包括Intel、AMD等公司。
A．显示器B．CPU C．内存D．鼠标8．使用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会减少1个逆序对，因此序列 5，4，3，2，1需要执行（）次操作，才能完成冒泡排序。
A．0 B．5 C．10 D．159． 1946年诞生于美国宾夕法尼亚大学的ENIAC属于（）计算机。
A．电子管B．晶体管C．集成电路D．超大规模集成电路10．无论是TCP/IP模型还是OSI模型，都可以视为网络的分层模型，每个网络协议都会被归入某一层中。
如果用现实生活中的例子来比喻这些“层”，以下最恰当的是（）。
A．中国公司的经理与波兰公司的经理交互商业文件B．军队发布命令C．国际会议中，每个人都与他国地位对等的人直接进行会谈D．体育比赛中，每一级比赛的优胜者晋级上一级比赛11．矢量图（Vector Image）图形文件所占的贮存空间比较小，并且无论如何放大、缩小或旋转等都不会失真，是因为它（）。
第十八届全国青少年信息学奥林匹克联赛初赛（普及组C++语言试题）竞赛时间：2012年10月13日14:30~16:30选手注意：●试题纸共有10页，答题纸共有2页，满分100分。
请在答题纸上作答，写在试题纸上一律无效。
●不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料一、单项选择题（共20题，每题1.5分，共计30分；每题且仅有一个正确选项）1．计算机如果缺少（），将无法正常启动。
A．内存B．鼠标C．U盘D．摄像头2．（）是一种先进先出的线性表。
A．栈B．队列C．哈希表（散列表）D．二叉树3．目前计算机芯片（集成电路）制造的主要原料是（），它是一种可以在沙子中提炼出的物质。
A．硅B．铜C．锗D．铝4．十六进制数9A在（）进制下是232。
A．四B．八C．十D．十二5．（）不属于操作系统。
A．Windows B．DOS C．Photoshop D．NOILinux6．如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是（）。
A．ABC B．CBA C．ACB D．BAC7．目前个人电脑的（）市场占有率最靠前的厂商包括Intel、AMD等公司。
A．显示器B．CPU C．内存D．鼠标8．使用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会减少1个逆序对，因此序列5，4，3，2，1需要执行（）次操作，才能完成冒泡排序。
A．0 B．5 C．10 D．159．1946年诞生于美国宾夕法尼亚大学的ENIAC属于（）计算机。
A．电子管B．晶体管C．集成电路D．超大规模集成电路10．无论是TCP/IP模型还是OSI模型，都可以视为网络的分层模型，每个网络协议都会被归入某一层中。
如果用现实生活中的例子来比喻这些“层”，以下最恰当的是（）。
A．中国公司的经理与波兰公司的经理交互商业文件B．军队发布命令C．国际会议中，每个人都与他国地位对等的人直接进行会谈D．体育比赛中，每一级比赛的优胜者晋级上一级比赛11．矢量图（VectorImage）图形文件所占的贮存空间比较小，并且无论如何放大、缩小或旋转等都不会失真，是因为它（）。
历届“问题求解”解析（2013竞赛辅导）问题求解是信息学竞赛初赛中常见题型，它共两题，每题5分，共10分，十六届增加了比重，有三题，占15分。
诸如寻找假币、博弈原理、抽屉原理、容斥问题、排列组合、逻辑推理、递推关系等问题出现在问题求解中。
（相关问题的具体讲解根据需要考虑发讲义） 第一届（逻辑推理问题）1. 有标号为A 、B 、C 、D 和1、2、3、4的8个球，每两个球装一盒，分装4盒。
标号为字母的球与标号为数字的球有着某种一一对应的关系（称为匹配），并已知如下条件： ① 匹配的两个球不能在一个盒子内。
② 2号匹配的球与1号球在一个盒子里。
③ A 号和2号球在一个盒子里。
④ B 匹配的球和C 号球在一个盒子里。
⑤ 3号匹配的球与A 号匹配的球在一个盒子里。
⑥ 4号是A 或B 号球的匹配球。
⑦ D 号与1号或2号球匹配。
请写出这四对球匹配的情况。
第四届（递推、树、图）1. 已知一个数列U 1，U 2，U 3，…，U N ，… 往往可以找到一个最小的K 值和K 个数a 1，a 2，…,a n 使得数列从某项开始都满足： U N+K =a 1U N+K-1+a 2U N+K-2+……+a k U N (A)例如对斐波拉契数列1，1，2，3，5，…可以发现：当K=2，a 1 =1，a 2 =1时，从第3项起（即N>=1）都满足U n+2 =U n+1+U n 。
试对数列13，23，33，…，n 3,…求K 和a 1,a 2, …,a K 使得（A ）式成立。
当K= 4，a 1,a 2,…,a k 为a 1=4, a 2=6, a 3=4，a 4=-1对数列132333,…,n 3,…（A ）成立。
2．给出一棵二叉树的中序遍历：DBGEACHFI 与后序遍历：DGEBHIFCA 画出此二叉树。
3．用邻接矩阵表示下面的无向图：表示该无向图的邻接矩阵为 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0第五届（递推）将Ln 定义为求在一个平面中用n 条直线所能确定的最大区域数目。
例如：当n=1时，L1=2,进一步考虑，用n 条折成角的直线（角度任意），放在平面上，能确定的最大区域数目Zn 是多少？例如：当n=1时，Z1=2（如下图所示）当给出n 后，请写出以下的表达式：Ln = ______________ 2、Zn = _______________ 答案为：Ln=n(n+1)/2+1(n ≥0) Zn=L2n-2n=2n2-n+1解析：本题实质是求直线或折线将一个平面分成的最大区域数，从两个方面考虑： （1）求在一个平面中用n 条直线所能确定的最大区域数； n=1,L1=2, F(1)=2n=2,L2=4, F(2)=F(1)+2 n=3,L3=7, F(3)=F(2)+3 n=4,L4=11, F(4)=F(3)+4 ……所以， F(n)=F(n-1)+n把上面的n 个等式左右相加，化简得出：F （n ）=2+2+3+4+……+n 即：L （n ）=n*(n+1)/2+1A B C D 4 3 1 2 A C B D E F G H I（2）求在一个平面中用n条折线所能确定的最大区域数；n=1,Z1=2, F(1)=0+2n=2,Z2=7, F(2)=1*(2*2-1)+4n=3,Z3=16, F(3)=2*(2*3-1)+6n=4,Z4=29, F(4)=3*(2*4-1)+8……所以，F(n)=(n-1)*(2*n-1)+2*n即：Z（n）=(n-1)*(2*n-1)+2*n 几何+归纳+组合数学！第六届（树与递推）1.已知，按中序遍历二叉树的结果为：abc问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。
有5种不同形态的二叉树可以得到这一遍历结果; 可画出的这些二叉树为:①a ②b ③ a ④ c ⑤ c\ / \ \ / /b ac c a b\ / \ /c b b a2.设有一个共有n级的楼梯，某人每步可走1级，也可走2级，也可走3级，用递推公式给出某人从底层开始走完全部楼梯的走法。
例如：当n=3时，共有4种走法，即1+1+1，1+2，2+1，3。
答案：F(n)=f(n-1)+f(n-2)+f(n-3) n>=4; F(1)=1; f(2)=2; f(3)=4;解析：两种方法，一是“猜”+“凑”，从具体的n=1,2,3……算起，只能算比较简单的，容易错；二是用组合数学和归纳法进行推导，一般先假设F（n）= a*F（n-1）+b*F（n-2）+c*F（n-3）+……，然后算a，b，c……直到某个系数=0就结束，再代入式子中。
F（1）＝1F（2）＝2 F（3）＝4F（N）＝F（N－3）＋F（N－2）＋F（N－1）（N≥4）推导：对于n级楼梯，可以有下面几种走法：1. 最后走一级，则有f(n-1)种2. 最后走两级，则有f(n-2)种3. 最后走三级，则有f(n-3)种第七届（树与排列组合）1.已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：CBGEAFHDIJ与CGEBHFJIDA则该二叉树的先序遍历的顺序为：ABCEGDFHIJ2.平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。
问用这些点为顶点，能组成多少个不同四边形？C(7,2)*(5+6)+C(5,2)*(7+6)+C(6,2)*(7+5)+7*6*5=21*11+10*13+15*12+210=231+130+180+210=751第八届（排列与递推）1.在书架上放有编号为1 ，2 ，．．．，n的n本书。
现将n本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来的位置上。
例如：n = 3时：原来位置为：1 2 3放回去时只能为：3 1 2 或 2 3 1 这两种问题：求当n = 5时满足以上条件的放法共有多少种？（不用列出每种放法）解法一：c(5,0)*5!-c(5,1)*4!+c(5,2)*3!-c(5,3)*2!+c(5,4)*1!-c(5,5)*0!=60-20+5-1=44解法二：n封装入n个信封时全部装错的装法总数为⎪⎭⎫⎝⎛-+-+-!1)1(!21!111!nn n。
通常称为伯努利一欧拉错装信封问题，又称为乱序排列，即把n个元素的排列a1，a2，L，an重新排列，使每个元素都不在原来的位置上的排列问题。
因此只要你代入公式就行2．设有一棵k叉树，其中只有度为0和k两种结点，设n 0 ，n k ，分别表示度为0和度为k的结点个数，试求出n 0 和n k之间的关系（n 0 = 数学表达式，数学表达式仅含n k 、k和数字）。
n0和nk之间的关系为：n0=(k-1) nk+1。
第九届（图与集合）1．无向图G有16条边，有3个4度顶点、4个3度顶点，其余顶点的度均小于3，则G至少11个顶点。
2. 某年级学生共选修6门课程，期末考试前，必须提前将这6门课程考完，每人每天只在下午至多考一门课程，设6门课程为C1，C2，C3，C4，C5，C6，S(Ci)为学习Ci 的学生集合。
已知S(Ci)∩S(C6)≠ф，i=1，2，...，5，S(Ci)∩S(Ci+1)≠ф，i=1，2，3，4，S(C5)∩S(C1)≠ф，问至少安排_4__天才能考完这6门课程。
第十届(递推)1. 75名儿童到游乐场去玩。
他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。
已知其中20人这三种东西都玩过，55人至少玩过其中的两种。
若每样乘坐一次的费用是5元，游乐场总共收入700，可知有名儿童没有玩过其中任何一种。
设a1,a2,a3分别是仅仅玩过一种游戏的人数，仅仅玩过2种游戏的人数，仅仅玩过三种的人数。
因此有a2+a3 = 55, a3=20, a1+2*a2+3*a3= 700/5;==>a1= 10所以结果就是75-a1-a2-a3=10名2. 已知a, b, c, d, e, f, g七个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲意大利语和德语；f会讲俄语、日语和法语；g会讲德语和法语。
能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？如果可以，请以“a b”开头写出你的安排方案：abdfgec第十一届（排序与最火柴）1. 将数组{32, 74, 25, 53, 28, 43, 86, 47}中的元素按从小到大的顺序排列，每次可以交换任意两个元素，最少需要交换次。
思路一：用直接选择排序实现：25,74,32,53,28,43,86,47 第一次：32<-->2525,28,32,53,74,43,86,47 第二次: 28<-->7425,28,32,43,74,53,86,47 第三次：43<-->55325,28,32,43,47,53,86,74 第五次：47-->7425,28,32,43,47,53,74,86 第五次：74<-->86思路二：首先排序给每个数字标上序号{32，74，25，53，28，43，86，47}{3 ，7 ，1 ，6 ，2 ，4 ，8 ，5 }再和标准序列{1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 }比较找出其中所有的"环" ，这里的"环"就是指它们互相交换之后能成为标准序列的最小集合比如这里{1,3}是一个"环", {7,2,5,8}是一个"环"。
具体找法很简单首先确定一个不在已找出"环"中的数字。
例如第一次从3开始,3对应标准序列的1 再找1对应的标准序列3 3回到了开始的数字那么这个环就是{1，3}第二次从7开始，7->2 2->5 5->8 8->7 所以第二个环是{7，2，5，8} 第三个环是{6,4} 这样所有的数字都在环中了交换的次数=（环中数字总数-环数）=8-3=52.一堆火柴有N根，A、B两人轮流取出。
每人每次可以取1 根或2 根，最先没有火柴可取的人为败方，另一方为胜方。
如果先取者有必胜策略则记为1，先取者没有必胜策略记为0。
当N 分别为100，200，300，400，500 时，先取者有无必胜策略的标记顺序为（回答应为一个由0 和/或1 组成的字符串）。
答案：11011规律：每次可以取1..m 根火柴(n 为正整数，且1<=m<N) 则 N=k(m+1) 后手胜，N ！=k(m+1)先手胜(k 为正整数)，N=3k 后手胜和 N ！=3k 先手胜(k 为正整数)补：(取石子游戏)现有5堆石子,石子数依次为3,5,7,19,50,甲乙两人轮流从任一堆中任取(每次只能取自一堆,不能不取),取最后一颗石子的一方获胜.甲先取,问甲有没有获胜策略(即无论乙怎样取,甲只要不失误,都能获胜) 如果有,甲第一步应该在哪一堆里取多少 请写出你的结果。
