《NOIP全国青少年信息学奥林匹克联赛初赛试题2009—2016普及组初赛试题及答案C++.docx》由会员分享，可在线阅读，更多相关《NOIP全国青少年信息学奥林匹克联赛初赛试题2009—2016普及组初赛试题及答案C++.docx（59页珍藏版）》请在三一办公上搜索。
1、下载原文可修改文字和底色颜色查看原文第十五届全国青少年信息学奥林匹克联赛初赛试题（普及组C+语言二小时完成）全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效一.单项选择题（共20题，每题1.5分，共计30分。每题有且仅有一个正确答案。）1、关于图灵机下面的说法哪个是正确的：A）图灵机是世界上最早的电子计算机。B）由于大量使用磁带操作，图灵机运行速度很慢。C）图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。D）图灵机只是一个理论上的计算模型。2、关于计算机内存下面的说法哪个是正确的：A）随机存储器（RAM）的意思是当程序运行时，每次具体分配给程序的内存位置是随机而不确定的B
2、）IMB内存通常是指1024*1024字节大小的内存。C）计算机内存严格说来包括主存（memory）、高速缓存（CaChe）和寄存器（register）三个部分。D）一般内存中的数据即使在断电的情况下也能保留2个小时以上。3、关于BIoS下面说法哪个是正确的：A） BloS是计算机基本输入输出系统软件的简称。B） BlOS里包含了键盘、鼠标、声卡、显卡、打印机等常用输入输出设备的驱动程序。C） BlOS一般由操作系统厂商来开发完成。D） BloS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。4、关于CPU下面哪个说法是正确的:A) CPU全称为中央处理器(或中央处理单元).B) C
3、PU可以直接运行汇编语言。C)同样主频下，32位的CPU比16位的CPU运行速度快一倍。D)CPU最早是由Intel公司发明的。5、关于ASClI,下面哪个说法是正确的：A) ASCII码就是键盘上所有键的唯一编码。B) 一个ASeIl码使用一个字节的内存空间就能够存放。C)最新扩展的ASCII编码方案包含了汉字和其他欧洲语言的编码。D)ASCIl码是英国人主持制定并推广使用的。6、下列软件中不是计算机操作系统的是：A)WindowsB)LinuxC)OS/2D)WPS7、关于互联网，下面的说法哪一个是正确的：A)新一代互联网使用的IPv6标准是IPv5标准的升级与补充。B)互联网的入网8主机
4、如果有了域名就不再需要IP地址。C)互联网的基础协议为TCP/IP协议。D)互联网上所有可下载的软件及数据资源都是可以合法免费使用的。8、关于HTML下面哪种说法是正确的：A) HTML实现了文本、图形、声音乃至视频信息的统一编码。B) HTML全称为超文本标记语言。C)网上广泛使用的FIaSh动画都是由HTML编写的。D)HTML也是一种高级程序设计语言。9、关于程序设计语言，下面哪个说法是正确的：A)加了注释的程序一般会比同样的没有加注释的程序运行速度慢。B)高级语言开发的程序不能使用在低层次的硬件系统如：自控机床或低端手机上。C)高级语言相对于低级语言更容易实现跨平台的移植。D)以上说法
5、都不对。10、已知大写字母A的ASCIl编码为65(10进制)，则大写字母J的10进制ASCIl编码为：A)71B)72C)73D)以上都不是11、十进制小数125.125对应的8进制数是A)100.1B)175.175C)175.1D)100.17512、有六个元素FEDCBA从左至右依次顺序进栈，在进栈过程中会有元素被弹出栈。问下列哪一个不可能是合法的出栈序列？A)EDCFABB)DECABFC)CDFEBAD)BCDAEF13表达式a*(b+c)-d的后缀表达式是：A)abed*+-B)abc+*d-C)abc*+d-D)-+*abcd14、一个包含n个分支结点(非叶结点)的非空二叉树，
6、它的叶结点数目最多为：A)2n+1B)2n-1C)n-1D)n+115、快速排序最坏情况下的算法时间复杂度为：A)O(log2n)B)O(n)C)O(nlog2n)D)0(n2)16.有一个由4000个整数构成的顺序表，假定表中的元素已经按升序排列，采用二分查找定位一个元素则最多需要几次比较就能确定是否存在所查找的元素：A)Il次B)12次C)13次D)14次17、排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪种排序算法是不稳定的：A)冒泡排序B)插入排序C)归并排序D)快速排序18、己知n个顶点的有向图，若该图是强连通的(从所有顶点都存在路径到达其他顶点)，则该图中
7、最少有多少条有向边？A)nB)n+1C)n-1D)n*(n-l)19、全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的信息和资源，请问全国信息学奥林匹克官方网站的网址是：A)B)http:/www.noi.org/C)D)20、在参加Nol系列竞赛过程中，下面哪一种行为是不被严格禁止的：A)携带书写工具，手表和不具有通讯功能的电子词典进入赛场。B)在联机测试中通过手工计算出可能的答案并在程序里直接输出答案来获取分数。C)通过互联网搜索取得解题思路。D)在提交的程序中启动多个进程以提高程序的执行效率。二 .问题求解(共2题，每空5分，共计10分)1 .小陈现有2个任务A,B要完
8、成，每个任务分别有若干步骤如下：A=al-a2-a3,B=bl-b2-b3-b4-b5,在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如a2-b2-a3-b3是合法的，而a2-b3-a3-b2是不合法的。小陈从B任务的bl步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己己经完成了整个任务A,其他的都忘了。试计算小陈饭前已做的可能的任务步骤序列共有种。2 .有如下的一段程序：1. a=l;2. b=a;3. d=-a;4. e=a+d
9、;5. c=2*d;6. f=b+e-d;7. g=a*f+c;现在要把这段程序分配到若干台(数量充足)用电缆连接的PC上做并行执行。每台PC执行其中的某几个语句，并可随时通过电缆与其他PC通讯，交换一些中间结果。假设每台PC每单位时间可以执行一个语句,且通讯花费的时间不计。则这段程序最快可以在单位时间内执行完毕。注意：任意中间结果只有在某台PC上己经得到，才可以被其他PC引用。例如若语句4和6被分别分配到两台PC上执行，则因为语句6需要引用语句4的计算结果，语句6必须在语句4之后执行。三 .阅读程序写结果(共4题，每题8分，共计32分)1.includeusingnamespacestd;i
10、nta,b;intwork(inta,intb)(if(a%b)returnwork(b,a%b);returnb;intmain()(cinab;coutwork(a,b)endl;returnO;输入：2012输出：#includeusingnamespacestd;intmain()(inta3,b3;inti,jztmp;for(i=0;i3;i+)cinbi;for(i=0;i3;i+)(ai=0;for(j=0;j=i;j+)(ai+=bj;bai%3+=aj;tmp=l;for(i=0;i3;i+)(ai%=10;bi%=10;tmp*=ai+bi;couttmpendl;ret
11、urnO;输入：235输出：3.#includeusingnamespacestd;constintc=2009;intmain()(i11tn,pzs,izj,t;cinn;s=0;t=l;for(i=l;i=n;i+)(t=t*%c;for(j=l;j=i;j+)S=(s+t)%c;coutsendl;return0;)输入：112输出：4.#includeusingnamespacestd;constintmaxn=50;voidgetnext(charstr)intI=Strlen(str),izj,k,temp;k=l-2;while(k=O&strkstrk+l)k-;i=k+l;
12、while(istrk)i+;temp=strk;strk=stri-l;stri-l=temp;for(i=l-l;ik;i-)for(j=k+l;jstrj+l)(temp=strj;strj=strj+l;strj+l=temp;)return;)intmain()(charamaxn;intn;cinan;while(n0)(getnext(a);n;)coutaendl;returnO;输入：NOIP3输出：四.完善程序(前8空，每空3分，后2空，每空2分，共28分)1.(最大连续子段和)给出一个数列(元素个数不多于IO0),数列元素均为负整数、正整数、Oo请找出数列中的一个连续子数
13、列，使得这个子数列中包含的所有元素之和最大,在和最大的前提下还要求该子数列包含的元素个数最多，并输出这个最大和以及该连续子数列中元素的个数。例如数列为4,-5,3,2,4时，输出9和3；数列为123-5078时，输出16和7。includeusingnamespacestd;inta101;intn,i,ans,Ien,tmp,beg;intmain()cinn;for(i=l;i=n;i+)cinai;tmp=0;ans=0;len=0;beg=;for(i=l;ians)ans=tmp+ai;len=i-beg;)elseif(&i-beglen)len=i-beg;if(tmp+a(i)
14、beg=;tmp=0;)else；)coutansuuIenendl;returnO;2.(国王放置)在n*m的棋盘上放置k个国王，要求k个国王互相不攻击，有多少种不同的放置方法。假设国王放置在第(x,y)格，国王的攻击的区域是：(x-l,y-l),(x-l,y),(x-lzy+l),(xzy-l),(xzy+l),(x+l,y-l),(x+l,y),(x+lzy+l)o读入三个数n,m,k,输出答案。题目利用回溯法求解。棋盘行标号为On-1,列标号为Om-1includeusingnamespacestd;intn,m,k,ans;inthash55;voidwork(intx,inty,i
15、nttot)inti,j;if(tot=k)ans+;return;dowhile(hashxy)y+;if(y=m)x+;y=;)if(x=n)return;)for(i=x-l;i=0&in)for(j=y-l;j=0&jm)；for(i=x-l;i=0&in)for(j=y-l;j=0&jm)；y+;if(y=m)x+;y=0;)if(x=n)return;)while(1);)intmain()cinnmk;ans=0;memset(hash,0,sizeof(hash);；coutansendl;returnO;答案部分NO工P2009年普及组（C+语言）参考答案与评分标准一、单项选
16、择题：（每题15分）I. D.DII. C16.B2.B3.A4.A5.B7.C8.B9.C10.D12.C13.B14.D15.D17.D18.A19.C20.B二、问题求解：（共2题，每空5分，共计10分）1. 702. 5三、阅读程序写结果（共4题，每题8分，共计32分）1. 42. 4163. 7824. .NPOI四.完善程序（前8空，每空3分，后2空，每空2分，共28分）（说明：以下各程序填空可能还有一些等价的写法，各省可请本省专家审定和上机验证，不一定上报科学委员会审查）1.0tmpai=ans或者ai+tmp=ans或者ans=ai+tmp等pq)B. QV (-PQ) V (
17、P八Q)d. pV-qV (p-iQ) V (-p-Q)4 .LinUX下可执行文件的默认扩展名为（）。D.以上都不是A.exeB.comC.dll5 .如果树根算第1层，那么一棵n层的二叉树最多有（）个结点。A.2n-lB.2nC.2n+lD.2n+16 .提出“存储程序”的计算机工作原理的是（）。A.克劳德香农B.戈登摩尔C.查尔斯巴比奇D.冯诺依曼7 .设X、Y、Z分别代表三进制下的一位数字，若等式XY+ZX=XYX在三进制下成立,那么同样在三进制下，等式XY*ZX=（）也成立。A.YXZB.ZXYC.XYZD.XZY8 .PaSCal语言、C语言和C+语言都属于（）。A.面向对象语言B
18、.脚本语言C.解释性语言D.编译性语言9 .前缀表达式“+3*2+512”的值是（）。A. 23B. 25C. 37D. 6510 .主存储器的存取速度比中央处理器（CPU）的工作速度慢得多，从而使得后者的效率受到影响。而根据局部性原理，CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。于是，为了提高系统整体的执行效率，在CPU中引入了（）。A.寄存器B.高速缓存C.闪存D.外存11 .一个字长为8位的整数的补码是IIIIIo01,则它的原码是（）。A.00000111B.01111001C.11111001D.1000011112 .基于比较的排序时间复杂度的下限是（），其中n表示
19、待排序的元素个数。A.（n）B.（nlogn）C.（logn）D.（n2）13 .一个自然数在十进制下有n位，则它在二进制下的位数与（）最接近。A.5nB.n*log2lC.10*log211D.Inlog2n14 .在下列HTML语句中，可以正确产生一个指向No工官方网站的超链接的是（）。A. MEi11）NOIMB. 欢迎访问No工网站C. http:/D. 欢迎访问No工网站15 .元素RI、R2、R3、R4、R5入栈的顺序为Rl、R2、R3、R4、R5。如果第1个出栈的是R3,那么第5个出栈的不可能是（）。A.RlB.R2C.R4D.R516.双向链表中有两个指针域IIink和“ink
20、,分别指向该结点的前驱及后继。设P指向链表中的一个结点，它的左右结点均非空。现要求删除结点p,则下面语句序列中错误的是（）OA. p-rlink-llink=p-rlink;p-llink-rlink=p-llink;deletep;B. p-llink-rlink=p-rlink;p-rlink-llink=p-llink;deletep;C. p-rlink-llink=p-llink;p-rlink-llink-rlink=p-rlink;deletep;D. p-llink-rlink=p-rlink;p-llink-rlink-llink=p-llink;deletep;17 .一棵
21、二叉树的前序遍历序列是ABCDEFG,后序遍历序列是CBFEGDA,则根结点的左子树的结点个数可能是（）。A. 2B. 3C. 4D. 518 .关于拓扑排序，下面说法正确的是（）。A.所有连通的有向图都可以实现拓扑排序B.对同一个图而言，拓扑排序的结果是唯一的C.拓扑排序中入度为O的结点总会排在入度大于O的结点的前面D.拓扑排序结果序列中的第一个结点一定是入度为O的点19.完全二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置，则第k号结点的父结点如果存在的话，应当存放在数组的（）号位置。A.2kB.2k+lC.k/2
22、下取整D.（k+l）2下取整20.全国青少年信息学奥林匹克系列活动的主办单位是（）。A.教育部B.科技部C.共青团中央D.中国计算机学会二、问题求解（共2题，每题5分，共计10分）1.LZW编码是一种自适应词典编码。在编码的过程中，开始时只有一部基础构造元素的编码词典，如果在编码的过程中遇到-个新的词条，则该词条及一个新的编码会被追加到词典中，并用于后继信息的编码。举例说明，考虑一个待编码的信息串：”XyXyyyyxyx.初始词典只有3个条目，第一个为X,编码为1;第二个为y,编码为2；第三个为空格，编码为3；于是串“xyx”的编码为1-2-1（其中-为编码分隔符），加上后面的一个空格就是1-
23、2-1-3。但由于有了一个空格，我们就知道前面的“xyx”是一个单词，而由于该单词没有在词典中，我们就可以自适应的把这个词条添加到词典里，编码为4,然后按照新的词典对后继信息进行编码，以此类推。于是，最后得到编码：l-2-l-3-2-2-3-5-3-4o现在已知初始词典的3个条目如上述，则信息串yyxyXXyyxyxyxXXxyx,的编码是O2.队列快照是指在某一时刻队列中的元素组成的有序序列。例如，当元素1、2、3入队，元素1出队后，此刻的队列快照是“23”。当元素2、3也出队后，队列快照是”“，即为空。现有3个正整数元素依次入队、出队。已知它们的和为8,则共有种可能的不同的队列快照（不同队
24、列的相同快照只计一次）。例如，“51“、“422“、”都是可能的队列快照；而”7”不是可能的队列快照，因为剩下的2个正整数的和不可能是1。三、阅读程序写结果（共4题，每题8分，其中第4题（1）、（2）各4分，共计32分）1.includeusingnamespacestd;voidswap(int&a,int&b)(intt;t=a;a=b;b=t;intmain()(intal,a2,a3,x;cinala2a3;if(ala2)swap(alza2);if(a2a3)swap(a2,a3);if(ala2)swap(alza2);cinx;if(xa2)if(xal)coutx,al,a2
25、,a3endl;elsecoutalx,a2 ,a3endl;elseif (x a3)coutal,a2,x,a3endl;elsecoutal,a2 ,a3,xendl;return 0;输入：9122077输出：2.includeusingnamespacestd;intrSum(intj)(intsum=0;while(j!=0)sum=sum*10+(j%10);j=j/10;)returnsum;第4层中国公司经理波兰公司经理tItI第3层卜国公司经理秘书反公司要理空书tItI第2层*国公司更盗波兰公司翻译tItI第1层半田打递员+波兰邮递员第4层司令,I第3层军长I军长2II第2
26、层师长1师长2师长3师长4IIII第1层团长1团长2团长3团长4团长5团长6团长7团长8第4层英国女王瑞典国王第3层英国首相-A瑞典首相第2层英国外交大臣-A瑞典外交大臣第1层英国驻瑞典大使-A瑞典左英田大空第4层奥运会t第3层全运会t第2层省运会t第1层市运会EA.i=1：dosum+=i;i+；while(i100);C.i=1;while(i=100)sum+=i;i+；)问答编号系统生成的n个数掌握密码的用户的回答aa2a3a4111001200110301100411100510000B.C+hD.2g40次方D.吧U(X)IIB.TXT格式0.8-.0 + s- * X)=w)ux
27、EuE，小-Il31()rowsumi()-。rowsumij-11+matxijarea=O;snilasil-rowsuni!first-1IIl-ILUikh“峰顶。现在已知L是单峰的，请把a-c三行代码补全到算法中使得算法正确找到L的峰顶。a. Search(k+1n)b. SearCh(1,k-l)c. returnLkSeareh(1,n)1. kH112J2. ifLkLk-1andLkLk+13. then4. elseifLkLk-1andLkLk+15. then6. else正确的填空顺序是()OA.cza,bB.c,b,aC. a,b,cD. b,a,c15.设简单无向
28、图G有16条边且每个顶点的度数都是2,则图G有(点。)个顶A. 10B. 12C.8D.1616.有7个一模一样的苹果，放到3个一样的盘子中，一共有（）种放法。A.7B.8C.21D.3717.下图表示一个果园灌溉系统，有A、B、C、D四个阀门，每个阀门可以打开或关上，所有管道粗细相同，以下设置阀门的方法中，可以让果树浇上水的有水有水果树是（）OA.B打开，其他都关上C.A打开，其他都关上B.AB都打开，CD都关上D.D打开，其他都关上CCFNOIP2016初赛普及组C+语言试题第3页，共9页18.Lucia和她的朋友以及朋友的朋友都在某社交网站上注册了账号。下图是他们之间的关系图，两个人之间
29、有边相连代表这两个人是朋友，没有边相连代表不是朋友。这个社交网站的规则是：如果某人A向他（她）的朋友B分享了某张照片，那么B就可以对该照片进行评论；如果B评论了该照片，那么他（她）的所有朋友都可以看见这个评论以及被评论的照片，但是不能对该照片进行评论（除非A也向他（她）分享了该照片）。现在Lucia已经上传了一张照片，但是她不想让Jacob看见这张照片，那么她可以向以下朋友（）分享该照片。A. Dana,MichaelzEveC.Michael,Eve,JacobB. Dana,Eve,MonicaD.MichealzPeter,Monica19.周末小明和爸爸妈妈三个人一起想动手做三道菜。小
30、明负责洗菜、爸爸负责切菜、妈妈负责炒菜。假设做每道菜的顺序都是：先洗菜10分钟，然后切菜10分钟，最后炒菜10分钟。那么做一道菜需要30分钟。注意：两道不同的菜的相同步骤不可以同时进行。例如第一道菜和第二道的菜不能同时洗，也不能同时切。那么做完三道菜的最短时间需要（）分钟。A. 90B. 60C. 50D. 4020.参加NOI比赛，以下不能带入考场的是（A.钢笔B.适量的衣服C.U盘）OD.铅笔二、问题求解（共2题，每题5分，共计10分；第一题全部答对得5分，没有部分分；第二题第一空2分，第二空3分）1 .从一个44的棋盘（不可旋转）中选取不在同一行也不在同一列上的两个方格，共有种方法。CC
31、FNOIP2016初赛普及组C+语言试题第4页，共9页2 .约定二叉树的根节点高度为U一棵结点数为2016的二叉树最少有个叶子结点；一棵结点数为2016的二叉树最小的高度值是O三、阅读程序写结果(共4题，每题8分,共计32分)1 .#includeusingnamespacestd;intmain()intmax,min,sum,count=0;inttmp;cintmp;if(tmp=0)return0;max=min=sum=tmp;count+;while(tmp!=0)cintmp;if(tmp!=0)sum+=tmp;count+;if(tmpmax)max=tmp;if(tmpmi
32、n)min=tmp;coutmax,min,sum/countendl;return0;输入：12345607输出：2 .#includeusingnamespacestd;intmain()CCFNOIP2016初赛普及组C+语言试题第5页，共9页inti=100,x=0,y=0;while(i0)i-；x=i%8;if(x=1)y+;coutyendl;return0;输出：3 .#includeusingnamespacestd;intmain()inta6=1,2,3,4,5,6);intpi=0;intpj=5;intt,i;while(pipj)t=api;api=apj;apj=
33、t;pi+;pj-5for(i=0;i6;i+)coutai,;coutendl;return0;输出：4 .#includeusingnamespacestd;intmain()inti,Iengthl,length2;stringsi,s2;si=Ihaveadream.;CCFNOIP2016初赛普及组C+语言试题第6页，共9页s2=IHaveADream.,;Iengthl=sl.size();length2=s2.size();for(i=0;i=a,&sli=,z)sli-=,a,-,A,;for(i=0;i=,a,&s2i=,z)s2i-=,a,-,A,;if(si=s2)cou
34、t=s2)coutendl;elsecout,endl;return0;输出：四、完善程序(共2题，每题14分,共计28分)1.(读入整数)请完善下面的程序，使得程序能够读入两个int范围内的整数,并将这两个整数分别输出，每行一个。(第一、五空2.5分，其余3分)输入的整数之间和前后只会出现空格或者回车。输入数据保证合法。例如：输入：123-789输出：123-789#includeusingnamespacestd;intreadint()intnum=0;/存储读取到的整数intnegative=0;/负数标识charc;/存储当前读取到的字符c=cin.get();while(c,9,)
35、&c!=-)c=(1)CCFNOIP2016初赛普及组C+语言试题第7页，共9页if(c=negative=1;else(2)c=cin.get();while(3)(4)c=cin.get();if(negative=1)returnnum;intmain()inta,b;a=readint();b=readint();coutaendlbendl;return0;2.(郊游活动)有n名同学参加学校组织的郊游活动，己知学校给这n名同学的郊游总经费为A元，与此同时第i位同学自己携带了Mi元。为了方便郊游，活动地点提供B(n)辆自行车供人租用，租用第j辆自行车的价格为Cj元，每位同学可以使用自己
36、携带的钱或者学校的郊游经费，为了方便账务管理，每位同学只能为自己租用自行车，且不会借钱给他人，他们想知道最多有多少位同学能够租用到自行车。(第四、五空2.5分，其余3分)本题采用二分法。对于区间l,r,我们取中间点mid并判断租用到自行车的人数能否达到mido判断的过程是利用贪心算法实现的。#includeusingnamespacestd;#defineMAXN1000000intn,B,A,MMAXN,CMAXN,1,r,ans,mid;boolcheck(intnn)intcount=0,i,j;i=(1)while(i=n)if(2)CCFNOIP2016初赛普及组C+语言试题第8页，
37、共9页Cj - Mi；count+=i+；j+；return(3)voidsort(inta,int1,intr)inti=1,j=r,x=a(l+r)/2,y;while(i=j)while(aix)j-;if(i=j)Y=ai;ai=aj;aj=y;i+；j-；if(ir)SOrt(a,i,r);if(1nBA;for(i=1;iMi;for(i=1;iCi;sort(M,1,n);SOrt(J1,B);1=0;r=n;while(1=r)mid=(1+r)/2;if()ans=mid;1=mid+1;elser=(4)(5)coutans=O&c=48&c=57(4)num=num*l()+c-()或num
