NOIP2016信息学奥赛普及组初赛C++试题

NOIP2016普及组C++语言试题竞赛时间:2016年10月22日14:30〜16:30一、单项选择題（201.530分；毎趣有且仅有一个正确选项）•以下不是微软公司出品的软件是（）。A•PowerPointB•WordC.ExcelD.AcrobatReader•256，至少需要（）A-6B-7C-8D-93•以下不属于无线通信技术的是（）。A-蓝牙B・WiFiC-GPRSD-以太网•CPU生产厂商的是（）。A.IntelB.AMDC.MicrosoftD.IBM•以下不是存储设备的是（）。A•光盘B•磁盘C•因态硬盘D•鼠标•，现在有一只小老鼠反复按照CapsLockA、字母键S和字母键D的顺序循环按键，即CapsLock、A、S・D、CapsLock、A、S、D................屏幕上输出的第81个字符是字母（）。A-AB-SC-DD-a7-二进制数00101100和00010101的和是（）。A.00101000B.01000001C.01000100D.001110008・与二进制小数0.1相等的八进制数是（）。A•0.8B•0.4C•0.2D•0.19・以下是32位机器和64位机器的区别的是（）。A•显示器不同硬盘大小不同C•寻址空间不同输入法不同10•以下关于字符串的判定语句中正确的是（）A•字符串是一种特殊的线性表B・串的长度必须大于零C•字符串不可以用数组来表示D・空格字符组成的串就是空串叉树中11•一棵二叉树如右图所，若采用顺序存储结，即用一维数组元素存储该二 yo的结点A.6B-10C-12D-1512•若有如下程序段，其中s、b、c且a、c(c0)。s=a;for(b=l;b<=c;b++)s=s+l;则与上述程序段修改s值的功能等价的赋值语句是()。A.s二a+b; B.s=a+c;C.s=s+c;D.13•有以下程序：#include<iostream>usingnamespaceintmainO{intk=4,n=0;while(n<k){n++;if(n%3!0)conntinue;k—;)cout«k«n,,f«n«cndl;return0;)程序运行后的输出结果是()。A•2,2B-2,3C-3,2D-3,314•给定含有n个不同的数的数组L=<xi9x29 ,9Xn>。如果L中存在xi（l<i<n）使得xl<x2<...<xi-l<xi>xi+l>...>xn#1则称L，并称xi是L的“峰顶"。现在己知L是单峰的»请把a-c三行代码补全到算法中使得算确找到L的峰顶。Search(k+1»n)Search⑴k-1)returnL[k]Search(l,1. k*-(n/2j2. ifL[k]>L[k-1]andL[k]>L[k+1]then elseifL[k]>L[k-1]andL[k]<L[k+1]then else 正确的填空顺序是（）。A.c,a,bB.c,b,aC.a,b,cD.b,a,c15・设简单无向图G有16条边且每个顶点的度数都是2，则图G有（）个顶点。A-10B-12 C-8D-16167，3，一共有（）种放法。A-7B-8C-21D-3717・下图表示一个果园淮溉系统，有A、B、C、D四个阀门，每个阀门可以打开或关上，所有管道粗细相A・B打开，其他都关上B-AB都打开，CD都关上C•A打开，其他都关上D•D打开，其他都关上18・Lucia和她的朋友以及朋友的朋友都在某社交上注册了账号。下图是他们之间的关系图，两个人之间有边相连代表这两个人是朋友，没有边相连代表不是朋友。这个社交的规则是：如果某人A向他（她）的朋友B分享了某照片，那么B就可以对该照片进行评论；如果B评论了该照片，那么他（她）的所有朋友都可以看见这个评论以及被评论的照片，但是不能对该照片进行评论（除非A也向他（她）分享了该照片）。现在Lucia已经上传了一照片，但是她不想让Jacob看见这照片，那么她可以向以下朋友（）分享该照片。A.Dana,Michael,EveB.Dana,Eve,MonicaC.Michael,Eve,JacobD.MicheaLPeter,Monica19・10101030分钟。注意：两道不同的菜的相同步骤不可以同时进行。例如第一道菜和第二道的菜不能同时洗，也不能同时切。那么做完三道菜的最短时间需要（）分钟。A-90B-60C-50D-4020・参加N0I比赛，以下不能带入考场的是（）。A•钢笔B•适量的衣服C・U盘D•铅笔二、问题求解（共2题，每趣5分，共计10分；第一题全部答对得5分，没有部分分；第二题第一空2分，第二空3分）1从一个4x4的棋盘（不可旋转）中选取不在同一行也不在同一列上的两个方格>共有 种方法2•约定二叉树的根节点高度为1。一棵结点数为2016的二叉树最少有 个叶子结点；一棵结点、数为2016的二叉树最小的高度值 。（4832分）#include<iostrcam>usingnamespacestd;intmainO{intmax,inin,sum,count=0;inttmp;cin»tinp;if(tmp==0)return0;max=niin=sum=tinp;count++;while(tmp!=0)Icin»tmp;if(tmp!=0){suiii+=tmp;count++;if(tnip>niax)max=tmp;if(tmp<min)min=tinp;cout«max«n,

