下载文档原格式
NOIP2008信息奥赛提高组试题与答案（Pascal语言）第14届信息学奥赛试题单项选择1. 在以下各项中，（）不是操作系统软件。
A．Solaris B.Linux C.Sybase D.Windows Vista E.Symbian2. 微型计算机中，控制器的基本功能是（）。
A. 控制机器的各个部件协调工作B.实现算数运算与逻辑运算C.存储各种控制信息D. 获取外部信息E.存放程序和数据3. 设字符串S=“Olympic”,S的非空字串的数目是（）。
A.29B.28C.16D.17E.74. 完全2叉树有2*N-1的结点，则它的叶子结点数目是（）。
A.N-1B.2*NC.ND.2^N-1E.N/25. 将数组{8，23，4，16，77，-5，53，100}中元素从大到小按顺序排序，每次可以交换任意两个元素，最少要交换（）次。
A.4B.5C.6D.7E.86.设栈S的初始状态为空，元素a,b,c,d,e,f依次入栈，出栈顺序为b,d,c,f,e,a那么栈容量至少该是（）A.6B.5C.4D.3E.27.与十进制数28.5625相等的四进制数是（）A.123.21B.131.22C.130.22D.130.21E.130.208.递归过程和函数调用时，处理参数和返回地址，通常使用一种称为（）的数据结构。
A.队列B.多维数组C.线性表D.链表E.栈9.TCP/IP 是一组构成互联网基础的网络协议，字面上包括两组协议：传输控制协议（TCP）和网际互联协议（IP）。
TCP/IP协议把Internet网络系统描述成具有4个层次功能的网络模型，其中提供源节点和目的节点之间的信息传输服务，包括寻址和路由器选择等功能的是（）。
A.链路层B.网络层C.传输层D.应用层E.会话层10.对有序数组{5,13,19,21,37,56,64,75,88,92,100}进行二分查找，等概率情况下，查找成功的平均查找长度（平均比较次数）是（）。
历年NOIP选题题解汇总 联赛前上vijos板刷往年联赛题，使⽤在线编辑编写代码，祝我rp++。
废话不多说，挑⽐较有意思的记⼀下。
题⽬是按照年份排序的，最早只到了03年。
有些题⽬因为我还没写/很早之前写的忘了所以就没写题解。
NOIP2003 神经⽹络：按照题⽬怎么说怎么做，BFS即可。
注意输出层是指出度为0的层，不是指深度最⼤的。
传染病防治：爆搜题，枚举每⼀层减掉哪个。
复杂度不可算，理论在O(2^30*8!)左右，但好像强势不满。
想了⼀会貌似卡不掉？ NOIP2004 ⾍⾷算：知⼆推三，边搜边判。
NOIP2005 篝⽕晚会：⾸先你得知道两个排列可以看成若⼲个环，⽽且每个点只要转⼀次就可以转出来……⽽这题正好是两个排列的形式，即找到⼀个1-n的环和原环匹配最多就是不要动的⼈。
把每个⼈在环中的1的位置记下来取最多的就好了。
过河：把边权>=100的缩成100，因为长度过长没有意义，⼤于100了前⾯的情况必然可以凑出来，然后在1000下暴⼒DP即可。
注意特判S=T的情况，还有不要以为给出的点都在L内。
等价表达式：随便找⼏个数字(1~20)带进去算在模意义下都相等就可以了(跟解⽅程的思想有点像？)，重点是化为后缀表达式处理的trick。
NOIP2006 2^k进制数：⼤整数组合数。
NOIP2007 先坑着 NOIP2008 传纸条：显然的⽹络流，其实化为四维DP可做。
双栈排序：若存在i<j且A[i]>A[j]，即A[j]在A[i]前⾯弹栈。
因为A[i]最终也要出栈，所以⽐A[i]还要⼤的、在[i,j]中间的⼀定不能和A[i]在同⼀个栈中，即构成⼆分图。
判断有解就是⼆分图染⾊。
输出……反正我铁定WA的输出因为数据⽔过去了，不予置评。
NOIP2009 Hankson的趣味题：醉题，复杂度O(nsqrt(B)logB)但是跑得过？反正我是不会什么更好的解法…… 最优贸易：SPFA求出从1出发能买进的最低阶，从n出发沿反向边能卖出的最⾼价，最后枚举边减掉就好了。
NOIP1995年复赛试题1. 设有下列的算式：求出□中的数字，并打印出完整的算式来。
8 0 9 ------------- □□) □□□□ □□------------- □□□ □□□ ------------- 12. 方阵填数：在一个N ⨯N 的方阵中，填入1，2，……N ⨯N 个数，并要求构成如下的格式： 例：3. 若将一个正整数化为二进制数，在此二进制数中，我们将数字1的个数多于数字0的个数的这类二进制数称为A 类数，否则就称其为B 类数。
例如：（13）10=（1101）2 其中1的个数为3，0的个数为1，则称此数为A 类数； （10）10=（1010）2 其中1的个数为2，0的个数也为2，称此数为B 类数； （24）10=（11000）2 其中1的个数为2，0的个数为3，则称此数为B 类数； 程序要求：求出1～1000之中（包括1与1000），全部A 、B 两类数的个数。
4.编码问题：设有一个数组A:ARRAY[0..N-1] OF INTEGER ；数组中存放的元素为0～N-1之间的整数，且A[i]≠A[j]（当i ≠j 时）。
例如：N=6时，有： A=（4，3，0，5，1，2） 此时，数组A 的编码定义如下： A[0]的编码为0；A[i]的编码为：在A[0]，A[1]，……A[i-1]中比A[i]的值小的个数（i=1，2……N-1） ∴上面数组A 的编码为：B=（0，0，0，3，1，2）程序要求解决以下问题：给出数组A 后，求出其编码；给出数组A 的编码后，求出A 中的原数据。
5. 灯的排列问题：设在一排上有N 个格子（N ≤20），若在格子中放置有不同颜色的灯，每种灯的个数记为N 1，N 2，……N k （k 表示不同颜色灯的个数）。
放灯时要遵守下列规则：同一种颜色的灯不能分开；不同颜色的灯之间至少要有一个空位置。
例如：N=8（格子数） R=2（红灯数） B=3（蓝灯数） 放置的方法有：N=513 14 15 16 1 12 23 24 17 2 11 22 25 18 3 10 21 20 19 4 9 8 7 6 5N=616 17 18 19 20 1 153****221214 29 36 33 22 3 132****423412 27 26 25 24 5 11 10 9 8 7 6B-R 顺序放置的总数为12种。
NOI’95 “同创杯”全国青少年信息学（计算机）奥林匹克竞赛分区联赛初赛试题（初中组）竞赛用时：2小时一、基础题：<1> 执行①C>DIR 命令后，屏幕上显示如下画面：FORMAT COM 12145SYS COM 4878PUC BAT 126XCOPY EXE 112164 FILE（S）123456 bytes free接着又顺序执行了如下几条DOS 命令：②C>DIR> DF.TXT //表示将列表显示的目录作为文件写盘//①C>TYPE DF.TXT②C>DIR试问:执行命令③和④在屏幕上显示的结果是否与①相同?<2> 请将以下程序段表示的计算公式写出来（假设X的值已给出）E：=1 ；A：=1 ；FOR N：=1 TO 10 DOA：=A*X/N ；E：=E+A ；ENDFOR ；写出所表示的公式。
<3> 列举一个算法，使算法的解能对应相应的问题。
例如，设问题为：学生答题，答对一题可得10分，答错一题则要扣去5分，输入答对的题数（M）与答错的题数（N），求最后得分（S）是多少？列举出相应算法为：X：=10；Y：=5；READ（M，N）；S：=X*M-Y*N；现有以下问题：用五角钱换成5分、2分与1分的硬币，可有多少种换法？请列出该问题的算法。
<4> 已知如下N*(N+1)/2个数据，按行的顺序存入数组A[1]，A[2]，……中：a11a21a22a31a32a33……a n1a n2a n3……a nn其中：第一个下标表示行第二个下标表示列。
若：a ij(i≥j,j,i=1,2,……n)存贮在A[k]中，试问：（1）k和i，j之间的关系如何表示？（2）给定k值（k≤n*(n+1)/2)后，写出能决定相应的i，j值的算法。
<5> 有红、黄、黑、白四色球各一个，放置在一个内存编号为1、2、3、4四个格子的盒中，每个格子放置一只球，它们的顺序不知。
第十四届全国青少年信息学奥林匹克联赛初赛试题（提高组Pascal语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共10题，每题1.5分，共计15分。
每题有且仅有一个正确答案）。
1．在以下各项中，（ C ）不是操作系统软件。
A．Solaris B．Linux C．Sybase D．Windows Vista E．Symbian2．微型计算机中，控制器的基本功能是（A ）。
A．控制机器的各个部件协调工作 B．实现算数运算与逻辑运算 C．存储各种控制信息D．获取外部信息E．存放程序和数据3．设字符串S=“Olympic”，S的非空字串的数目是（ C ）。
A．29 B．28 C．16 D．17 E．74．完全二叉树有2*N-1的结点，则它的叶子结点数目是（C ）。
A．N-1 B．2*N C．N D．2N-1 E．N/25．将数组{8，23，4，16，77，-5，53，100}中元素从大到小按顺序排序，每次可以交换任意两个元素，最少要交换（ B ）次。
A．4 B．5 C．6 D．7 E．8原顺序：8 23 4 16 77 -5 53 100现顺序：-5 4 8 16 23 53 77 100变化：1 2 3 4 5 6 7 83 5 24 7 1 6 8共六位需要变化所以最少6-1=5次6．设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈，出栈顺序为b，d，c，f，e，a那么栈容量至少应该是（ D ）。
A．6 B．5 C．4 D．3 E．27．与十进制数28.5625相等的四进制数是（D ）A．123.21 B．131.22 C．130.22 D．130.21 E．130.20 十进制小数→二进制小数：整数部分照常；小数部分转换方法：(1)把十进制小数乘以2，得到积，把积的整数部分提出；(2)再用所得积的小数部分乘以2，得到积，把积的整数部分提出；(3)重复步骤2；(4)乘以2过程中提出的各个整数部分组成转换后的二进制小数。
NOIP2008普及组初赛试题+答案第十四届全国青少年信息学奥林匹克联赛初赛试题（普及组Pascal语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效一、单项选择题（共20题，每题1.5分，共计30分。
每题有且仅有一个正确答案.）。
1.微型计算机中,控制器的基本功能是：A.控制机器各个部件协调工作B.实现算术运算和逻辑运算C.获取外部信息D.存放程序和数据2.设A=TRUE B=fALSE C=TRUE D=fALSE以下逻辑运算中表达式值为真的是：A.（A∧B)∨(C∧D∨┐A)B.((┐A∧B)∨C)∧┐D)C.(B∨C∨D)∧D∧AD.A∧(D∨┐C)∧B3.在下列关于图灵奖的说法中,不正确的是：A.图灵奖是美国计算机协会于1966年设立的,专门奖励那些对计算机事业做出重要贡献的个人B.图灵奖有计算机界诺贝尔奖的称号C.迄今为止，还没有华裔计算机科学家获此殊荣D.图灵奖的名称取自计算机科学的先驱、英国科学家阿兰•图灵4.计算机在工作过程中，若突然停电，（）中的信息不会丢失。
A.ROM和RAMB.CPUC.ROMD.RAM5.完全二叉树共有2n-1个节点，则它的叶节点数为：A.N-1B.NC.2*ND.2^N-16.在下列各项中，（）不是操作系统软件。
A.SolarisB.linuxC.Windows VistaD.Sybase7.设栈S的初始状态为空，元素A,B,C,D,E,f依次入栈S，出栈的序列为B,D,f,E,C,A,则栈S 的容量至少应该是：A.6B.5C.4D.38.与十进制数28.5625相等的四进制数是：A.123.21B.131.22C.130.22D.130.219.设字符串S="Olympic",S的非空字串的数目为A.28B.29C.16D.1710.Web2.0是近年来互联网的热门概念之一，其核心思想是互动与分享，下列网站中，（）是典型的Web2.0应用。
1995NOIP01普及组 (2)1996NOIP02普及组 (2)1997NOIP03普及组 (2)1998NOIP04普及组 (2)1999NOIP05普及组 (2)2000NOIP06普及组 (3)2001NOIP07普及组 (3)2002NOIP08普及组 (4)2003NOIP09普及组 (4)2004NOIP10普及组 (4)2005NOIP11普及组 (4)2006NOIP12普及组 (5)2007NOIP13普及组 (5)2008NOIP14普及组 (6)2009NOIP15普及组 (6)2010NOIP16普及组 (7)2011NOIP17普及组 (7)2012NOIP18普及组 (8)2013NOIP19普及组 (8)2014NOIP20普及组 (8)2015NOIP21普及组 (9)1995NOIP01提高组 (9)1996NOIP02提高组 (9)1997NOIP03提高组 (9)1998NOIP04提高组 (9)1999NOIP05提高组 (10)2000NOIP06提高组 (10)2001NOIP07提高组 (10)2002NOIP08提高组 (10)2003NOIP09提高组 (10)2004NOIP10提高组 (11)2005NOIP11提高组 (11)2006NOIP12提高组 (11)2007NOIP13提高组 (12)2008NOIP14提高组 (12)2009NOIP15提高组 (12)2010NOIP16提高组 (13)2011NOIP17提高组 (13)2012NOIP18提高组 (14)2013NOIP19提高组 (14)2014NOIP20提高组 (15)2015NOIP21提高组 (15)1995NOIP01普及组1996NOIP02普及组1997NOIP03普及组1998NOIP04普及组1．已知一个数列U1，U2，U3，…，U N，…往往可以找到一个最小的K值和K个数a1，a2，…，a k使得数列从某项开始都满足：U N+K=a1U N+K-1+a2U N+K-2+……+a k U N(A) 例如对斐波拉契数列1，1，2，3，5，…可以发现：当K=2，a1 =1，a2 =1时，从第3项起（即N>=1）都满足U n+2 =U n+1+U n 。
N O I’95“同创杯”全国青少年信息学（计算机）奥林匹克竞赛分区联赛复赛试题（高中组）（上机编程，完成时间：210分钟）<1>编码问题：设有一个数组A:ARRAY[0..N-1] OF INTEGER；数组中存放的元素为0～N-1之间的整数，且A[i]≠A[j]（当i≠j时）。
N-1），N1数据输入的方式为：NP1（颜色，为一个字母） N1（灯的数量）P2 N2……Q（结束标记，Q本身不是灯的颜色）程序要求：求出一种顺序的排列方案及排列总数。
<3> 设有一个四层的积木块，1～4层积木块的数量依次为：5，6，7，82个。
例如n=2时的比赛安排：队 1 2 3 4比赛 1==2 3==4 一天1==3 2==4 二天1==4 2==3 三天2．数制转换（20分）设有一个字符串A$的结构为：A$=’m<n>p’其中m为数字串（长度<=20），而n,p均为1或2位的数字串（其中所表达的内容在2-10之间）。
程序要求：从键盘上读入A$后（不用正确性检查），将A$中的数字串m(n进制)，以p进制的形式输出。
例如：A$=’48<10>8’其意义为：将10进制数48，转换成8进制数输出。
输出结果为：48<10>=60<8>4．挖地雷（30分）在一个地图上有N 个地窖（N<=20），每个地窖中埋有一定数量的地雷。
同时，给出地窖之间的连接路径。
[题目要求] 当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接，当设计一（表示1g 砝码有a1个，2g 砝码有a2个，…，20g 砝码有a6个）输出方式：Total=N（N 表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）如输入：1_1_0_0_0_0 （注：下划线表示空格）输出：TOTAL=3 表示可以称出1g ，2g ，3g 三种不同的重量。
NOIP部份试题分析和解答南宁三中孙国强QQ： 393936008竞赛试题名称算法N01P2004津津的储蓄计划模拟合并果子排序+二分杏找合唱队形动态规划虫食算搜索N01P2005谁拿了最多奖学金模拟过河数学或动态规划篝火晚会图论或数学等价表达式分治NOIP2006能量项链动态规划金明的预算方案动态规划作业调度方案模拟2”k进制数数学+高精N01P2007统计数字排序字符串的展开模拟知阵取数游戏动态规划+高精树网的核图论N01P2008笨小猴模拟火柴棒等式搜索或数学传纸条动态规划双栈排序图论一、枚举：I 1 1 e ! 11 It I H It 1 LJ n. -i "i JIJ iri j注意：1.加号与等号各自需要两根火柴棍2.如果A,B,则A+B=C与B+A=C视为不同的等式（A、B、0=0）3.n根火柴棍必须全部用上【输入】输入文件matches.in共一行，乂一个整数n （nv=24）。
【输出】输出文件matches.out共一行，表示能拼成的不同等式的数目。
【输入输出样例1 ]matches, in matches, out142【输入输出样例1解释】2个等式为0+1=1和1+0=1 □【输入输出样例2】matches, in matches, out189【输入输出样例2解释】9个等式为: 0+4=4 0+11=11 1+10=112+2=42+7=94+0=47+2=9 10+1=11 11+0=11既然我们用枚举的方法，就要确定枚举什么？枚举的数量（范）有多少，估算时间和空间复杂度。
2.举例：一-年一度的高一YL杯超级篮球赛开赛了。
当然，所谓超级，意思是参赛人数可能多余5人。
小三对这项篮球非常感兴趣，所以一场都没有落下。
每个中午都准时守侯在篮球场看比赛。
经过一个星期的研究，小三终于对篮球的技战术找到了一丝丝感觉了。
他发现打YL 杯的每个班都有一奁相似的进攻战术：1:控球后卫带球到前场，找到一个最佳攻击点（x,y）2:所有除控卫以外的队员都从各自的当前位置迅速向（x,y）移动3:控球后卫根据场上情况组织进攻这个战术对于一般情况是非常奏效的，但是每个队员毕竞不像小三一样每天精力过剩, 每个队员都有一个疲劳指数W,显然对于每个队员的移动需要消耗一些能量。
