NOIP2011提高组初赛试题_C++含答案.docx

《NOIP2011提高组初赛试题_C++含答案.docx》由会员分享，可在线阅读，更多相关《NOIP2011提高组初赛试题_C++含答案.docx（20页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、NOIP2011提高组初赛试题_C+含答案NOIP2020第十七届全国青少年信息学奥林匹克联赛初赛试题提高组C+语言两小时完成全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效一、单项选择题共10题，每题1.5分，共计15分。每题有且仅有一个正确选项。1在二进制下，1011001+=1100110。A1011B1101C1010D11112字符“A的ASCII码为十六进制41，则字符“Z的ASCII码为十六进制的。A66B5AC50D视详细的计算机而定3右图是一棵二叉树，它的先序遍历是。AABDEFCBDBEFACCDFEBCADABCDEF4寄存器是的重要组成部分。A硬盘B高速缓存C内存D

2、中央处理器CPU5广度优先搜索时，需要用到的数据构造是。A链表B队列C栈D散列表6在使用高级语言编写程序时，一般提到的“空间复杂度中的空间是指。A程序运行时理论上所占的内存空间B程序运行时理论上所占的数组空间C程序运行时理论上所占的硬盘空间D程序源文件理论上所占的硬盘空间7应用快速排序的分治思想，能够实现一个求第K大数的程序。假定不考虑极端的最坏情况，理论上能够实现的最低的算法时间复杂度为。AO(n2)BO(nlogn)CO(n)DO(1)8为解决web应用中的不兼容问题，保障信息的顺利流通，制定了一系列标准，涉及HTML、XML、CSS等，并建议开发者遵循。A微软B美国计算机协会ACMC联合

3、国教科文组织D万维网联盟W3C9体育课的铃声响了，同学们都陆续的奔向操场，按教师的要求从高到低站成一排。每个同学按顺序来到操场时，都从排尾走到排头，找到第一个比本人高的同学，并站在他的后面。这种站队的方法类似于算法。A快速排序B插入排序C冒泡排序D归并排序101956年授予肖克利WilliamShockley、巴丁JohnBardeen和布拉顿WalterBrattainA诺贝尔物理学奖B约翰冯诺依曼奖C图灵奖D高德纳奖DonaldE.KnuthPrize二、不定项选择题共10题，每题1.5分，共计15分。每题正确答案的个数不少于1。多项选择或少选均不得分。1假如根结点的深度记为1，则一棵恰有

4、2020个叶子结点的二叉树的深度可能是。A10B11C12D20202在布尔逻辑中，逻辑“或的性质有。A交换律：PVQ=QVPB结合律：PVQVR=PVQVRC幂等律：PVP=PD有界律：PV1=11表示逻辑真3一个正整数在十六进制下有100位，则它在二进制下可能有位。A399B400C401D4044汇编语言。A是一种与详细硬件无关的程序设计语言B在编写复杂程序时，相对于高级语言而言代码量大，且不易调试C能够直接访问寄存器、内存单元、I/O端口D随着高级语言的诞生，如今已被完全淘汰，不再使用5现有一段文言文，要通过二进制哈夫曼编码进行压缩。简单起见，假设这段文言文只由4个汉字“之、“乎、“者

5、、“也组成，它们出现的次数分别为700、600、300、400。那么，“也字的编码长度可能是。A1B2C3D46生物特征识别，是利用人体本身的生物特征进行身份认证的一种技术。目前，指纹识别、虹膜识别、人脸识别等技术已广泛应用于政府、银行、安全防卫等领域。下面属于生物特征识别技术及其应用的是。A指静脉验证B步态验证CATM机密码验证D声音验证7对于序列“7、5、1、9、3、6、8、4，在不改变顺序的情况下，去掉会使逆序对的个数减少3。A7B5C3D68计算机中的数值信息分为整数和实数浮点数。实数之所以能够表示很大或者很小的数，是由于使用了。A阶码B补码C反码D较长的尾数9对右图使用Dijkstr

