下载文档原格式
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}进行二分查找，等概率情况下，查找成功的平均查找长度（平均比较次数）是（）。
全国青少年信息学奥林匹克联赛复赛模拟试题湖南省长沙市第一中学周祖松1．无限序列(infinit.pas/c/cpp)【问题描述】我们按以下方式产生序列：1、开始时序列是： "1" ；2、每一次变化把序列中的 "1" 变成 "10" ，"0" 变成 "1"。
经过无限次变化，我们得到序列"1011010110110101101..."。
总共有 Q 个询问，每次询问为：在区间A和B之间有多少个1。
任务写一个程序回答Q个询问输入第一行为一个整数Q，后面有Q行，每行两个数用空格隔开的整数a, b。
输出共Q行，每行一个回答约定∙ 1 <= Q <= 5000∙ 1 <= a <= b < 263样例分析：我们先看看序列变化规律，S1 = "1", S2 = "10", S3 = "101", S4 = "10110", S5 = "10110101", 等等. Si 是 S（i+1）的前缀。
序列Si 是由序列 S（i-1）和 S（i-2）, 连接而成的。
即Si = Si-1 + Si-2 (实际上上是Fibonacci数列)。
找到规律以后，我们可以可以用递归的方法求出从从位置1到位置X之间所有的1的个数，用一个函数F计算，结果为f(b)-f(a-1)。
时间复杂度为： O(Q * log MAX_VAL)此题需要先找出数学规律，再进用递归实现。
主要考查选手的数学思维能力和递归程序的实现。
源程序：constnn=92; //进行92次的数列扩展后，数列长度就会超过给定的数据范围,varf,ft:array[0..nn] of int64;q,i,j,l1,l2:longint;a,b:qword;procedure prapre;{预处理}var i:longint;beginf[0]:=1;f[1]:=1;ft[0]:=0;ft[1]:=1;for i:=2 to nn dobeginf[i]:=f[i-1]+f[i-2];ft[i]:=ft[i-1]+ft[i-2];end;end;function find(a:int64;ll:longint):int64;{求这个数列的前a个有多少个1}beginif a=0 then exit(0);find:=0;if a=f[ll] then find:=ft[ll] elseif a<=f[ll-1] then find:=find(a,ll-1)else find:=ft[ll-1]+find(a-f[ll-1],ll-2);end;beginassign(input,'infinit.in');reset(input);assign(output,'infinit.out');rewrite(output);prapre;readln(q);for i:=1 to q dobeginreadln(a,b);writeln(find(b,nn)-find(a-1,nn));end;close(input);close(output);end.2．删数(remove.pas/c/cpp)【问题描述】有N个不同的正整数数x1, x2, ... x N排成一排，我们可以从左边或右边去掉连续的i个数（只能从两边删除数），1<=i<=n，剩下N-i个数，再把剩下的数按以上操作处理，直到所有的数都被删除为止。
Day1铺地毯【问题描述】为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。
一共有n 张地毯，编号从1 到n。
现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。
地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。
注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。
【输入】输入文件名为 carpet.in。
输入共 n+2 行。
第一行，一个整数 n，表示总共有n 张地毯。
接下来的 n 行中，第i+1 行表示编号i 的地毯的信息，包含四个正整数a，b，g，k，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标（a，b）以及地毯在x轴和y 轴方向的长度。
第 n+2 行包含两个正整数x 和y，表示所求的地面的点的坐标（x，y）。
【输出】输出文件名为 carpet.out。
输出共 1 行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出-1。
【输入输出样例 1】【输入输出样例说明】如下图，1 号地毯用实线表示，2 号地毯用虚线表示，3 号用双实线表示，覆盖点（2，2）的最上面一张地毯是3 号地毯。
【输入输出样例 2】【输入输出样例说明】如上图，1 号地毯用实线表示，2 号地毯用虚线表示，3 号用双实线表示，点（4，5）没有被地毯覆盖，所以输出-1。
【数据范围】对于 30%的数据，有n≤2；对于 50%的数据，0≤a, b, g, k≤100；对于 100%的数据，有0≤n≤10,000，0≤a, b, g, k≤100,000。
【一句话题意】给定n个按顺序覆盖的矩形，求某个点最上方的矩形编号。
【考察知识点】枚举【思路】好吧我承认看到图片的一瞬间想到过二维树状数组和二维线段树。
置答案ans=-1，按顺序枚举所有矩形，如果点在矩形内则更新ans。
注意题中给出的不是对角坐标，实际上是(a,b)与(a+g,b+k)。
题目编号0003题目名称笨小猴题目来源Noip 2008 编写时间未知难度 1题目NOIP2008复赛提高组第一题描述Description笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。
但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！这种方法的具体描述如下：假设maxn是单词中出现次数最多的字母的出现次数，minn是单词中出现次数最少的字母的出现次数，如果maxn-minn是一个质数，那么笨小猴就认为这是个Lucky Word，这样的单词很可能就是正确的答案。
输入格式Input Format输入只有一行，是一个单词，其中只可能出现小写字母，并且长度小于100。
输出格式Output Format输出共两行，第一行是一个字符串，假设输入的的单词是Lucky Word，那么输出“Lucky Word”，否则输出“No Answer”；第二行是一个整数，如果输入单词是Lucky Word，输出maxn-minn的值，否则输出0。
输入样例1error输入样例2Olympic输出样例1Lucky Word2输出样例2No Answer分析用下标为字符变量的数组来存储每个字母的出现次数，扫描一遍，用max 和min记录值和最小值，对他们的差进行判断，是否是质数。
小结在这道题目中，我对求质数的方法有了更进一步的体会，在小于算数平方根数的范围内没有质因子，大于几何平均数的范围内也不会有，只需从小于算数平方根的范围内判断是否是其因数即可。
源程序program stupidmonkey;vara:string; {读入英语单词}i:longint; {整形循环变量}j:char; {字符型循环变量}b:array['a'..'z'] of longint; {定义一个下标为字符型的数组，用于存储每个字母出现的次数}maxn:longint; {出现次数最多字母的出现次数} minn:longint; {出现次数最少字母的出现次数} s:integer; {字符串长度}cha:integer; {最大值和最小值的差} function max(m, n:longint):longint; {求最大值函数}beginif (m>n) thenmax:= melsemax:= n;end;function min(m , n:longint):longint; {求最小值函数}beginif (m<n) thenmin:= melsemin:= n;end;function zhi(m:longint):boolean; {判断质数函数}var i:longint;beginif m<2 thenbeginzhi:=false;exit;end;for i:= 2 to trunc(sqrt(m) ) do ｛原来使用2 to m-1，和现在相比复杂了很多，因为在小于算数平方根的范围内没有质因子，大于几何平均数的范围内也不会有｝if m mod i=0 thenbeginzhi:=false;exit;end;zhi:=true;end;begin {main}maxn:=0;minn:=101;readln(a);fillchar(b,sizeof(b),0); ｛注意要把数组置空｝s:=length(a);for i:= 1 to s dobegininc(b[a[i]]);end;for j:= 'a' to 'z' doif b[j]<>0 thenbeginmaxn:=max(b[j],maxn);minn:=min(b[j],minn);end;cha:=maxn-minn;if( zhi(cha)) thenbeginwriteln('Lucky Word');writeln(cha);endelsebeginwriteln('No Answer');writeln(0);end;end.。
