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

《NOIP2022年提高组初赛试题及答案.docx》由会员分享，可在线阅读，更多相关《NOIP2022年提高组初赛试题及答案.docx（7页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第十一届全国青少年信息学奥林匹克联赛初赛试题(提高组pascal语言二小时完成) 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效一、单项选择题(共10题，每题L 5分，共计15分。每题有且仅有一个正确答案.)。1 .字符串“ababacbab”和字符串“abcba”的最长公共子串是()。A. abcba B. cba C. abc D. ab E. bcba.设全集I = a, b, c, d, e, f, g, h,集合3 U A = a, b, c, d, e, f, Cn A = c, d, e,3cA=a,d,那么集合CcBcA为()。A. c, e B. d, e C. e D

2、. c, d, e E. d, f.以下二进制数的值与十进制数23.456的值最接近的是)。A. 10111.0101 B. 11011.1111 C. 11011.0111 D. 10111.0111 E. 10111.1111.完全二叉树的结点个数为4 * N+3,那么它的叶结点个数为)。A. 2*NB.2*N-1C.2*N+1D. 2*N-2E2*N + 2.平面上有五个点A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1)。以这五点作为完全图G的顶点, 每两点之间的直线距离是图G中对应边的权值。图G的最小生成树中的全部边的权值 综合为()。A. 8 B

