附上汇总帖历年CSP-J初赛真题解析 | 汇总单项选择第1题在8位二进制补码中10101011表示的数是十进制下的 。A.43B.-85C.-43D.-84【答案】B【解析】正数的原码、反码和补码均相同最高位为符号位0表示正数1表示负数。负数的反码原码符号位不变其他位取反负数的补码反码1计算得到原码为11010101为-85第2题计算机存储数据的基本单位是 。A.bitB.ByteC.GBD.KB【答案】B【解析】2013年就讲过基本单位是字节最小单位是bit第3题下列协议中与电子邮件无关的是 。A.POP3B.SMTPC.WTOD.IMAP【答案】C【解析】WTO是世界贸易组织POP3 Post office Protocol 3第4题分辨率为800x600、16位色的位图存储图像信息所需的空间为 。A.937.5KBB.4218.75KBC.4320KBD.2880KB【答案】A【解析】800 * 600 * 16 / 8 / 1024 937.5KB第5题计算机应用的最早领域是 。A.数值计算B.人工智能C.机器人D.过程控制【答案】A【解析】计算机常识最早就用于计算导弹射击路线第6题下列不属于面向对象程序设计语言的是 。A.CB.CC.JavaD.C#【答案】A【解析】2014年介绍过面向对象程序设计语言C语言没有对象单身狗第7题NOI的中文意思是 。A.中国信息学联赛B.全国青少年信息学奥林匹克竞赛C.中国青少年信息学奥林匹克竞赛D.中国计算机协会【答案】B【解析】信奥常识NOI National Olympiad in Informatics第8题2017年10月1日是星期日1999年10月1日是 。A.星期三B.星期日C.星期五D.星期二【答案】C【解析】非闰年365天365%71每过一年相当于星期中过了一天闰年366天366%72每过一年相当于星期中过了两天。1999年-2017年一共18年5个闰年13个非闰年相当于星期中过了23天23%72。星期五过2天是星期日选C第9题甲、乙、丙三位同学选修课程从4门课程中甲选修2门乙、丙各选修3门则不同的选修方案共有 种。A.36B.48C.96D.192【答案】C【解析】甲从4门中选2门C 4 2 C_{4}^{2}C42​乙从4门中选3门C 4 3 C_{4}^{3}C43​丙从4门中选3门C 4 3 C_{4}^{3}C43​6*4*496第10题设G是有n个结点、m条边(n≤m)的连通图必须删去G的 条边才能使得G变成一棵树。A.m-n1B.m-nC.mn1D.n-m1【答案】A【解析】一棵树n个节点则有n-1条边。m - x n - 1得到x m - n 1第11题对于给定的序列{ak}我们把(i, j)称为逆序对当且仅当ij且aiaj。那么序列172354的逆序对数为 个。A.4B.5C.6D.7【答案】B【解析】(7,2) (7,3) (7,5) (7,4) (5,4)共5对第12题表达式a ∗ ( b c ) ∗ d a*(bc)*da∗(bc)∗d的后缀形式是 。A.a b c d ∗ ∗ abcd**abcd∗∗B.a b c ∗ d ∗ abc*d*abc∗d∗C.a ∗ b c ∗ d a*bc*da∗bc∗dD.b c ∗ a ∗ d bc*a*dbc∗a∗d【答案】B【解析】正常的运算对应中缀形式可以画出二叉树写出后续遍历结果即后缀形式选B第13题向一个栈顶指针为hs的链式栈中插入一个指针s指向的结点时应执行 。A.hs-nexts;B.s-nexths; hss;C.s-nexths-next; hs-nexts;D.s-nexths; hshs-next;【答案】B【解析】先把栈顶变成s所指向的节点即s-next hs。再把指针s变为栈顶即hs s第14题若串S“copyright” 其子串的个数是 。A.72B.45C.46D.36【答案】C【解析】(19) * 9 / 2 45再加1个空串第15题十进制小数13.375对应的二进制数是 。A.1101.011B.1011.011C.1101.101D.1010.01【答案】A【解析】小数部分乘2取整剩余部分继续乘2取整。0.3750.250.1251/41/8第16题对于入栈顺序为abcdefg的序列下列 不可能是合法的出栈序列。A.abcdefgB.adcbegfC.adbcgfeD.gfedcba【答案】C【解析】C错误是因为不可能b先出c再出第17题设A和B是两个长为n的有序数组现在需要将A和B合并成一个排好序的数组任何以元素比较作为基本运算的归并算法在最坏情况下至少要做 次比较。A.n 2 n^2n2B.nlognC.2nD.2n-1【答案】D【解析】一共2n个数最坏情况需要比较2n-1次最后一个数不用比较第18题从 年开始 NOIP竞赛将不再支持Pascal语言。A.2020B.2021C.2022D.2023【答案】C【解析】NOI常识第19题一家四口人至少两个人生日属于同一月份的概率是 假定每个人生日属于每个月份的概率相同且不同人之间相互独立。A.1/12B.1/144C.41/96D.3/4【答案】C【解析】至少两人属于同一月份的方面是四个人的生日都不在同一月份概率为( 12 ∗ 11 ∗ 10 ∗ 9 ) / ( 12 ∗ 12 ∗ 12 ∗ 12 ) 55 / 96 (12*11*10*9)/(12*12*12*12)55/96(12∗11∗10∗9)/(12∗12∗12∗12)55/96答案为41/96第20题以下和计算机领域密切相关的奖项是 。A.奥斯卡奖B.图灵奖C.诺贝尔奖D.普利策奖【答案】B【解析】2015年已经考过计算机届最高奖项是图灵奖问题求解第21题一个人站在坐标(0, 0)处面朝x轴正方向。第一轮他向前走1单位距离然后右转第二轮他向前走2单位距离然后右转第三轮他向前走3单位距离然后右转…他一直这么走下去。请问第2017轮后他的坐标是 。【答案】1009 1008【解析】第0轮(0,0)第1轮(1,0)第2轮(1,-2)第3轮(-2,-2)第4轮(-2,2)第5轮(3,2)第6轮(3,-4)第7轮(-4,-4)第8轮(-4,4)第9轮(5,4)第10轮(5,)第11轮(-2,-2)第12轮(-2,2)每4轮行走方向一样2017%41第2017轮(1009,1008)第22题如下图所示共有13个格子。对任何一个格子进行一次操作会使得它自己以及与它上下左右相邻的格子中的数字改变(由1变0或由0变1)。现在要使得所有的格子中的数字都变为0至少需要 次操作。【答案】3【解析】自己模拟第一次改变最顶上的1第二次改变右边倒数第2个0第三次改变中间的1阅读程序#includeiostreamusingnamespacestd;intmain(){intt[256];string s;inti;cins;for(i0;i256;i)t[i]0;for(i0;is.length();i)t[s[i]];for(i0;is.length();i)if(t[s[i]]1){couts[i]endl;return0;}coutnoendl;return0;}第23题输入xyzxyw输出 【答案】z【解析】程序的功能是输出第一个只出现1次的字母7845690-23978-6#includeiostreamusingnamespacestd;intg(intm,intn,intx){intans0;inti;if(n1)return1;for(ix;im/n;i)ansg(m-i,n-1,i);returnans;}intmain(){intt,m,n;cinmn;coutg(m,n,0)endl;return0;}第24题输入7 3输出 【答案】8【解析】g(7,3,0)g(7,2,0)g(6,2,1)g(5,2,2)g(7,2,0)g(7,1,0)g(6,1,1)g(5,1,2)g(4,1,3)4g(6,2,1)g(5,1,1)g(4,1,2)g(3,1,3)3g(5,2,2)g(3,1,2)1所以g(7,3,0)8求排列组合的题mxm的方案数#includeiostreamusingnamespacestd;intmain(){string ch;inta[200];intb[200];intn,i,t,res;cinch;nch.length();for(i0;i200;i)b[i]0;for(i1;in;i){a[i]ch[i-1]-0;b[i]b[i-1]a[i];}resb[n];t0;for(in;i0;i--){if(a[i]0)t;if(b[i-1]tres)resb[i-1]t;}coutresendl;return0;}第25题输入1001101011001101101011110001输出 【答案】11【解析】012345678910111213141516171819202122232425262728ch1001101011001101101011110001a[ ]01001101011001101101011110001b[ ]01112334456667889101011111213141515151516t1212111010109988876665554433333210res1112131415b数组是在算从头到i的“1”的个数前缀和res为a数组中1的个数t是从i到尾的“0”的个数后缀和。程序的目的是将字符串劈成两半前一半统计1的个数后一半统计0的个数计算什么时候得到的两者的个数最小。#includeiostreamusingnamespacestd;intmain(){intn,m;cinnm;intx1;inty1;intdx1;intdy1;intcnt0;while(cnt!2){cnt0;xxdx;yydy;if(x1||xn){cnt;dx-dx;}if(y1||ym){cnt;dy-dy;}}coutx yendl;return0;}第26题输入14 3输出1 输入22017 1014输出2 【答案】1 3 和2017 1【解析】xydxdycnt1111022110331-10/142-1-10/131-110/122-110131-10/1/2两个if语句都成立才能结束while循环。(n-1)和(m-1)的最小公倍数。2017和2014的最小公倍数是2016 * 1013即x走1013次y走2016次则1013为奇数所以x到了20172016为偶数所以y到了1完善程序快速幂请完善下面的程序该程序使用分治法求x p m o d m x^p\ mod\ mxpmodm的值。输入三个不超过10000的正整数xpm。输出x p m o d m x^p\ mod\ mxpmodm的值。提示若p为偶数x p ( x 2 ) p / 2 x^p(x^2)^{p/2}xp(x2)p/2若p为奇数x p x ∗ ( x 2 ) ( p − 1 ) / 2 x^px*(x^2)^{(p-1)/2}xpx∗(x2)(p−1)/2。#includeiostreamusingnamespacestd;intx,p,m,i,result;intmain(){cinxpm;result__1__;while(__2__){if(p%21)result__3__;p/2;x__4__;}cout__5__endl;return0;}第27题1处应该填 【答案】1【解析】乘法的累乘器初始值为1第28题2处应该填 【答案】p0【解析】按照快速幂的公式最后一个数算到1次方第29题3处应该填 【答案】result*x%m【解析】如果是奇数需要保留底数第30题4处应该填 【答案】x*x%m【解析】最后一定会有个数的1次方出现所以这里只是x*x%m第31题5处应该填 【答案】result【解析】仅需输出答案切割绳子有n条绳子每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割但不可以连接。现在要从这些绳子中切割出m条长度相同的绳段求绳段的最大长度是多少。输入第一行是一个不超过100的正整数n第二行是n个不超过10 6 10^6106的正整数表示每条绳子的长度第三行是一个不超过10 8 10^8108的正整数m。输出绳段的最大长度若无法切割输出Failed。#includeiostreamusingnamespacestd;intn,m,i,lbound,ubound,mid,count;intlen[100];// 绳子长度intmain(){cinn;count0;for(i0;in;i){cinlen[i];__1__;}cinm;if(__2__){coutFailedendl;return0;}lbound1;ubound1000000;while(__3__){mid__4__;count0;for(i0;in;i)__5__;if(countm)uboundmid-1;elselboundmid;}coutlboundendl;return0;}第32题1处应该填 【答案】count len[i]【解析】计算所有线段的总长第33题2处应该填 【答案】countm【解析】如果所有线段加起来的总长度小于m那么即使按照最小的长度1来切割也无法切出m段第34题3处应该填 【答案】lboundubound【解析】l和r重合时才退出循环第35题4处应该填 【答案】(lboundubound1)/2【解析】如果l3r4且3就是正解那么应该希望mid 4否则就会陷入死循环第36题5处应该填 【答案】count len[i]/mid【解析】计算在mid长度下可以切出的总段数