《noip信息学联赛2019模拟试卷(四)解析.pdf》由会员分享，可在线阅读，更多相关《noip信息学联赛2019模拟试卷(四)解析.pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、25 届 ccf noip 2019 普及组初赛 c+试题卷第二十五届全国青少年信息学奥林匹克联赛初赛第二十五届全国青少年信息学奥林匹克联赛初赛（普及组 C+语言试题）竞赛时间：2019 年 10 月 13 日 14:3016:30选手注意：试题纸共有 7 页，答题纸共有 2 页，满分 100 分。请在答题纸上作答，写在试题纸上一律无效。不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料一 单项选择题（共2020题，每题1.51.5分，共计3030分。每题有且仅有一个正确答案.）1.(2019)12+(9102)16=：A：（1001100110100111）2B：（1166
2、43）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时，计算过程中共调用
3、的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.以下示意图中的数据结构不属于不属于选项中的哪
4、个数据结构：A：大根堆B：无向图C:连通图D：完全二叉树825 届 ccf noip 2019 普及组初赛 c+试题卷14.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:cei
5、l(x)18.一棵n层二叉树的最多节点数减去最少节点数等于：A:2*nB:2n-nC:n2-nD:n*log2(n)-n19.现给出以下程序：#includeusing namespace std;int i,x;int a11=0,10,2,3,5,14,8,20,1,7,-1;int main()cinx;sort(a+1,a+11);for(i=1;i=x)break;coutiendl;问若将此程序的输入输出看做函数，则此函数的图像不经过点：A：（0,2）B：（2,4）C：（11,9）D：（21,11）20.上题程序划线部分可替换为：A：coutupper_bound(a,a+10,x
6、)endl;825 届 ccf noip 2019 普及组初赛 c+试题卷B：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 2题，每题5 5分，共计1010分）1.五位数的卡布列克运算循环节为：注释：卡布列克运算为将一数的所有数位数字重新排列可得的数的最大值减最小值（高位补零），保证有循环节，本题有三个答案，写出一个即得5分，各数字用逗号隔开。2.2.对于一棵勾股树（任一直角三角形三边均有与边长等长正方形重合，任一直
7、角三角形直角边为边长的正方形均与另一直角三角形斜边重合，如图），设所有最小正方形边长为ai(1i)，则最大正方形面积为（1i）三阅读程序写结果（共4 4题，每题8 8分，共计3232分）1.#includeusing namespace std;int main()int a,b,c;double ans;cinac;if(!c11=c)c-=1;b=(a*c)/2;ans=sqrt(pow(b,3);printf(%0.2f,ans);return 0;输入：1 3输出：2.825 届 ccf noip 2019 普及组初赛 c+试题卷#include#includeusing namesp
8、ace std;int n,a101,i;int main()cinn;for(i=1;iai;sort(a+1,a+n+1);n=unique(a+1,a+n+1)-a-1;coutnendl;for(i=1;i=n;i+)coutai;coutendl;return 0;输入：1020 40 32 67 40 20 89 300 400 15输出：3.#includeusing namespace std;long long o=1,minn=10000000,m;struct pa long long s;long long j;string n;long long cost;pa p1
9、0005;int main()while(cinpo.spo.jpo.n)o+;for(int i=1;io;i+)for(int g=1;go;g+)pi.cost+=abs(pi.j-pg.j)*pg.s;if(pi.cost=minn)minn=pi.cost;m=i;825 届 ccf noip 2019 普及组初赛 c+试题卷 coutpm.n pm.costendl;return 0;输入：7 9289 Vladivostok5 8523 Chabarovsk3 5184 Irkutsk8 2213 Yalutorovsk10 0 Moscow输出：4.#includeusing
10、namespace std;int a500001,b500001,i,n,A,B,l,r,mid;bool check(int mid)int ii,s=0;memcpy(b,a,sizeof(a);for(ii=1;ii=n;ii+)bii-=mid*A;for(ii=1;ii0)s+=(int)ceil(double)bii/B);return s=mid;int main()scanf(%d%d%d,&n,&A,&B);for(i=1;i=n;i+)scanf(%d,&ai);l=0;r=500010;while(laj825 届 ccf noip 2019 普及组初赛 c+试题卷且i
11、j的有序对。逆序对可以用冒泡排序和归并排序求得。试完善以下冒泡排序程序段与归并排序程序。s=0;for(i=1;i=n;i+)for(j=1;jaj+1)（2）;+s;coutsendl;/#includeusing namespace std;long long a500001,b500001,s,n;void guibing(long long l,long long r)if(r-l=0)return;if(r-l=1)if(araj)s+=（6）bk=aj;+k;+j;else bk=ai;+k;+i;825 届 ccf noip 2019 普及组初赛 c+试题卷 for(;i=mid
12、;i+)bk+=ai;for(;j=r;j+)bk+=aj;for(k=l;k=r;k+)（7）;int main()long long i;scanf(%ld,&n);for(i=1;i=n;i+)scanf(%ld,&ai);guibing(1,n);printf(%ldn,s);return 0;2.2.石子合并：石子合并：在一个圆形操场的四周摆放N 堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的 2 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。试设计出 1 个算法,计算出将 N 堆石子合并成 1 堆的最小得分和最大得分.#includeusing names
13、pace std;const int Maxn=1000+10;int tMaxn,dp1MaxnMaxn,dp2MaxnMaxn;int main()int n;cinn;for(int i=1;iti;t（1）=ti;for(int i=2;i=2*n;+i)ti+=ti-1;memset(dp1,0,sizeof(dp1);for(int i=2*n-1;（2）)for(int j=（3）;j=2*n;+j)int b=2147483647;for(int k=i;kj;+k)dp1ij=max(dp1ij,dp1ik+dp1k+1j+tj-ti-1);b=min(b,（4）);dp2i
14、j=b;int max0=0,min0=10000000;for(int i=1;i=n;+i)max0=max(（5）);min0=min(min0,dp2ii+n-1);coutmin0endlmax0endl;return 0;CCF NOIP2019 CCF NOIP2019普及组（普及组（C+C+语言）参考答案与评分标准语言）参考答案与评分标准825 届 ccf noip 2019 普及组初赛 c+试题卷一、单项选择题（共一、单项选择题（共 2020 题，每题题，每题 1.51.5 分，共计分，共计 3030 分）分）1C2A3C4B5A6D7D8B9B10C11B12D13A14C
15、15D16A17C18B19B20D二、问题求解（共二、问题求解（共 2 2 题，每题题，每题 5 5 分，共计分，共计 1010 分）分）1.答案为：（任答其一即可）59994,53955：74943,62964,71973,83952：61974,82962,75933,639542.a12+a22+a2或ai2三、阅读程序写结果（共三、阅读程序写结果（共 4 4 题，每题题，每题 8 8 分，共计分，共计 3232 分）分）1.1.002.815 20 32 40 67 89 300 4003Yalutorovsk 11212546四、完善程序（第四、完善程序（第1 1 题，每空题，每空2 2 分，第分，第2 2 题，每空题，每空3 3 分，共计分，共计2828 分）分）（说明：以下各程序填空可能还有一些等价的写法，各省可请本省专家审定和上机验证，不一定上报科学委员会审查）1.（1）n-1（2）swap(aj,aj+1);（3）(l+r)/2（4）guibing(mid+1,r);（5）i=mid&j=1;-i（3）i+1（4）dp2ik+dp2k+1j+tj-ti-1（5）max0,dp1ii+n-18