NOIP2018提高组C++试题

CCFNOIP2018初赛提高组C++语言试题第1页，共9页第二十四届全国青少年信息学奥林匹克联赛初赛提高组C++语言试题竞赛时间：2018年10月13日14:30~16:30选手注意：试题纸共有10页，答题纸共有2页，满分100分。请在答题纸上作答，写在试题纸上的一律无效。不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。一、单项选择题（共10题，每题2分，共计20分；每题有且仅有一个正确选项）1.下列四个不同进制的数中，与其它三项数值上不相等的是（）。A.(269)16B.(617)10C.(1151)8D.(1001101011)22.下列属于解释执行的程序设计语言是（）。A.CB.C++C.PascalD.Python3.中国计算机学会于（）年创办全国青少年计算机程序设计竞赛。A.1983B.1984C.1985D.19864.设根节点深度为0，一棵深度为h的满k（k1）叉树，即除最后一层无任何子节点外，每一层上的所有结点都有k个子结点的树，共有（）个结点。A.(kh+1-1)/(k-1)B.kh-1C.khD.(kh-1)/(k-1)5.设某算法的时间复杂度函数的递推方程是T(n)=T(n-1)+n（n为正整数）及T(0)=1，则该算法的时间复杂度为（）。A.O(logn)B.O(nlogn)C.O(n)D.O(n2)CCFNOIP2018初赛提高组C++语言试题第2页，共9页6.表达式a*d-b*c的前缀形式是（）。A.ad*bc*-B.-*ad*bcC.a*d-b*cD.-**adbc7.在一条长度为1的线段上随机取两个点，则以这两个点为端点的线段的期望长度是（）。A.1/2B.1/3C.2/3D.3/58.关于Catalan数Cn=(2n)!/(n+1)!/n！，下列说法中错误的是（）。A.Cn表示有n+1个结点的不同形态的二叉树的个数。B.Cn表示含n对括号的合法括号序列的个数。C.Cn表示长度为n的入栈序列对应的合法出栈序列个数。D.Cn表示通过连接顶点而将n+2边的凸多边形分成三角形的方法个数。9.假设一台抽奖机中有红、蓝两色的球，任意时刻按下抽奖按钮，都会等概率获得红球或蓝球之一。有足够多的人每人都用这台抽奖机抽奖，假如他们的策略均为：抽中蓝球则继续抽球，抽中红球则停止。最后每个人都把自己获得的所有球放到一个大箱子里，最终大箱子里的红球与蓝球的比例接近于（）。A.1:2B.2:1C.1:3D.1:110.为了统计一个非负整数的二进制形式中1的个数，代码如下：intCountBit(intx){intret=0;while(x){ret++;________;}returnret;}则空格内要填入的语句是（）。A.x=1CCFNOIP2018初赛提高组C++语言试题第3页，共9页B.x&=x-1C.x|=x1D.x=1二、不定项选择题（共5题，每题2分，共计10分；每题有一个或多个正确选项，多选或少选均不得分）1.NOIP初赛中，选手可以带入考场的有（）。A.笔B.橡皮C.手机（关机）D.草稿纸2.2-3树是一种特殊的树，它满足两个条件：（1）每个内部结点有两个或三个子结点；（2）所有的叶结点到根的路径长度相同。如果一棵2-3树有10个叶结点，那么它可能有（）个非叶结点。A.5B.6C.7D.83.下列关于最短路算法的说法正确的有（）。A.当图中不存在负权回路但是存在负权边时，Dijkstra算法不一定能求出源点到所有点的最短路。B.当图中不存在负权边时，调用多次Dijkstra算法能求出每对顶点间最短路径。C.图中存在负权回路时，调用一次Dijkstra算法也一定能求出源点到所有点的最短路。D.当图中不存在负权边时，调用一次Dijkstra算法不能用于每对顶点间最短路计算。4.下列说法中，是树的性质的有（）。A.无环B.任意两个结点之间有且只有一条简单路径C.有且只有一个简单环D.边的数目恰是顶点数目减15.下列关于图灵奖的说法中，正确的有（）。A.图灵奖是由电气和电子工程师协会（IEEE）设立的。B.目前获得该奖项的华人学者只有姚期智教授一人。C.其名称取自计算机科学的先驱、英国科学家艾伦·麦席森·图灵。CCFNOIP2018初赛提高组C++语言试题第4页，共9页D.它是计算机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖”之称。三、问题求解（共2题，每题5分，共计10分）1.甲乙丙丁四人在考虑周末要不要外出郊游。已知①如果周末下雨，并且乙不去，则甲一定不去；②如果乙去，则丁一定去；③如果丙去，则丁一定不去；④如果丁不去，而且甲不去，则丙一定不去。如果周末丙去了，则甲________（去了/没去）(1分)，乙________（去了/没去）(1分)，丁________（去了/没去）(1分)，周末________（下雨/没下雨）(2分)。2.方程a*b=(aorb)*(aandb)，在a,b都取[0,31]中的整数时，共有_____组解。（*表示乘法；or表示按位或运算；and表示按位与运算）四、阅读程序写结果（共4题，每题8分，共计32分）1.#includecstdiointmain(){intx;scanf(%d,&x);intres=0;for(inti=0;ix;++i){if(i*i%x==1){++res;}}printf(%d,res);return0;}输入：15输出：_________2.#includecstdiointn,d[100];boolv[100];intmain(){scanf(%d,&n);for(inti=0;in;++i){scanf(%d,d+i);v[i]=false;CCFNOIP2018初赛提高组C++语言试题第5页，共9页}intcnt=0;for(inti=0;in;++i){if(!v[i]){for(intj=i;!v[j];j=d[j]){v[j]=true;}++cnt;}}printf(%d\n,cnt);return0;}输入：107143259806输出：_________3.#includeiostreamusingnamespacestd;strings;longlongmagic(intl,intr){longlongans=0;for(inti=l;i=r;++i){ans=ans*4+s[i]-'a'+1;}returnans;}intmain(){cins;intlen=s.length();intans=0;for(intl1=0;l1len;++l1){for(intr1=l1;r1len;++r1){boolbo=true;for(intl2=0;l2len;++l2){for(intr2=l2;r2len;++r2){if(magic(l1,r1)==magic(l2,r2)&&(l1!=l2||r1!=r2)){bo=false;}}}if(bo){CCFNOIP2018初赛提高组C++语言试题第6页，共9页ans+=1;}}}coutansendl;return0;}输入：abacaba输出：_________4.#includecstdiousingnamespacestd;constintN=110;boolisUse[N];intn,t;inta[N],b[N];boolisSmall(){for(inti=1;i=n;++i)if(a[i]!=b[i])returna[i]b[i];returnfalse;}boolgetPermutation(intpos){if(posn){returnisSmall();}for(inti=1;i=n;++i){if(!isUse[i]){b[pos]=i;isUse[i]=true;if(getPermutation(pos+1)){returntrue;}isUse[i]=false;}}returnfalse;}voidgetNext(){for(inti=1;i=n;++i){isUse[i]=false;}getPermutation(1);for(inti=1;i=n;++i){CCFNOIP2018初赛提高组C++语言试题第7页，共9页a[i]=b[i];}}intmain(){scanf(%d%d,&n,&t);for(inti=1;i=n;++i){scanf(%d,&a[i]);}for(inti=1;i=t;++i){getNext();}for(inti=1;i=n;++i){printf(%d,a[i]);if(i==n)putchar('\n');elseputchar('');}return0;}输入1：610164532输出1：_________（3分）输入2：6200153426输出2：_________（5分）五、完善程序（共2题，每题14分，共计28分）1.对于一个1到𝑛的排列𝑃（即1到𝑛中每一个数在𝑃中出现了恰好一次），令𝑞𝑖为第𝑖个位置之后第一个比𝑃𝑖值更大的位置，如果不存在这样的位置，则𝑞𝑖=𝑛+1。举例来说，如果𝑛=5且𝑃为15423，则𝑞为26656。下列程序读入了排列𝑃，使用双向链表求解了答案。试补全程序。（第二空2分，其余3分）数据范围1≤𝑛≤105。#includeiostreamusingnamespacestd;constintN=100010;intn;intL[N],R[N],a[N];intmain(){cinn;for(inti=1;i=n;++i){intx;CCFNOIP2018初赛提高组C++语言试题第8页，共9页cinx;(1);}for(inti=1;i=n;++i){R[i]=(2);L[i]=i-1;}for(inti=1;i=n;++i){L[(3)]=L[a[i]];R[L[a[i]]]=R[(4)];}for(inti=1;i=n;++i){cout(5);}coutendl;return0;}2.一只小猪要买N件物品（N不超过1000）。它要买的所有物品在两家商店里都有卖。第i件物品在第一家商店的价格是a[i]，在第二家商店的价格是b[i]，两个价格都不小于0且不超过10000。如果在第一家商店买的物品的总额不少于50000，那么在第一家店买的物品都可以打95折(价格变为原来的0.95倍)。求小猪买齐所有物品所需最少的总额。输入：第一行一个数N。接下来N行，每行两个数。第i行的两个数分别代表a[i]，b[i]。输出：输出一行一个数，表示最少需要的总额，保留两位小数。试补全程序。（第一空2分，其余3分）#includecstdio#includealgorithmusingnamespacestd;constintInf=1000000000;constintthreshold=50000;constintmaxn=1000;intn,a[maxn],b[maxn];boolput_a[maxn];inttotal_a,total_b;CCFNOIP2018初赛提高组C++语言试题第9页，共9页doubleans;intf[threshold];intmain(){scanf(%d,&n);total_a=total_b=0;for(inti=0;in;++i){scanf(%d%d,a+i,b+i);if(a[i]=b[i])total_a+=a[i];elsetotal_b+=b[i];}ans=total_a+total_b;total_a=total_b=0;for(inti=0;in;++i){if((1)){put_a[i]=true;total_a+=a[i];}else{put_a[i]=false;total_b+=b[i];}}if((2)){printf(%.2f