NOIP提高组初赛历年试题及答案完善题篇

NOIP提高组初赛历年试题及答案（完善题篇）完善程序，每年两题，每题每空2-4分，共28分。【数学题目】1、变量赋初值，如果以后用到的是加减运算，则赋初值0；如果以后用到的是乘除运算，则赋初值为1。2、循环条件的填空，分析表达式的规律，看表达式中的最后一项的值是否到了第m项或者是第n项，如果到了，则在循环中的第二个表达式中用到的是i=或者i=。3、循环条件中如果用的是while语句，则循环变量的初值应该在while的外面定义和赋初值，在循环语句中必须给变量自加或者是自减，即i++或i--。【字符串题目】1、把一个数字字符转变成对应的数值的格式是：ch=’1’-‘0’;把大写字母转变为小写字母的格式：ch=ch+32;把小写字母转变为大写字母的格式为：ch=ch-32。2、区分好字符数组中的指针和指针所指的值的关系。在循环语句中，当指针往后走一个位置的时候，用的是指针的自加，而不是指针所指的值的自加。【结构体题目】1、注意定义结构体变量时的格式。2、结构体中成员的调用格式。结构体中的成员分为多种类型，调用结构体中的成员，使用的是“.”或者是“—”运算符。3、如果返回的是结构体的话，函数的返回类型必须是结构体类型。调用函数的格式中，调用的若是结构体数组，则只用写结构体数组名。【函数题目】1、看函数的返回类型，函数的返回类型必须和return语句返回的表达式的类型一致。2、函数的调用的情况，函数调用时只用写函数的名称，以及函数的参数。如：f1(x)和f2(x,y)。【数组题目】1、求一个数值数组中的所有值的平均值和把大于或者小于平均值的数放到另外一个数组中。首先定义一个变量来存放平均值，如果变量avg已经定义但是没有赋初值，那么这个空填写的内容的为：avg=0;2、求平均值时有两种方法，如果在for语句的后面有avg=avg/N;则第二个空一般的填写时avg+=s[i];如果说没有avg=avg/N;则填写的是：avg+=s[i]/N。3、二维数组遍历时，使用的是两个循环，使用的是循环的嵌套使用，第二个循环填写的内容为：j=0。NOIP2011-1.大整数开方（同普及组2011-2）输入一个正整数n(1≤n≤10^100)，试用二分法计算它的平方根的整数部分。#includeiostream#includestringusingnamespacestd;constintSIZE=200;structhugeint{intlen,num[SIZE];};//其中len表示大整数的位数;num[1]表示个位，num[2]表示十位，以此类推hugeinttimes(hugeinta,hugeintb)//计算大整数a和b的乘积{inti,j;hugeintans;memset(ans.num,0,sizeof(ans.num));for(i=1;i=a.len;i++)for(j=1;j=b.len;j++)ans.num[i+j-1]+=a.num[i]*b.num[j];for(i=1;i=a.len+b.len;i++){ans.num[i+1]+=ans.num[i]/10;ans.num[i]%=10;}if(ans.num[a.len+b.len]0)ans.len=a.len+b.len;elseans.len=a.len+b.len-1;returnans;}hugeintadd(hugeinta,hugeintb)//计算大整数a和b的和{inti;hugeintans;memset(ans.num,0,sizeof(ans.num));if(a.lenb.len)ans.len=a.len;elseans.len=b.len;for(i=1;i=ans.len;i++){ans.num[i]+=a.num[i]+b.num[i];ans.num[i+1]+=ans.num[i]/10;ans.num[i]%=10;}if(ans.num[ans.len+1]0)ans.len++;returnans;}hugeintaverage(hugeinta,hugeintb)//计算大整数a和b的平均数的整数部分{inti;hugeintans;ans=add(a,b);for(i=ans.len;i=2;i--){ans.num[i-1]+=(ans.num[i]%2)*10;ans.num[i]/=2;}ans.num[1]/=2;if(ans.num[ans.len]==0)ans.len--;returnans;}hugeintplustwo(hugeinta)//计算大整数a加2之后的结果{inti;hugeintans;ans=a;ans.num[1]+=2;i=1;while((i=ans.len)&&(ans.num[i]=10)){ans.num[i+1]+=ans.num[i]/10;ans.num[i]%=10;i++;}if(ans.num[ans.len+1]0)ans.len++;returnans;}boolover(hugeinta,hugeintb)//若大整数ab则返回true，否则返回false{inti;if(a.lenb.len)returnfalse;if(a.lenb.len)returntrue;for(i=a.len;i=1;i--){if(a.num[i]b.num[i])returnfalse;if(a.num[i]b.num[i])returntrue;}returnfalse;}intmain(){strings;inti;hugeinttarget,left,middle,right;cins;memset(target.num,0,sizeof(target.num));target.len=s.length();for(i=1;i=target.len;i++)target.num[i]=s[target.len-i]-'0';memset(left.num,0,sizeof(left.num));left.len=1;left.num[1]=1;right=target;do{middle=average(left,right);if(over(times(middle,middle),target))right=middle;elseleft=middle;}while(!over(plustwo(left),right));for(i=left.len;i=1;i--)coutleft.num[i];return0;}NOIP2011-2.笛卡尔树对于一个给定的两两不等的正整数序列，笛卡尔树是这样的一棵二叉树：首先，它是一个最小堆，即除了根结点，每个节点的权值都大雨父节点的权值；其次，它的中序遍历恰好就是给定的序列。例如，对于序列7、2、12、1、10、5、15、3，下图就是一棵对应的笛卡尔树。现输入序列的规模n（1≤n100）和序列的n个元素，试求其对应的笛卡尔树的深度d（根节点深度为1），以及有多少个叶子节点的深度为d。#includeiostreamusingnamespacestd;constintSIZE=100+5;constintINFINITY=1000000;intn,a[SIZE],maxDeep,num;voidsolve(intleft,intright,intdeep){inti,j,min;if(deepmaxDeep){maxDeep=deep;num=1;}elseif(deep==maxDeep)num++;min=INFINITY;for(i=left;i=right;i++)if(mina[i]){min=a[i];j=i;}if(leftj)solve(left,j–1,deep+1);if(jright)solve(j+1,right,deep+1);}intmain(){inti;cinn;for(i=1;i=n;i++)cina[i];maxDeep=0;solve(1,n,1);coutmaxDeep''numendl;return0;}NOIP2012-1.排列数（同普及组2012-2）输入两个正整数n,m(1≤n≤20,1≤m≤n)，在1~n中任取m个数，按字典序从小到大输出所有这样的排列。例如输入:32输出:121321233132#includeiostream#includecstringusingnamespacestd;constintSIZE=25;boolused[SIZE];intdata[SIZE];intn,m,i,j,k;boolflag;intmain(){cinnm;memset(used,false,sizeof(used));for(i=1;i=m;i++){data[i]=i;used[i]=true;}flag=true;while(flag){for(i=1;i=m-1;i++)coutdata[i];coutdata[m]endl;flag=false;for(i=m;i=1;i--){used[data[i]]=false;for(j=data[i]+1;j=n;j++)if(!used[j]){used[j]=true;data[i]=j;flag=true;break;}if(flag){for(k=i+1;k=m;k++)for(j=1;j=n;j++)if(!used[j]){data[k]=j;used[j]=true;break;}break;}}}}NOIP2012-2.新壳栈小Z设计了一种新的数据结构“新壳栈”。首先，它和传统的栈一样支持压入、弹出操作。此外，其栈顶的前c个元素是它的壳，支持翻转操作。其中，c2是一个固定的正整数，表示壳的厚度。小Z还希望，每次操作，无论是压入、弹出还是翻转，都仅用与c无关的常数时间完成。聪明的你能帮助她编程实现“新壳栈”吗？程序期望的实现效果如以下两表所示。其中，输入的第一行是正整数c，之后每行输入都是一条指令。另外，如遇弹出操作时栈为空，或翻转操作时栈中元素不足c个，应当输出相应的错误信息。#includeiostreamusingnamespacestd;constintNSIZE=100000,CSIZE=1000;intn,c,r,tail,head,s[NSIZE],q[CSIZE];//数组s模拟一个栈，n为栈的元素个数//数组q模拟一个循环队列，tail为队尾的下标，head为队头的下标booldirection,empty;intprevious(intk){if(direction)return((k+c-2)%c)+1;elsereturn(k%c)+1;}intnext(intk){if(direction)return(k%c)+1;elsereturn((k+c-2)%c)+1;}voidpush(){intelement;cinelement;if(next(head)==tail){n++;s[n]=q[tail];tail=next(tail);}if(empty)empty=false;elsehead=next(head);q[head]=element;}voidpop(){if(empty){coutError:thestackisempty!endl;return;}coutq[head]endl;if(tail==head)empty=true;else{head=previous(head);if(n0){tail=previous(tail);q[tail]=s[n];n--;}}}voidreverse(){inttemp;if(next(head)==tail){directio