3、. 7+ 5 C. 9 D. 6+ 5 E 4+2 2 + 5.以下设备中没有计算功能的是)。A.笔记本电脑B.掌上电脑C.智能手机D.电子计算器E.液晶显示器2 . Intel的首颗64位处理器是)。A. 8088 B. 8086 C. 80386 D. 80486 E. Pentium.常见的邮件传输效劳器使用(协议发送邮件。A. B. SMTP C. TCP D. FTP E. POP3.不能在Linux上使用的网页扫瞄器是()。A. Internet Explore B. Netscape C. Opera D. Firefox E. Mozilla. 一位艺术史学家有20220幅10

4、24 * 768的真彩色图像，假设将这些图像以位图形式保存 在CD光盘上(一张CD光盘的容量按600M计算)，大约需要()张CD光盘。A. 1 B. 10 C. 100 D. 1000 E. 10000二、不定项选择题(共10题，每题L5分，共计15分。多项选择或少选均不得分)。10 .设A = true, B二false, C二false, D = true,以下规律运算表达式值为真的有()。A. (A B A )V(CD A ) B. (A B A ) C V ) D A C. AA(B C V )D V )D. (AA(BC V )D V E. (A B V )A(CD V )12.(3

5、725%+(B)i6的运算结果是()oA. (3736)8B. (2O22)1oC.2 D. (3OO6)1oE. (7E0)1613.二叉树T的宽度优先遍历序列为ABC DEFG HL A是C的父结点，D是G的父结点，F是I的父结点，树中全部结点的最大深度为3 (根结点深度设为0),可知E 的父结点可能是()。A. A B. B C. C D. D E. F14.设栈S的初始状态为空，元素a, 人孰(1,孰8依次入栈，以下出栈序列不行能消灭的有 ()OA. a, b, c, e, d, f, g B. b, c, a, f, e, g, d C. a, e, c, b, d, f, gD.

6、d, c, f, e, b, a, g E. g, e, f, d, c, b, a15.以下外设接口中可以通过无线连接的方式连接设备的是)。A. USB 2.0高速版B.红外C蓝牙D.串口E.IEEE 802.11g无线网卡.处理器A每秒处理的指令数是处理器B的2倍。某一特定程序P分别编译为处理器A 和处理器B的指令，编译结果处理器A的指令数是处理器B的4倍。程序P的算法时间 简单度为0（空），假设处理器A执行程序P时能在一小时内完成的输入规模为n,那么处理器B执行程序P时能在一小时内完成的输入规模为（）。A.4*nB.2*nC.nD. n/2E,n/4.以下哪个（些）不是计算机的输出设备（

7、）。A.鼠标B.显示器C.键盘D.扫描仪E.绘图仪.以下断电之后将不能保存数据的有（）。A.硬盘B.存放器C.显存D.内存E.高速缓存.以下活动中属于信息学奥赛系列活动的是）。A. NOIP B. NOI C. 101 D.冬令营E.国家队选拔赛.以下关于高级语言的说法正确的有（）。A. Ada是历史上的第一个高级语言Pascal和C都是编译执行的高级语言B. C+是历史上的第一个支持面对对象的语言D.编译器将高级语言程序转变为目标代码E.高级语言程序比汇编语言程序更简洁从一种计算机移植到另一种计算机上.问题求解（请在空格处填上答案，每空5分，共计10分）1 .将数组32, 74, 25, 5

8、3, 28, 43, 86, 47中的元素按从小到大的挨次排列，每次可以交换任 意两个元素，最少需要交换次。2 .取火柴玩耍的规章如下：一堆火柴有N根，A、B两人轮番取出。每人每次可以取1根或 2 根，最先没有火柴可取的人为败方，另一方为胜方。假设先取者有必胜策略那么记为1, 先取者没有必胜策略记为0。当N分别为100, 200, 300, 400, 500时，先取者有无必胜 策略的标记挨次为（回同意为一个由0和/或1组成的字符串）。三 .阅读程序（共4题，每题8分，共计32分）vara, b, c, p, q : integer;r : array0.2 of integer;beginre

9、ad（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 * （r0 - 300）;if （3 * q - p mod 3 = r0） and （r 2 = r 2） thenr 1 := rr0 div p mod 2else r1 := q mod p;writein（r0 - r1）;end.输入：100 7 3输出：1. vara : array 1. . 50 of integer;h, i, sum : integer;procedure work（p, r: intege

10、r）;varj, temp : integer;beginif p = ar then begin inc (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);for i := 1 to n do read(ai);work(lz n);for i := 1 to n - 1 do sum := sum + abs(ai + 1 - ai); writei

11、n(sum);end.输入：10 23 435 12 345 3123 43 456 12 32 -100 输出：2. var str : string;len, i, 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 str i - 1) and (strj mmin) then mmin := str j;inc (nchr ord (str j )

12、- ord (z,a,z);end;dec (nchrord(mmin) inc (nchrord(stridec (nchrord(mmin) inc (nchrord(striord (a);1 ) - ord(a);nchri do ord(a);write(mmin);for i := 0 to 25 do for j := 1 to write(chr (i + writein;输入：zzyzcccbbbaaa输出：3. . varn : longint;function g (k : longint) : longint;beginif k = k then break;num :

13、=；end;if then isok := trueelse isok := false;end;beginreadln(n, k);right := 0;for i := 1 to n do beginreadln(leni);if right len i then right : = len i ; end;inc (right);；while right do beginmid := (left + right) div 2;if then right := midelse left := mid;end;writein (left);end.1, N叉树题目描述：我们都了解二叉树的先根

14、遍历，中根遍历和后根遍历。当知道先根遍历的结果和中根遍历结果的时候，我们可以唯一确实定二叉树；同样的，假设知道了后根遍历的结果和中根遍 历结果，二叉树也是唯一确定的。但是假设只知道先根遍历和后根遍历的结果，二叉树就不 是唯一的了。但是我们可以计算满足条件的不同二叉树一共有多少个。这不是一个很困难的 问题，略微简单一点，我们把这个问题推广到N叉树。我们用小写英文字母来表示N 叉树的结点，不同的结点用不同的字母表示。比方，对 于4叉树，假设先根遍历的结果是abdfgc,后根遍历的结果是dfgbca,那么我们可以 得到6个不同的4叉树1如以下列图)。小detg输入：输入数据包括3行。第一行是一个正整

15、数N (2 W N W 20),表示我们要考虑N叉树。其次行和第三行分别是两个字符串序列，分别表示先根遍历和后根遍历的结果。 输出：输出不同的N叉树的数目。题目中给的数据保证得到的结果小于231O输入样例：4abdefgcdefgbca输出样例：6程序：varstrlA str2 : string; N,len : integer;com : array0.100, 0 . . 100 of longint;function getcom(x, y : integer) : longint;beginif (y = 0) or (x = y) then else if comxy 0 then

16、 getcom := comxyelse begincomx y := getcom(x - 1, y) + ;getcom := comxy;end;end;function count(a, b, c : integer) : longint;varsum : longint;k, 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);s

17、um := 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.第十一届全国青少年信息学奥林匹克联赛初赛提高组参考答案一.单项选择题（共10题，每题1.5分，共计15分。每题有且仅有一个正确答案.）。二不定项选择题共10题 每题1.5分，共计15分。多项选择或少选均不得分。三.问题求解（共2题，每题5分，共计10分）1

18、 .答：52 .答：11011四.阅读程序（共4题，每题8分,共计32分）（1）程序的运行结果是： 7452（2）程序的运行结果是：3223（3）程序的运行结果是： zzzaaabbbcccy（4）程序的运行结果是：31五.完善程序（前5空，每空2分，后6空，每空3分，共28分）pascal语言1.(1) num + leni div t(2) num = k(3) left := 0(4) left + 1(5) not isok(mid) (或者 isok(mid) = false)2,.(1) getcom := 1(2) getcom(x - 1, y - 1)(3) s + t - p + 1(4) inc(t)(或者 t := t + 1)(5) sum 1, len, 1