NOIP2022年提高组初赛试题及答案.pdf

第十一届全国青少年信息学奥林匹克联赛初赛试题(提高组pascal语言二小时完成)全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 一、单项选择题(共10题，每题1.5分，共计15分。每题有且仅有一个正确答案.)。1.字符串“ababacbab”和字符串“abcba”的最长公共子串是()。A.abcba B.cba C.abc D.ab E.bcba2.设全集I=a,b,c,d,e,f,g,h ,集合B D A=%b,c,d,e,f,C n A=c,d,e,B cA=a,d,那么集合C c B c A 为()。A.c,e B.d,e)C.e D.c,d,e E.d,f3.以下二进制数的值与十进制数23.456的值最接近的是()。A.10111.0101 B.11011.1111 C.11011.0111 D.10111.0111 E.10111.11114.完全二叉树的结点个数为4*N+3,则它的叶结点个数为()oA.2*NB.2*N-1C.2*N+1D.2*N-2E.2*N +25.平面上有五个点A(5,3),B(3,5),C(2,1),D(3,3),E(5,1)。以这五点作为完全图G 的顶点，每两点之间的直线距离是图G 中对应边的权值。图G 的最小生成树中的全部边的权值综 合 为().A.8 B.7+5 C.9 D.6+5 E.4+2 2+56.以下设备中没有计算功能的是()。A.笔记本电脑B.掌上电脑C.智能手机D.电子计算器E.液晶显示器7.Intel的首颗64位处理器是()。A.8088 B.8086 C.80386 D.80486 E.Pentium8.常见的邮件传输效劳器使用()协议发送邮件。A.B.SMTP C.TCP D.FTP E.POP39.不能在Linux上使用的网页扫瞄器是()oA.Internet Explore B.Netscape C.Opera D.Firefox E.Mozilla10.一位艺术史学家有20220幅1024*768的真彩色图像，假设将这些图像以位图形式保存在CD光盘上(一张CD 光盘的容量按600M计 算)，大约需要()张CD光盘。A.1 B.10 C.100 D.1000 E.10000二、不定项选择题(共10题，每题1.5分，共计15分。多项选择或少选均不得分)。11.设人=true,B=false,C=false,D=tru e,以下规律运算表达式值为真的有()。A.(A B A)V(C D A)B.(A B A)C V)D A C.AA(B C V)D V)D.(AA(B C V)D V E.(A B V)A(C D V)12.(3725%+(B)6的运算结果是().A.(3736)8B.(2O22)IOC.(11111100000),D.(3OO6)IOE.(7E0)l613.二叉树T的宽度优先遍历序列为A aC DE FG HI,A是C的父结点，D 是G 的父结点，F 是I 的父结点，树中全部结点的最大深度为3(根结点深度设为0),可知E的父结点可能是()。A.A B.B C.C D.D E.F14.设栈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,c,b,d,f,gD.d,c,f,e,b,a,g E.g,e,f,d,c,b,a1 5.以下外设接口中可以通过无线连接的方式连接设备的是()。A.USB 2.0高速版B.红外C.蓝牙D.串口E.IEEE 802.11g无线网卡1 6.处理器A每秒处理的指令数是处理器B 的2倍。某一特定程序P 分别编译为处理器A和处理器B的指令，编译结果处理器A 的指令数是处理器B的4 倍。程序P 的算法时间简单度为0（n 2），假设处理器A 执行程序P 时能在一小时内完成的输入规模为n,则处理器B 执行程序P 时能在一小时内完成的输入规模为（）。A.4*n B.2*n C.n D.n/2 E.n/41 7 .以下哪个（些）不是计算机的输出设备（）。A.鼠标B.显示器C.键盘D.扫描仪E.绘图仪1 8 .以下断电之后将不能保存数据的有（）。A.硬盘B.存放器C.显存D.内存E.高速缓存1 9 .以下活动中属于信息学奥赛系列活动的是（）。A.N O I P B.N O I C.1 0 1 D.冬令营E.国家队选拔赛2 0.以下关于高级语言的说法正确的有（）。A.A da 是历史上的第一个高级语言B.P a s ca l 和C 都是编译执行的高级语言C.C+是历史上的第一个支持面对对象的语言D.编译器将高级语言程序转变为目标代码E.高级语言程序比汇编语言程序更简洁从一种计算机移植到另一种计算机上三.问 题 求 解（请在空格处填上答案，每空5 分，共计1 0 分）1 .将数组 3 2,7 4,2 5,5 3,2 8,4 3,8 6,4 7 中的元素按从小到大的挨次排列，每次可以交换任意两个元素，最少需要交换次。2 .取火柴玩耍的规章如下：一堆火柴有N 根，A、B 两人轮番取出。每人每次可以取1 根或2 根，最先没有火柴可取的人为败方，另一方为胜方。假设先取者有必胜策略则记为1,先取者没有必胜策略记为0。当N 分别为1 0 0,2 0 0,3 0 0,4 0 0,500时;先取者有无必胜策略的标记挨次为（回同意为一个由0和/或1组成的字符串）。四.阅读程序(共4 题，每题8 分，共计32分)1.vara,b,c,p,q:integer;r:array0.2 of integer;beginread(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(r2=r2)thenr1 :=rr0 div p mod 2else r1:=q mod p;writein(r 0-r1);end.输入：100 7 3输出：2.vara:array 1.50 of integer;n,i,sum:integer;procedure work(p,r:integer);varizj r temp:integer;beginif p=ar then begininc(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+2f r);end;end;beginread(n);for i:=1 to n do read(ai);work(lzn);for i:=1 to n-1 do sum:=sum+abs(a i+1 -a i);writein(sum);end.输入：10 23 435 12 345 3123 43 456 12 32-100输出：3.varstr:string;lenz iz j:integer;nchr:array 0.25 of integer;mmin:char;beginmmin:=z;readln(str);len:=length(str);i:=len;while i=2 do beginif stri-1 stri-1)and(strj mmin)thenmmin:=strj;inc(nchrord(strj)-ord(a);end;dec(nchrord(mmin)inc(nchrord(stri-ord(a);-1)-ord(a);write(mmin);for i:=0 to 25 dofor j :=1 towrite(chr(i+writein;nchri doord(a);end.输入：z z y z cccb b b a a a输出：4 .va rn :l o n g i n t;f u n ct i o n g (k :l o n g i n t):l o n g i n t;b eg i ni f k =k then b reak;num:=；end;if then isok:=trueelse isok:=false;end;beginreadln(n,k);right:=0;for i:=1 to n do beginreadln(leni);if right leni then right:=leni;end;inc(right);；while right do beginmid:=(left+right)div 2;if then right:=midelse left:=mid;end;writein(left);end.2.N叉树题目描述：我们都了解二叉树的先根遍历，中根遍历和后根遍历。当知道先根遍历的结果和中根遍历结果的时候，我们可以唯一确实定二叉树；同样的，假设知道了后根遍历的结果和中根遍历结果，二叉树也是唯一确定的。但是假设只知道先根遍历和后根遍历的结果，二叉树就不是唯一的了。但是我们可以计算满足条件的不同二叉树一共有多少个。这不是一个很困难的问题，略微简单一点，我们把这个问题推广到N叉树。我们用小写英文字母来表示N 叉树的结点，不同的结点用不同的字母表示。比方，对于4叉树，假设先根遍历的结果是abdefgc,后根遍历的结果是defgbca,那么我们可以得到6个不同的4叉树(如以下图)。输入：输入数据包括3行。第一行是一个正整数N(2 W N W 20),表示我们要考虑N叉树。其次行和第三行分别是两个字符串序列，分别表示先根遍历和后根遍历的结果。输出：输出不同的N叉树的数目。题目中给的数据保证得到的结果小于231O输入样例：4abdefgcdefgbca输出样例：6程序：varstrlz str2:string;N,len:integer;com:array0.100,0.100 of longint;function getcom(xz y:integer):longint;beginif(y=0)or(x=y)then else if comx y 0 then getcom:=comx yelse begincomx y:=getcom(x-1z y)+；getcom:=comxy;end;end;function count(a,b,c:integer):longint;varsum:longint;kz s,t,p:integer;beginsum:=1;k:=0;s:=a+1;t:=c;if a=b then count:=1else beginwhile s=b do beginp：=t;while strl s str2 t do inc(t);sum:=sum*count(s,s+t-p,p);s ;inc(k);end;count:=()*getcom(N,k);end;end;beginreadln(N);readln(strl);readln(str2);len:=length(strl);writein(count();end.第十一届全国青少年信息学奥林匹克联赛初赛提高组(P)参考答案一.单 项 选 择 题(共1 0题，每 题1.5分，共 计1 5分。每题有且仅有一个正确答案.)。题号 12 3456789 1 0选择 BADEDEEBAC二.不定项选择题 共1 0题，每 题1.5分，共 计1 5分。多班选择或少选均不得分。题号 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0选择 C D E B C E B C C E B C E B A C D B C D E A B C D E B D E三.问 题 求 解(共2题，每 题5分，共 计1 0分)1.答：_5 _ _ _ _ _ _ _ _2.答：1 1 0 1 1四.阅读 程序(共4题，每题8分，共 计3 2分)(1)程序的运行结果是：7452(2)程序的运行结果是：3223(3)程序的运行结果是：zzzaaabbbcccy(4)程序的运行结果是：31五.完 善 程 序(前5空，每 空2分，后6空，每 空3分，共2 8分)pascal语言1.(1)num+len i di v t(2)num =k(3)left:=0(4)left+1(5)not i sok(mi d)(或者 i sok(mi d)=false)2.(1)getcom:=1(2)getcom(x-1,y-1)(3)s+t-p+1(4)i nc(t)(或者 t:=t+1)(5)sum(6)1,len,1