NOIP2005提高组初赛试题答案

第十一届全国青少年信息学奥林匹克联赛初赛试题（提高组pascal语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共10题，每题1.5分，共计15分。每题有且仅有一个正确答案.）。6.下列设备中没有计算功能的是（）。A.笔记本电脑B.掌上电脑C.智能手机D.电子计算器E.液晶显示器7.Intel的首颗64位处理器是（）。A.8088B.8086C.80386D.80486E.Pentium8.常见的邮件传输服务器使用（）协议发送邮件。A.HTTPB.SMTPC.TCPD.FTPE.POP39.不能在Linux上使用的网页浏览器是（）。A.InternetExploreB.NetscapeC.OperaD.FirefoxE.Mozilla10.一位艺术史学家有20000幅1024*768的真彩色图像，如果将这些图像以位图形式保存在CD光盘上（一张CD光盘的容量按600M计算），大约需要（）张CD光盘。A.1B.10C.100D.1000E.10000二、不定项选择题（共10题，每题1.5分，共计15分。多选或少选均不得分）。11.设A=true，B=false，C=false，D=true，以下逻辑运算表达式值为真的有（）。A.(A∧B)∨(C∧D)B.((A∧B)∨C)∧DC.A∧((B∨C)∨D)D.(A∧(B∨C))∨DE.(A∨B)∧(C∨D)12.(3725)8+(B)16的运算结果是（）。A.(3736)8B.(2016)10C.(11111100000)2D.(3006)10E.(7E0)1613.二叉树T的宽度优先遍历序列为ABCDEFGHI，已知A是C的父结点，D是G的父结点，F是I的父结点，树中所有结点的最大深度为3（根结点深度设为0），可知E的父结点可能是（）。A.AB.BC.CD.DE.F14.设栈S的初始状态为空，元素a,b,c,d,e,f,g依次入栈，以下出栈序列不可能出现的有（）。A.a,b,c,e,d,f,gB.b,c,a,f,e,g,dC.a,e,c,b,d,f,gD.d,c,f,e,b,a,gE.g,e,f,d,c,b,a15.下列外设接口中可以通过无线连接的方式连接设备的是（）。A.USB2.0高速版B.红外C.蓝牙D.串口E.IEEE802.11g无线网卡16.处理器A每秒处理的指令数是处理器B的2倍。某一特定程序P分别编译为处理器A和处理器B的指令，编译结果处理器A的_______指令数是处理器B的4倍。已知程序P的算法时间复杂度为O(n2)，如果处理器A执行程序P时能在一小时内完成的输入规模为n，则处理器B执行程序P时能在一小时内完成的输入规模为（）。A.4*nB.2*nC.nD.n/2E.n/417.以下哪个（些）不是计算机的输出设备（）。A.鼠标B.显示器C.键盘D.扫描仪E.绘图仪18.以下断电之后将不能保存数据的有（）。A.硬盘B.寄存器C.显存D.内存E.高速缓存19.下列活动中属于信息学奥赛系列活动的是（）。A.NOIPB.NOIC.IOID.冬令营E.国家队选拔赛20.下列关于高级语言的说法正确的有（）。A.Ada是历史上的第一个高级语言B.Pascal和C都是编译执行的高级语言C.C++是历史上的第一个支持面向对象的语言D.编译器将高级语言程序转变为目标代码E.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上三．问题求解（请在空格处填上答案，每空5分，共计10分）1.将数组{32,74,25,53,28,43,86,47}中的元素按从小到大的顺序排列，每次可以交换任意两个元素，最少需要交换次。52.取火柴游戏的规则如下：一堆火柴有N根，A、B两人轮流取出。每人每次可以取1根或2根，最先没有火柴可取的人为败方，另一方为胜方。如果先取者有必胜策略则记为1，先取者没有必胜策略记为0。当N分别为100，200，300，400，500时，先取者有无必胜策略的标记顺序为（回答应为一个由0和/或1组成的字符串）。11011四．阅读程序（共4题，每题8分，共计32分）1．vara,b,c,p,q:integer;r:array[0..2]ofinteger;beginread(a,b,c);p:=adivbdivc;q:=b-c+a+p;r[0]:=a*pdivq*q;r[1]:=r[0]*(r[0]-300);if(3*q-pmod3=r[0])and(r[2]=r[2])thenr[1]:=r[r[0]divpmod2]elser[1]:=qmodp;writeln(r[0]-r[1]);end.输入：10073输出：-74522．vara:array[1..50]ofinteger;n,i,sum:integer;procedurework(p,r:integer);vari,j,temp:integer;beginifprthenbegini:=p-1;forj:=ptor-1doifa[j]=a[r]thenbegininc(i);temp:=a[i];a[i]:=a[j];a[j]:=temp;end;temp:=a[i+1];a[i+1]:=a[r];a[r]:=temp;work(p,i);work(i+2,r);end;end;beginread(n);fori:=1tondoread(a[i]);work(1,n);fori:=1ton-1dosum:=sum+abs(a[i+1]-a[i]);writeln(sum);end.输入：1023435123453123434561232-100输出：332233．varstr:string;len,i,j:integer;nchr:array[0..25]ofinteger;mmin:char;beginmmin:='z';readln(str);len:=length(str);i:=len;whilei=2dobeginifstr[i-1]str[i]thenbreak;dec(i);end;ifi=1thenbeginwriteln('Noresult!');exit;end;forj:=1toi-2dowrite(str[j]);fillchar(nchr,sizeof(nchr),0);forj:=itolendobeginif(str[j]str[i-1])and(str[j]mmin)thenmmin:=str[j];inc(nchr[ord(str[j])-ord('a')]);end;dec(nchr[ord(mmin)-ord('a')]);inc(nchr[ord(str[i-1])-ord('a')]);write(mmin);fori:=0to25doforj:=1tonchr[i]dowrite(chr(i+ord('a')));writeln;end.输入：zzyzcccbbbaaa输出：zzzaaabbbcccy4.varn:longint;functiong(k:longint):longint;beginifk=1theng:=kelseg:=(2002*g(k-1)+2003*g(k-2))mod2005;end;beginread(n);writeln(g(n));end.输入：2005输出：五．完善程序(前5空，每空2分，后6空，每空3分，共28分)1．木材加工题目描述:木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头（木头有可能有剩余），需要得到的小段的数目是给定的。当然，我们希望得到的小段越长越好，你的任务是计算能够得到的小段木头的最大长度。木头长度的单位是cm。原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。输入:第一行是两个正整数N和K(1≤N≤10000，1≤K≤10000)，N是原木的数目，K是需要得到的小段的数目。接下来的N行，每行有一个1到10000之间的正整数，表示一根原木的长度。输出:输出能够切割得到的小段的最大长度。如果连1cm长的小段都切不出来，输出”0”。输入样例:37232124456输出样例:114程序：varn,k:integer;len:array[1..10000]ofinteger;i,left,right,mid:integer;functionisok(t:integer):boolean;varnum,i:integer;beginnum:=0;fori:=1tondobeginifnum=kthenbreak;num:=①;end;if②thenisok:=trueelseisok:=false;end;beginreadln(n,k);right:=0;fori:=1tondobeginreadln(len[i]);ifrightlen[i]thenright:=len[i];end;inc(right);③;while④rightdobeginmid:=(left+right)div2;if⑤thenright:=midelseleft:=mid;end;writeln(left);end.2．N叉树题目描述:我们都了解二叉树的先根遍历，中根遍历和后根遍历。当知道先根遍历的结果和中根遍历结果的时候，我们可以唯一的确定二叉树；同样的，如果知道了后根遍历的结果和中根遍历结果，二叉树也是唯一确定的。但是如果只知道先根遍历和后根遍历的结果，二叉树就不是唯一的了。但是我们可以计算满足条件的不同二叉树一共有多少个。这不是一个很困难的问题，稍微复杂一点，我们把这个问题推广到N叉树。我们用小写英文字母来表示N叉树的结点，不同的结点用不同的字母表示。比如，对于4叉树，如果先根遍历的结果是abdefgc，后根遍历的结果是defgbca，那么我们可以得到6个不同的4叉树（如下图）。输入:输入数据包括3行。第一行是一个正整数N(2≤N≤20)，表示我们要考虑N叉树。第二行和第三行分别是两个字符串序列，分别表示先根遍历和后根遍历的结果。输出:输出不同的N叉树的数目。题目中给的数据保证得到的结果小于231。输入样例:4abdefgcdefgbca输出样例:6程序：varstr1,str2:string;N,len:integer;com:array[0..100,0..100]oflongint;functiongetcom(x,y:integer):longint;beginif(y=0)or(x=y)then①elseifcom[x][y]0thengetcom:=com[x][y]elsebegincom[x][y]:=getcom(x-1,y)+②;getcom:=com[x][y];end;end;functioncount(a,b,c:integer):longint;varsum:longint;k,s,t,p:integer;beginsum:=1;k:=0;s:=a+1;t:=c;ifa=bthencount:=1elsebeginwhiles=bdobeginp:=t;whilestr1[s]str2[t]doinc(t);sum:=sum*count(s,s+t-p,p);s:=③;④;inc(k);end;count:=⑤*getcom(N,k);end;end;beginreadln(N);readln(str1);readln(str2);len:=length(str1);writeln(count(⑥));end.第十一届全国青少年信息学奥林匹克联赛初赛提高组(P)参考答案一.单项选择题（共10题，每题1.5分，共计15分。每题有且仅有一个正确答案.）。题号12３45678910选择BADEDEEBAC二．不定项选择题（共10题，每题1.5分，共计15分。多选或少选均不得分）。题号11121314151617181920选择CDEBCEBCCEBCEBACDBCDEABCDEBDE三．问