第十一届全国青少年信息学奥林匹克联赛初赛试题（普及组pascal&C语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●由OIFans（www.OIFans.cn）整理一．选择一个正确答案代码（A/B/C/D/E）,填入每题的括号内(每题1.5分,共30分)1.在字符串“ababacbabcbdecced”中出现次数最多的字母出现了（）次。A.6 B.5 C.4 D.3 E.2 2.设全集I={a,b,c,d,e,f,g,h}，集合A={a,b,c,d,e,f}，B={c,d,e}，C={a,d}，那么集合C B A~ÇÇ为（）。A.{c,e}B.{d,e}C.{e}D.{c,d,e}E.{d,f}3.和十进制数23的值相等的二进制数是（）。A.10110 B.11011 C.11011 D.10111 E.10011 4.完全二叉树的结点个数为11，则它的叶结点个数为（）。A.4 B.3 C.5 D.2 E.6 5.平面上有五个点A(5,3),B(3,5),C(2,1),D(3,3),E(5,1)。以这五点作为完全图G的顶点，每两点之间的直线距离是图G中对应边的权值。以下哪条边不是图G的最小生成树中的边（）。A.AD B.BD C.CD D.DE E.EA 6.Intel的首颗16位处理器是（）。A.8088 B.80386 C.80486 D.8086 E.Pentium 7.处理器A每秒处理的指令数是处理器B的2倍。某一特定程序P分别编译为处理器A和处理器B的指令，编译结果处理器A的指令数是处理器B的4倍。已知程序P在处理器A上执行需要1个小时，那么在输入相同的情况下，程序P在处理器B上执行需要（）小时。A.4 B.2 C.1 D.1/2 E.1/4 8.以下哪个不是计算机的输出设备（）。A.音箱B.显示器C.打印机D.扫描仪E.绘图仪9.下列活动中不属于信息学奥赛的系列活动的是（）。A.NOIP B.NOI C.IOI D.冬令营E.程序员等级考试10.以下断电之后仍能保存数据的是（）。A.硬盘B.寄存器C.显存D.内存E.高速缓存11.以下哪个软件不是即时通信软件（）。A.网易泡泡B.MSN Messenger C.Google Talk D.3DS Max E.QQ 12.下列关于高级语言的说法错误的是（）。A.Fortran是历史上的第一个面向科学计算的高级语言B.Pascal和C都是编译执行的高级语言C.C++是历史上的第一个支持面向对象的语言D.编译器将高级语言程序转变为目标代码E.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上13.下列设备不具有计算功能的是（）。A.笔记本电脑B.掌上电脑C.智能手机D.电子计算器E.液晶显示器14.常见的邮件传输服务器使用（）协议接收邮件。A.HTTP B.SMTP C.TCP D.FTP E.POP3 15.下列浏览器中，由微软公司开发的浏览器是（）。A.Internet Explore B.Netscape C.Opera D.Firefox E.Mozilla 16.一位艺术史学家有20000幅真彩色图像，每幅图像约占3M空间。如果将这些图像以位图形式保存在CD光盘上（一张CD光盘的容量按600M计算），大约需要（）张CD光盘。A.1 B.10 C.100 D.1000 E.10000 17.设A=true，B=false，C=false，D=true，以下逻辑运算表达式值为真的是（）。A.(A B∧)∨(C D∧)B.((A B∧)C∨)D∧C.A∧((B C∨)D∧)D.(A∧(B C∨))D∨E.(A B∨)∧(C D∧)18.(3725)8+(B)16的运算结果是（）。A.(3736)8 B.(2016)10 C.(1111110000)2 D.(3006)10 E.(7B0)16 19.二叉树T的宽度优先遍历序列为A B C D E F G H I，已知A是C的父结点，D是G的父结点，F是I的父结点，树中所有结点的最大深度为3（根结点深度设为0），可知F的父结点是（）。A.无法确定B.B C.C D.D E.E 20.设栈S的初始状态为空，元素a,b,c,d,e,f,g依次入栈，以下出栈序列不可能出现的是（）。A.a,b,c,e,d,f,g B.b,c,a,f,e,g,d C.a,e,d,c,b,f,g D.d,c,f,e,b,a,g E.g,e,f,d,c,b,a二．问题求解（请在空格处填上答案，每空5分，共10分）1.将数组{32,74,25,53,28,43,86,47}中的元素按从小到大的顺序排列，每次可以交换任意两个元素，最少需要交换次。2.有3个课外小组：物理组，化学组和生物组。今有张、王、李、赵、陈5名同学，已知张、王为物理组成员，张、李、赵为化学组成员，李、赵、陈为生物组成员。如果要在3个小组中分别选出3位组长，一位同学最多只能担任一个小组的组长，共有种选择方案。三．阅读程序（共4题，每题8分，共计32分）==================PASCAL语言==================1．var a,b:integer;begin read(a);b:=(a*(a*a))+1;if b mod 3=0 then b:=b div 3;if b mod 5=0 then b:=b div 5;if b mod 7=0 then b:=b div 7;if b mod 9=0 then b:=b div 9;if b mod 11=0 then b:=b div 11;if b mod 13=0 then b:=b div 13;if b mod 15=0 then b:=b div 15;writeln((100*a-b)div 2);end.输入：10输出：2.var str:string;i:integer;begin str:=’Today-is-terrible!’;for i:=7 to 11 do if str=’-’then str[i-1]:=’x’;for i:=13 downto 1 do if str=’t’then str[i+1]:=’e’;writeln(str);end.输出：3．var a,b,c,p,q:integer;r:array[0..2]of integer;begin read(a,b,c);p:=a div b div c;q:=b-c+a+p;r[0]:=a*p div q*q;r[1]:=r[0]*(r[0]-300);if(3*q-p mod 3<=r[0])and(r[2]=r[2])then r[1]:=r[r[0]div p mod 2]else r[1]:=q mod p;writeln(r[0]-r[1]);end.输入：100 7 3输出：4．var str:string;len,i,j:integer;nchr:array[0..25]of integer;mmin:char;begin mmin:=’z’;readln(str);len:=length(str);i:=len;while i>=2 do begin if str[i-1]<str then break;dec(i);end;if i=1 then begin writeln(’No result!’);exit;end;for j:=1 to i-2 do write(str[j]);fillchar(nchr,sizeof(nchr),0);for j:=i to len do begin if(str[j]>str[i-1])and(str[j]<mmin)then mmin:=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);for i:=0 to 25 do for j:=1 to nchr do write(chr(i+ord(’a’)));writeln;end.输入：zzyzcccbbbaaa输出：==================C语言==================1．#include<stdio.h>int main(){int a,b;scanf(“%d”,&a);b=(a*(a*a))+1;if(b%3==0)b=b/3;if(b%5==0)b=b/5;if(b%7==0)b=b/7;if(b%9==0)b=b/9;if(b%11==0)b=b/11;if(b%13==0)b=b/13;if(b%15==0)b=b/15;printf(“%d\n”,(100*a–b)/2);return 0;}输入：10输出：2．#include<stdio.h>int main(){char str[20]=“Today-is-terrible!”;int i;for(i=6;i<=10;i++)if(str==‘-‘)str[i–1]=‘x‘;for(i=12;i>=0;i--)if(str==‘t’)str[i+1]=‘e’;printf(“%s\n”,str);return 0;}输出：3．#include<stdio.h>int main(){int a,b,c,p,q,r[3];scanf(“%d%d%d”,&a,&b,&c);p=a/b/c;q=b–c+a+p;r[0]=a*p/q*q;r[1]=r[0]*(r[0]–300);if(3*q–p%3<=r[0]&&r[2]==r[2])r[1]=r[r[0]/p%2];else r[1]=q%p;printf(“%d\n”,r[0]–r[1]);return 0;}输入：100 7 3输出：4．#include<stdio.h>#include<string.h>int main(){char str[60];int len,i,j,chr[26];char mmin=’z’;scanf("%s",str);len=strlen(str);for(i=len-1;i>=1;i--)if(str[i-1]<str)break;if(i==0){printf("No result!\n");return 0;}for(j=0;j<i-1;j++)putchar(str[j]);memset(chr,0,sizeof(chr));for(j=i;j<len;j++){if(str[j]>str[i-1]&&str[j]<mmin)mmin=str[j];chr[str[j]-’a’]++;}chr[mmin-’a’]--;chr[str[i-1]-’a’]++;putchar(mmin);for(i=0;i<26;i++)for(j=0;j<chr;j++)putchar(i+’a’);putchar(’\n’);return 0;}输入：zzyzcccbbbaaa输出：四．完善程序(前4空，每空2分，后5空，每空4分，共28分)==================PASCAL语言==================1．判断质数题目描述:给出一个正整数，判断这个数是否是质数。输入:一个正整数n(1≤n≤10000)。输出:如果n是质数，输出”YES”；否则，输出”NO”。输入样例:10输出样例:NO程序：var①:integer;begin read(n);if n=2 then writeln(②)else if(③)or(n mod 2=0)then writeln(’NO’)else begin i:=3;while i*i<=n do begin if④then begin writeln(’NO’);exit;end;i:=i+2;end;writeln(’YES’);end;end.2．木材加工题目描述:木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头（木头有可能有剩余），需要得到的小段的数目是给定的。当然，我们希望得到的小段越长越好，你的任务是计算能够得到的小段木头的最大长度。木头长度的单位是cm。原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。输入:第一行是两个正整数N和K(1≤N≤10000，1≤K≤10000)，N是原木的数目，K是需要得到的小段的数目。接下来的N行，每行有一个1到10000之间的正整数，表示一根原木的长度。输出:输出能够切割得到的小段的最大长度。如果连1cm长的小段都切不出来，输出”0”。输入样例:3 7 232 124 456输出样例:114程序：var n,k:integer;len:array[1..10000]of integer;i,left,right,mid:integer;function isok(t:integer):boolean;var num,i:integer;begin num:=0;for i:=1 to n do begin if num>=k then break;num:=①;end;if②then isok:=true else isok:=false;end;begin readln(n,k);right:=0;for i:=1 to n do begin readln(len);if right<len then right:=len;end;inc(right);③;while④<right do begin mid:=(left+right)div 2;if⑤then right:=mid else left:=mid;end;writeln(left);end.==================C语言==================1．判断质数题目描述:给出一个正整数，判断这个数是否是质数。输入:一个正整数n(1≤n≤10000)。输出:如果n是质数，输出”YES”；否则，输出”NO”。输入样例:10输出样例:NO程序：#include<stdio.h>int main(){int①;scanf("%d",&n);if(n==2)puts(②);else if(③||n%2==0)puts("NO");else{i=3;while(i*i<=n){if(④){puts("NO");return 0;}i=i+2;}puts("YES");}return 0;}2．木材加工题目描述:木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目是给定的。当然，我们希望得到的小段越长越好，你的任务是计算能够得到的小段木头的最大长度。木头长度的单位是cm。原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。输入:第一行是两个正整数N和K(1≤N≤10000，1≤K≤10000)，N是原木的数目，K是需要得到的小段的数目。接下来的N行，每行有一个1到10000之间的正整数，表示一根原木的长度。输出:输出能够切割得到的小段的最大长度。如果连1cm长的小段都切不出来，输出”0”。输入样例:3 7 232 124 456输出样例:114程序：#include<stdio.h>int n,k,len[10000];int isok(int t){int num=0,i;for(i=0;i<n;i++){if(num>=k)break;num=①;}if(②)return 1;else return 0;}int main(){int i,left,right,mid;scanf("%d%d",&n,&k);right=0;for(i=0;i<n;i++){scanf("%d",&(len));if(right<len)right=len;}right++;③;while(④<right){mid=(left+right)/2;if(⑤)right=mid;else left=mid;}printf("%d\n",left);return 0;第十一届全国青少年信息学奥林匹克联赛初赛试题普及组(P&C)参考答案由OIFans（www.OIFans.cn）整理一.选择一个正确答案代码（A/B/C/D/E）,填入每题的括号内(每题1.5分,多选无分,共30分)题号12３45678910选择BADEDDDDEA题号11121314151617181920选择DCEEACDBCE二．问题解答（每题5分，共10分）1.答：5 2.答：11三.阅读程序，并写出程序的正确运行结果：（每题8分，共32分）(1)程序的运行结果是:499(2)程序的运行结果是:Today-ix-terrible!(3)程序的运行结果是:-7452(4)程序的运行结果是:zzzaaabbbcccy四.根据题意,将程序补充完整(前4空，每空2分，后5空，每空4分，共28分)pascal语言＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝1.①n,i（或者i,n）②’YES’③n=1(或者n–1=0)④n mod i=0 2.①num+len[i]div t②num>=k③left:=0④left+1⑤not isok(mid)（或者isok(mid)=false）C语言＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝1.①n,i（或者i,n）②’YES’③n==1(或者n–1==0)④n%i==0（或者!n%i）2.①num+len[i]/t②num>=k③left=0④left+1⑤!isok(mid)（或者isok(mid)==0）。
