noip信息学联赛2019模拟试卷(四)

25届ccfnoip2019普及组初赛c++试题卷1第二十五届全国青少年信息学奥林匹克联赛初赛（普及组C++语言试题）竞赛时间：2019年10月13日14:30~16:30选手注意：试题纸共有7页，答题纸共有2页，满分100分。请在答题纸上作答，写在试题纸上一律无效。不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料一．单项选择题（共20题，每题1.5分，共计30分。每题有且仅有一个正确答案.）1.(2019)12+(9102)16=：A：（1001100110100111）2B：（116643）8C：（9DA7）16D：（9DA5）162.图灵奖是信息学的最高奖项，以下获得过图灵奖的中国人是：A：姚期智B：姚期辉C：马云D：马化腾3.国际信息学奥林匹克竞赛缩写是：A：NOIB：CTSCC：IOID：ACM4.2.0E-3=A：2000B：0.002C：8D：-20005.计算20196&1=A：1B：31C：0D：20196.使用二分算法在一个大小为n（n=4）中寻找第4大的整数所需的时间复杂度为：A：O（1）B：O（nlogn）C：O（logn）D：O（n）7.若设函数f(x)=1（x=1,x=2）3*f(sqrt(x))+f(x/2)+1（x2）当x=19时，计算过程中共调用的f（x）个数是（包括调用f（1），f（2））：注释：此处运算默认下取整A：3B:4C:5D:68.上题函数中f（19）=A：30B:37C：36D:399.第7题中的函数值不可以用以下哪种方法求得：A:动态规划B：分治C：递推D：递归搜索10.以下部件损坏，主机仍可正常工作的是：A：内存条B：硬盘C：显示屏D：显卡11.对一下数据{1000,2,3,5,4,1,5000}进行冒泡排序，共计需交换次数为：A：5B：10C：15D：1812.如果将人体比作计算机，那么人体的记忆中枢相当于以下计算机部件的：A：运算器B：中央处理器C：控制器D：内存13.以下示意图中的数据结构不属于选项中的哪个数据结构：A：大根堆B：无向图C:连通图D：完全二叉树25届ccfnoip2019普及组初赛c++试题卷214.dos、unix和windows的共同点是：A：都是硬件B：都是联网系统软件C：都是应用软件D：都已经过时15.html是一种高级语言，以下操作可以查看html代码的是：A：打开浏览器按F11B：运行html.exeC：无法查看D：打开浏览器按F1216.以下关于计算机病毒的说法正确的是：A：防火墙可以防止感染B：通过生物传播C：一旦感染无法破解D：计算机一次感染终身免疫17.c++语言“实数下取整”操作是：A：(int)xB：float(x)C：floor(x)D:ceil(x)18.一棵n层二叉树的最多节点数减去最少节点数等于：A:2*nB:2n-nC:n2-nD:n*log2(n)-n19.现给出以下程序：#includebits/stdc++.husingnamespacestd;inti,x;inta[11]={0,10,2,3,5,14,8,20,1,7,-1};intmain(){cinx;sort(a+1,a+11);for(i=1;i=10;i++)if(a[i]=x)break;coutiendl;}问若将此程序的输入输出看做函数，则此函数的图像不经过点：A：（0,2）B：（2,4）C：（11,9）D：（21,11）20.上题程序划线部分可替换为：A：coutupper_bound(a,a+10,x)endl;25届ccfnoip2019普及组初赛c++试题卷3B：coutupper_bound(a+1,a+11,x)endl;C：coutupper_bound(a+1,a+11,x)-aendl;D:coutlower_bound(a+1,a+11,x)-aendl;二．问题求解（共2题，每题5分，共计10分）1.五位数的卡布列克运算循环节为：注释：卡布列克运算为将一数的所有数位数字重新排列可得的数的最大值减最小值（高位补零），保证有循环节，本题有三个答案，写出一个即得5分，各数字用逗号隔开。2.对于一棵勾股树（任一直角三角形三边均有与边长等长正方形重合，任一直角三角形直角边为边长的正方形均与另一直角三角形斜边重合，如图），设所有最小正方形边长为a[i](1≤i≤∞)，则最大正方形面积为（1≤i≤∞）三．阅读程序写结果（共4题，每题8分，共计32分）1.#includebits/stdc++.husingnamespacestd;intmain(){inta,b,c;doubleans;cinac;if(!c11==c)c-=1;b=(a*c)/2;ans=sqrt(pow(b,3));printf(%0.2f,ans);return0;}输入：13输出：2.25届ccfnoip2019普及组初赛c++试题卷4#includeiostream#includealgorithmusingnamespacestd;intn,a[101],i;intmain(){cinn;for(i=1;i=n;i++)cina[i];sort(a+1,a+n+1);n=unique(a+1,a+n+1)-a-1;coutnendl;for(i=1;i=n;i++)couta[i]'';coutendl;return0;}输入：102040326740208930040015输出：3.#includebits/stdc++.husingnamespacestd;longlongo=1,minn=10000000,m;structpa{longlongs;longlongj;stringn;longlongcost;};pap[10005];intmain(){while(cinp[o].sp[o].jp[o].n)o++;for(inti=1;io;i++){for(intg=1;go;g++)p[i].cost+=abs(p[i].j-p[g].j)*p[g].s;if(p[i].cost=minn){minn=p[i].cost;m=i;}25届ccfnoip2019普及组初赛c++试题卷5}coutp[m].np[m].costendl;return0;}输入：79289Vladivostok58523Chabarovsk35184Irkutsk82213Yalutorovsk100Moscow输出：4.#includebits/stdc++.husingnamespacestd;inta[500001],b[500001],i,n,A,B,l,r,mid;boolcheck(intmid){intii,s=0;memcpy(b,a,sizeof(a));for(ii=1;ii=n;ii++)b[ii]-=mid*A;for(ii=1;ii=n;ii++)if(b[ii]0)s+=(int)ceil((double)b[ii]/B);returns=mid;}intmain(){scanf(%d%d%d,&n,&A,&B);for(i=1;i=n;i++)scanf(%d,&a[i]);l=0;r=500010;while(lr){mid=(l+r)/2;if(check(mid))r=mid;elsel=mid+1;}printf(%d\n,l);}输入：102391031274815924输出：四．完善程序(前8空，每空2分，后4空，每空3分，共28分)1.逆序对：逆序对的定义是：对于给定的一段正整数序列，逆序对就是序列中aiaj25届ccfnoip2019普及组初赛c++试题卷6且ij的有序对。逆序对可以用冒泡排序和归并排序求得。试完善以下冒泡排序程序段与归并排序程序。s=0;for(i=1;i=n;i++)for(j=1;j=（1）;j++)if(a[j]a[j+1]){（2）;++s;}coutsendl;//////////////////////////////////////////////////////////#includebits/stdc++.husingnamespacestd;longlonga[500001],b[500001],s,n;voidguibing(longlongl,longlongr){if(r-l==0)return;if(r-l==1){if(a[r]a[l]){swap(a[r],a[l]);++s;}return;}longlongmid=（3）,i=l,j=mid+1,k=l;guibing(l,mid);（4）;while(（5）)if(a[i]a[j]){s+=（6）b[k]=a[j];++k;++j;}else{b[k]=a[i];++k;++i;25届ccfnoip2019普及组初赛c++试题卷7}for(;i=mid;i++)b[k++]=a[i];for(;j=r;j++)b[k++]=a[j];for(k=l;k=r;k++)（7）;}intmain(){longlongi;scanf(%ld,&n);for(i=1;i=n;i++)scanf(%ld,&a[i]);guibing(1,n);printf(%ld\n,s);return0;}2.石子合并：在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.#includebits/stdc++.husingnamespacestd;constintMaxn=1000+10;intt[Maxn],dp1[Maxn][Maxn],dp2[Maxn][Maxn];intmain(){intn;cinn;for(inti=1;i=n;++i){cint[i];t[（1）]=t[i];}for(inti=2;i=2*n;++i)t[i]+=t[i-1];memset(dp1,0,sizeof(dp1));for(inti=2*n-1;（2）)for(intj=（3）;j=2*n;++j){intb=2147483647;for(intk=i;kj;++k){dp1[i][j]=max(dp1[i][j],dp1[i][k]+dp1[k+1][j]+t[j]-t[i-1]);b=min(b,（4）);}dp2[i][j]=b;}intmax0=0,min0=10000000;for(inti=1;i=n;++i){max0=max(（5）);min0=min(min0,dp2[i][i+n-1]);}coutmin0endlmax0endl;return0;}CCFNOIP2019普及组（C++语言）参考答案与评分标准25届ccfnoip2019普及组初赛c++试题卷8一、单项选择题（共20题，每题1.5分，共计30分）12345678910CACBADDBBC11121314151617181920BDACDACBBD二、问题求解（共2题，每题5分，共计10分）1.答案为：（任答其一即可）①59994,53955②：74943,62964,71973,83952③：61974,82962,75933,639542.a[1]2+a[2]2+……+a[∞]2或∑a[i]2三、阅读程序写结果（共4题，每题8分，共计32分）1.1.002.81520324067893004003．Yalutorovsk1121254．6四、完善程序（第1题，每空2分，第2题，每空3分，共计28分）（说明：以下各程序填空可能还