6、a算法计算S点到其余各点的最短途径长度时，到B点的距离dB初始时赋为8，在算法的执行经过中还会出现的值有。A3B7C6D510为计算机网络中进行数据交换而建立的规则、标准或约定的集合称为网络协议。下列英文缩写中，是网络协议AHTTPBTCP/IPCFTPDWWW三问题求解共2题，每空5分，共计10分1平面图能够在画在平面上，且它的边仅在顶点上才能相交的简单无向图。4个顶点的平面图至少有6条边，如右图所示。那么，5个顶点的平面图至少有条边。2定义一种字符串操作，一次能够将其中一个元素移到任意位置。举例讲明，对于字符串“BCA能够将A移到B之前，变字符串“ABC。假如要将字符串“DACHEBGIF

7、变成“ABCDEFGHI最少需要_次操作。四阅读程序写结果共4题，每题8分，共计32分1#include#includeusingnamespacestd;constintSIZE=100;intmain()intn,i,sum,x,aSIZE;cinn;memset(a,0,sizeof(a);for(i=1;ix;ax+;i=0;sum=0;while(sumreturn0;输入：1145664332321输出：2#includeusingnamespacestd;intn;voidf2(intx,inty);voidf1(intx,inty)if(xn;f1(0,1);return0;r

8、eturn0;输入：30输出：_3#includeusingnamespacestd;constintV=100;intn,m,ans,eVV;boolvisitedV;voiddfs(intx,intlen)inti;visitedx=true;if(lenans)ans=len;for(i=1;inm;for(i=1;iabc;eab=c;eba=c;for(i=1;i414013502460输出：_4#include#include#includeusingnamespacestd;constintSIZE=10000;constintLENGTH=10;intn,m,aSIZELENG

9、TH;inth(intu,intv)intans,i;ans=0;for(i=1;in;memset(a,0,sizeof(a);m=1;while(1)i=1;while(in)break;m+;ami=1;for(j=i+1;jsum=0;for(i=1;i#includeusingnamespacestd;constintSIZE=200;structhugeintintlen,numSIZE;/其中len表示大整数的位数；num1表示个位，num2表示十位，以此类推hugeinttimes(hugeinta,hugeintb)/计算大整数a和b的乘积inti,j;hugeintans;

10、memset(ans.num,0,sizeof(ans.num);for(i=1;i0)ans.len=a.len+b.len;elseans.len=a.len+b.len-1;returnans;hugeintadd(hugeinta,hugeintb)/计算大整数a和b的和inti;hugeintans;memset(ans.num,0,sizeof(ans.num);if(a.lenb.len)ans.len=a.len;elseans.len=b.len;for(i=1;i0)ans.len+;returnans;hugeintaverage(hugeinta,hugeintb)/计

11、算大整数a和b的平均数的整数部分inti;hugeintans;ans=add(a,b);for(i=ans.len;i=2;i-)ans.numi-1+=()*10;ans.numi/=2;ans.num1/=2;if(ans.numans.len=0)ans.len-;returnans;hugeintplustwo(hugeinta)/计算大整数a加2之后的结果inti;hugeintans;ans=a;ans.num1+=2;i=1;while(i=10)ans.numi+1+=ans.numi/10;ans.numi%=10;i+;if(ans.numans.len+10);retu

12、rnans;boolover(hugeinta,hugeintb)/若大整数ab则返回true，否则返回falseinti;if()returnfalse;if(a.lenb.len)returntrue;for(i=a.len;i=1;i-)if(a.numib.numi)returntrue;returnfalse;intmain()strings;inti;hugeinttarget,left,middle,right;cins;memset(target.num,0,sizeof(target.num);target.len=s.length();for(i=1;iif(over()r

13、ight=middle;elseleft=middle;while(!over(plustwo(left),right);for(i=left.len;i=1;i-)coutusingnamespacestd;constintSIZE=100+5;constintINFINITY=1000000;intn,aSIZE,maxDeep,num;voidsolve(intleft,intright,intdeep)inti,j,min;if(deepmaxDeep)maxDeep=deep;num=1;elseif(deep=maxDeep);min=INFINITY;for(i=left;iai)min=ai;if(left当前位置：文档视界NOIP2020提高组初赛试题_C+含答案NOIP2020提高组初赛试题_C+含答案