n«min«h,u

«sum/count«endl;return0;输入：12345607输出：#includc<iostream>usingnamespaceintmainO{inti=100,x=0,y=0;while(i>0){i—;x=i%8;if(x==l)y++;}coutyreturn0;}输出：#include<iostream>usingnamespaceintmainOIinta[6]={l,2,3,4,5,6};intpi=0;intpj=5;intt,i;while(pi<pj){t=a[pi];a[pi]=a[pj];a[pj]=t;pi++;}for(i=0;i<6;i++)\coutendl;return0;}输出：#include<iostrcam>usingnamespaceintmainO{inti,length1,lcngth2;stringsl,s2;sl=Thaveas2MIHaveAlengthl=s1.sizeO;Iength2=s2.sizeO;for(i=O;i<lcngthl;i++)if(sl[i]>=a&&sl[i]<=z)sl[i]-=a*-'A';for(i=0;i<lcngth2;i++)if(s2[i]>=a&&s2[i]<=z)s2[i]-=a*-'A*;if(sl==s2)cout«w=h«cndl:elseif(sl>s2)cout«H>u«cndl;elsecout«H<n«cnd1;return0;}输出： 四、完善程序(共2趣，毎趣14分，共计28分)1.(读入整数)请完善下面的程序，使得程序能够读入两个int田的整数，并将这两个整数分别输出，每行一个。(第一'五空2.5分，其余3分)输入的整数之间和前后只会出现空格或者回车。输入数扌居保证合法。例如：输入：123-789输出:123-789#include<iostrcain>usingnamespaceintreadint(){intnum=0;//存储读取到的整数intnegative=0;//负数标识charc;//存储当前读取到的字符c=cin.get();while((c<'O'||c>'9')&&c!='-')c=if(celse

(1) ;)negative=1;(2) ;c=cin.gct();while({

(3))(4);c=cin.get();}if(negative==1)returnnum;}

(5) ;intmainOinta,b;a=rcadintO;b=rcadintO;cout«a«end1«b«end1;return0;}2.（郊游活动）nnAi位同学自己携带了MiB（^n）j辆自行车的价格为Cj元，钱给他人，他们想知道最多有多少位同学能够租用到自行车。（第四、五空2.5分，其余3分）［1,mid并判斷租用到自行车的人数能否达到mid。判斷的过程是利用贪心算法实现的。#include<iostrcain>usingnamespacestd;#defineMAXN1000000intn,B,A,M[MAXN],CfMAXN],1,r,ans,mid;boolchcck(intnn){intcount=0,i,i= (1);j=1；while(i<=n){if( (2))count+=C[j]-i++；j++；return(3)voidsort(inta[],int 1,intr)inti= hjwhile(i <=j)

=a[(l+r)/2],y;while (a[i] <x) i++;while

>x) j—if(i

<=j) ；y= a[i];a[i] =a[j];a[j]=i++ j—；if(i<r)if(1sort(a,i,r);sort(a,1,j);<