信息学竞赛真题.docx
一'单项选择题(共15题，每虺1.S分,共计22.5分：每题有且仅有一个正确选项)1 .从()年起先，NOIP竟寤将不再支持Pasca1.语言.A.2020B.2021C.2022D.20232 .在8位二进制补码中，1010MnI表示的数是十进制下的().A.43B.-85C.-43D.-843 .辨别率为1600x900、16位色的位图，存储图像信息所需的空间为()，A.2812.5KBB.4218.75KBC.4320KBD.2880KB4.2017年10月T日是星期日，1949年10月1日是()。A.星期三B.星期HC.星期六D.星期二，设G是有n个结点、m条边(nWm)的连通图，必需删去G的()条边，才能使得G变成一棵树.A.m-n*1.B.m-C.m+n+1D.n-m+16 .若某算法的计算时辰表示为递推关系式：T(N)=2T(N2"NI"NT(I)=I则该算法的时间困难度为().A.O(N)B.ON1.ogN)CQ(N1.og2N)D.O(N2)7 .表达式a(b+c)d的后级形式是0，A.abcd*B.abc+d,C.abc+*dD.b+c*ad&由四个不同的点构成的简洁无向连通图的个数是().A.32B.3SC.38D.419 .将7个名额分给4个不同的班级，允许有的班级没出名额，有()种不同的安排方案.A.60B.84C.96D.12010 .f0>0,f1.-1.,fn+1.1.=(fh+ft11-1.W,则随岩i的增大，4将接近及().A.V2B.2/3D.111.设A和8是两个长为n的有序数组，现在须要将A和B合并成一个排好序的数组，请问任何以元素比较作为基本运算的归并算法最坏状况下至少要做()次比较，A.n2B.n1.ogC.2nD.2n-112.在n(n>=3)枚现币中有一枚质信不合格的硬币(质从过轻或灰量过理)，假如只有架天平可以用来称Hi且林Hi的硬币数没有网制，下面是找出这枚不合格的硬币的算法。清把ac三行代码补全到算法中。a.AXUYb.AZC.11A算法Coin(An)1. kn/32. 将A中硬市分成XXZ三个集合，使得IX1.=IY1.=k/Z=112k3. ifW(X)W(Y)/W(X),W(Y)分别为X或Y的1E量4. then5. e1.se6. 7. if>2thengoto18. ifn=2then任取A中T枚硬币及拿走硬币比较,若不等，则它不合格;若相等，则A中剩下的硬币不合格9. ifn=1.thenA中硬币不合格正确的埴空依次是().A.b,c,aB.c,b,aC.c,a,bD.a,b,c13.在正实数内成的数字.角形排列形式如图所示，第一行的数为a1.1.：其次行的数从左到方依次为a21,a22;第n行的数为an1.,an2,，ann。从a11起先，每一行的散aij只有两条边可以分别通向卜一行的两个数a(i+1.)j和a(i+1.)(j÷1.),用动态规划算法找出一条从a1.1.向卜通到an1.,a112,ann中某个数的路径,使得该路径上的数之和达到股大.令C同是从a1.1.到aij的路径上的数的最大和,并且Ci,0三q0JJ=0,则Ci,j)=().A.maxC1.-1.,j-1.1.C1.-1.JHaijB.C(-1.J-1.+c1.-1.JC.maxCi-1.,j-1.1.C(i-1.,j1.+1.D.maxCi,j-1.,C(i-1.,jaij14 .小明要去南美洲旅谢一共乘坐三趟航班才能到达H的地，其中第1个航班准点的概率是0.9.第2个航班准点的概率为0.8.第3个航班准点的概率为0.9.假如存在第i个(i1.,2)航班晚点，第i+1个航班准点，则小明将赶不上第i+1个航班，旅行失败：除了这种状况，其他状况下旅行都能胜利,请问小明此次旅行胜利的概率是().A.0.5B,0.648C.0.72D.0.7415 .快乐喷球：儿童游乐场有个嬉戏叫“快乐喷球”，正方形场地中心能不断喷出彩色乒乓球，以场地中心为圆心还有一个切轨道，轨道上有一列小火车在匀速运动，火车有六节车厢”假设乒乓球等概率落到正方形场地的年个地点，包括火车车厢。小架发玩这个域戏时，只能坐在同一个火车车厢里,可以在自己的车厢里捡落在该车照内的全部乒乓球,每个人每次婚戏有三分钟时间，则一个小学友独自玩一次螭戏期空可以得到()个兵乓球.假设乒乓球喷出的速度为2个/杪，好节车剂的面积是整个场他面积的1/20。A.60B.108C.18D.20二、不定项选择Sfi(共SSfi抵阳1.5分，共计7.5分：每SS有一个或多个正确选J,多选或少选均不得分)1 .以下排序算法在最坏状况下时间困难度最优的有().A.出泡排序B.快速排序C.归并排序D.堆排序2 .对于入校依次为a,b,c,de,f,g的序列，卜列()不行能是合法的出栈序列，A.a,b,c,dze,f,gB.a,d,c,b,e,gjC.a,d,b,c,g,f,eD.g,f,e,d,c,b,a3,下列算法中，()是麹定的排序算法。A.快速排序B.推排序C.希尔排序D.插入排序4 .以卜是面时对象的高级语言的是().A.汇第谙=B.C*÷C.FortanD.Java5 .以下和计算机领域亲密相关的奖项是(),A.奥斯卡奖B.图灵奖C.诺贝尔奖D,工选奖何超求解共2题.每超5分,共计10分1 .如图所示，共有13个格子。对(E何一个格子进行一次操作，会使得它自己以及及它上下左右相邻的格子中的数字变更(由1变0.或用0变1).现在要使得全部的格子中的数字都变为0.至少须要3次操作.2 .如图所示，A到8是连通的，©设删除一条细的边的代价是1,删除一条粗的边的代价是2.要让A、B不连通,最小代价是4(2分).最小代价的不同方案数是9(3分).(II要有条删除的边不同,就是不同的方案)四、阅读程序后结果<4Ig>19®8分，共计32分)1.Minc1.udeusingnamespacestd;intg(1.ntm,IntnfInt×)intans三0;inti;1.f(n=1)return1;for(i=x;i<=mn;i*+)ans+=g(m-i,n-1.zi);intmain()int1.m,n;cin»m»cout«g(m,nr0)«end1.;returnO;)输入：84输出:152.Itinc1.udeusingnamespacestd;intmain()intzifj,×,yzn×,ny;inta(401140;for(I=0;i<40;1+)for(j=0;j<40;j÷+)a(i)UI三0;c1.n»n;y=0;x=n-1;=2*n-1.;for(i1；i<n*n;i*÷)a(y1.M=;ny=(y-1.+n)%n;n(x÷1.)%n;if(y=0&&x=n-1.)any11nxj!=0y=v÷1.;eKey=n;x=nx;)for(j三(j<nj)cout«aO11j1.<<cout«end1.;returnO;输入:3输出:172418153.Minc1.udeusingnamesacestd;intnfs,a(100005j.U1.OooO5,i;voidmergesort(int1.fintr)If(I=r)return;intmid=(I÷r)/2;intpI;inti=I;intj=mid+1：mergesort(I,mid);mergesort(mid1.zr);whi1.e(I<=mid&&j<=r)if(aU<a(IJKs*midi÷1.;Up)-a(j;p÷+;肚+;)e1.se(t1.P1.=a1.1.;P+；i+；)whi1.e(I<=mid)t(=a|i)；p+*;i+；)whi1.e(j<三r)(t(P1.=aj1.:p+;)+；)for(i=1.;i<=r;i+*|aN=ti;)intmain()cin»n;for(i=1;i<=n;i+)cin>>a川；mergesort(1,n);cout«s«end1.;returnO;)输入：263451输出：84.Kinc1.udeusingnamespace$td；intmain()int,m;c1.n»n»m；intx=1;inty=1.;intd×=1;intdy=1;intct=O;whi1.e(ent!2)(ent=O;x=x+d×y=V+dv;if(x=1I1.x=n)+ent;dx=YHif(V=1I1.y=m)+ent;dy=-dy;)cout«x«""«y«end1.;returnO;输入1:43输出1:13(2分)输入2:20171014输出2:2017113分)输入3:987321输出3:1321(3分)五、完善程序(共2题，每卷14分，共计28分)1.大整数除法：给定两个正整数P和q,其中P不超过IO1.ooq不超过100O00.求P除以q的商和余数。(第一空2分，其余3分)输入：第一行是P的位数n.其次行是正整数p第三行是正整数q.输出：两行，分别是P除以q的商和余数，"Inc1.udeusingnamespacestd;intp100;intn,irqrrest;charc;ntmain()cin»n;for(i三0J<n;i)cin»c;PN=C-o)cin»q;rest=pO;i=1.；whi1.e(rest<q&&i<n)rest三rest410+pi;i÷+;)if(rest<q)cout«O<<end1.;e1.secout«rest/q;whi1.e(i<)rest«rest%q*10÷pi;i+；cout<<rest/q;)cout«ed1.;)cout«rest%q«endI；returnO;最长路径：给定一个有向五环图.短条边长度为3求图中的最长路径长度.（第五空2分.其余3分）输入；第一行是结点数n（不超过100）和边数m,接下来m行，出行两个整数a,b,表示从结点a到结点b有一条有向边。结点标号从0f（n-1.）输出：最长路径长度.提示：先进行拓扑排序,然后根掘拓扑排序计"最K路径.W1.nc1.udeusingnamespacestd;intn,mzi,j,a,b,head,tai1.,ans;intgraph1.U:/用邻接矩阵存储图ntdegree100;/记录短个站点的入度intIenI1.OO;记录以各结点为终点的角长路径长枝intqueue(100);/存放拓扑排序结果intmain()cin»n»
