完整NOIP2010提高组初赛试题及详细解析

1、第十六届全国青少年信息学奥林匹克联赛初赛试题（提高组C+语言两小时完成）全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效、单项选择题（共10题，每题1.5分，共计15分。每题有且仅有一个正确选项。）1 .与十六进制数A1.2等值的十进制数是（A.101.2B.111.4C.161.125D.177.252 .一个字节（byte）由（）个二进制组成。B. 16C. 32D.以上都有可能3 .以下逻辑表达式的值恒为真的是(A.PV(rPAQ)V(rPAnQ)C.PVQV(PArQ)V3PAQ)。B.QV(rPAQ)V(PAnQ)D.PVrQV(PArQV(nPAnQ)4 .Linux下可执行文

2、件的默认扩展名是（）。A.exeB.comC.dll都不是D.以上5 .如果在某个进制下等式7*7=41成立，那么在该进制下等式12*12=（）也成立。A.100B.144C.164D.1966.提出“存储程序”的计算机工作原理的是（A.克劳德？香农B.戈登？摩尔）。C.查尔斯？巴比奇D.冯？诺依曼7.前缀表达式“+3*2+512”的值是（A.235B.25C.37D.8 .主存储器的存取速度比中央处理器（CPU）的工作速度慢的多，从而使得后者的效率受到影响。而根据局部性原理，CPU所访问的存储单元通常都趋于一个较小的连续区域中。于是，为了提高系统整体的执行效率，在CPU中弓I入了（）。A,寄

3、存器B.高速缓存C.闪存D.外存9 .完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置上，则第k号结点的父结点如果存在的话，应当存放在数组中的（）号位置。A.2kB,2k+1C.k/2下取整D.（k+1）/210 .以下竞赛活动中历史最悠久的是（）。A.全国青少年信息学奥林匹克联赛（NOIP）B.全国青少年信息学奥林匹克竞赛（NOI）C.国际信息学奥林匹克竞赛（IOI）D.亚太地区信息学奥林匹克竞赛（APIO）二、不定项选择题（共10题，每题1.5分，共计15分。每题正确答案的个数不少于1。多选或少选均不得分）。1

4、 .元素R1、R2、R3R4R5入栈的顺序为R1、R2、R3R4R5。如果第1个出栈的是R3,那么第5个出栈的可能是（）。A.R1B.R2C.R4D.R52 .Pascal语言，C语言和C+聪言都属于（）。A.高级语言B.自然语言C.解释性语言D.编译性语言3 .原地排序是指在排序过程中（除了存储待排序元素以外的）辅助空间的大小与数据规模无关的排序算法。以下属于原地排序的有（）。A.冒泡排序B.插入排序C.基数排序D.选择排序4 .在整数的补码表示法中，以下说法正确的是（）。A.只有负整数的编码最高位为1B.在编码的位数确定后，所能表示的最小整数和最大整数的绝对值相同C.整数0只有一个唯一的编

5、码D.两个用补码表示的数相加时，如果在最高位产生进位，则表示运算溢出5 .一颗二叉树的前序遍历序列是ABCDEFG后序遍历序列是CBFEGDA则根结点的左子树的结点个数可能是（）。A.0B.2C.4D.66 .在下列HTMLg句中，可以正确产生一个指向NOI官方网站的超链接的是（）。ABC.D<aurl="http:"><ahref="http:"><a></a><aname"">欢迎访问NOI网站</a>欢迎访问NOI网站</a>欢迎访问NOI网站&

6、lt;/a>7 .关于拓扑排序，下列说法正确的是（）。A.所有连通的有向图都可以实现拓扑排序B.对同一个图而言，拓扑排序的结构是唯一的C.拓扑排序中入度为0的结点总会排在入度大于0的结点的前面D.拓扑排序结果序列中的第一个结点一定是入度等于0的点8 .一个平面的法线是指与该平面垂直的直线。过点（1,1,1）、（0,3,0）、（2,0,0）的平面的法线是（）。A.过点（1,1,1）、（2,3,3）的直线B.过点（1,1,1）、（3,2,1）的直线C.过点（0,3,0）、（-3,1,1）的直线D.过点（2,0,0）、（5,2,1）的直线9 .双向链表中有两个指针域llink和rlink,分别

7、指向该结点的前驱及后继。设p指向链表中的一个结点，他的左右结点均为非空。现要求删除结点p,则下列语句序列中正确的是（）。A.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;dele

8、tep;D.p->llink->rlink=p->rlink;p->llink->rlink->link=p->llink;deletep;10 .今年（2010年）发生的事件有（）。A.惠普实验室研究员VinayDeolalikar自称证明了什NPB.英特尔公司收购计算机安全软件公司迈克菲（McAfee）C.苹果公司发布iPhone4手机D.微软公司发布Windows7操作系统3 .问题求解（共2题，每空5分，共计10分）1 .LZW编码是一种自适应词典编码。在编码的过程中，开始时只有一部基础构造元素的编码词典，如果在编码的过程中遇到一个新的词条，则

9、该词条及一个新的编码会被追加到词典中，并用于后继信息的编码。举例说明，考虑一个待编码的信息串：“xyxyyyyxyx”。初始词典只有3个条目，第一个为x,编码为1;第二个为V,编码为2;第三个为空格，编码为3;于是串“xyx”的编码为1-2-1（其中-为编码分隔符），加上后面的一个空格就是1-2-1-3。但由于有了一个空格，我们就知道前面的“xyx”是一个单词，而由于该单词没有在词典中，我们就可以自适应的把这个词条添加到词典里，编码为4,然后按照新的词典对后继信息进行编码，以此类推。于是，最后得到编码：1-2-1-3-2-2-3-5-3-4。我们可以看到，信息被压缩了。压缩好的信息传递到接受方

10、，接收方也只要根据基础词典就可以完成对该序列的完全恢复。解码过程是编码过程的逆操作。现在已知初始词典的3个条目如上述，接收端收至编码信息为2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6,则解码后的信息串是2 .无向图G有7个顶点，若不存在由奇数条边构成的简单回路，则它至多有条边。3 .记T为一队列，初始时为空，现有n个总和不超过32的正整数依次入列。如果无论这些数具体为何值，都能找到一种出队的方式，使得存在某个时刻队列T中的数之和恰好为9,那么n的最小值是O4 .阅读程序写结果(共4题，每题8分，共计32分)1.#include<iostream>usingna

11、mespacestd;intmain()(constintSIZE=10;intdataSIZE,ij,cnt,n,m;cin»n»m;for(i=1;i<=n;i+)cin»datai;for(i=1;i<=n;i+)cnt=0;for(j=1;j<=n;j+)if(datai<dataj)|(dataj=datai&&j<i)cnt+;if(cnt=m)cout«datai«endl;)return0;)输入：5296-801687输出：2.#include<iostream>usi

12、ngnamespacestd;intmain()(constintSIZE=100;intna,nb,aSIZE,bSIZE,i,j,k;cin»na;for(i=1;i<=na;i+)cin»ai;cin»nb;for(i=1;i<=nb;i+)cin»bi;i=1;j=1；while(i<=na)&&(j<=r|b)(if(aik洵)(cout«ai«'i+；)else(cout«bj«'j+；)if(i<=na)for(k=i;k<=na;k

13、+)cout«ak«'if(j<=nb)for(k=j;k<=nb;k+)cout«bk«'return0;)输入：5135794261014输出：3.#include<iostream>usingnamespacestd;constintNUM=5;intr(intn)(inti;if(n<=NUM)return0;for(i=1;i<=NUM;i+)if(r(n-i)<0)returni;return-1;intmain()(intn;cin>>n;cout<<r(n)

14、<<endl;return0;)输入：16输出：4.#include<iostream>#include<cstring>usingnamespacestd;constintSIZE=100;intn,m,rSIZE;boolmapSIZESIZE,found;boolsuccessful()(inti;for(i=1;i<=n;i+)if(!mapriri%n+1)returnfalse;returntrue;)voidswap(int*a,int*b)(intt;t=*a;*a=*b;*b=t;)voidperm(intleft,intright)

15、(inti;if(found)return;if(left>right)(if(successful()(for(i=1;i<=n;i+)cout<<ri<<found=true;)return;)for(i=left;i<=right;i+)(swap(r+left,r+i);perm(left+1,right);swap(r+left,r+i);)intmain()(intx,y,i;cin>>n>>m;memset(map,false,sizeof(map);for(i=1;i<=m;i+)(cin>>x

16、>>y;mapxy=true;mapyx=true;)for(i=1;i<=n;i+)ri=i;found=false;perm(1,n);if(!found)cout<<"Nosolution!"<<endl;return0;)输入：9121 22 33 44 55 66 11 72 73 84 85 96 9输出：五.完善程序(第1题，每空2分，第2题，每空3分，共28分)1 .(过河问题)在一个月黑风高的夜晚，有一群人在河的右岸，想通过唯一的一根独木桥走到河的左岸,在伸手不见五指的黑夜里，过桥时必须借照灯光来照明，不幸白是，他

17、们只有一盏灯.另外，独木桥上最多能承受两个人同时经过，否则将会坍塌.每个人单独过独木桥都需要一定的时间，不同的人要的时间可能不同.两个人一起过独木桥时，由于只有一盏灯，所以需要的时间是较慢的那个人单独过桥所花费的时间.现在输入N(2<=N<1000)和这N个人单独过桥需要的时间，请计算总共最少需要多少时间，他们才能全部到达河左岸.例如，有3个人甲、乙、丙，他们单独过桥的时间分别为1、2、4,则总共最少需要的时间为7.具体方法是：甲、乙一起过桥到河的左岸，甲单独回到河的右岸将灯带回，然后甲、丙在一起过桥到河的左岸，总时间为2+1+4=7.#include<iostream>

18、;#include<cstring>usingnamespacestd;constintSIZE=100;constintINFINITY=10000;constboolLEFT=true;constboolRIGHT=false;constboolLEFT_TO_RIGHT=true;constboolRIGHT_TO_LEFT=false;intn,hourSIZE;boolposSIZE;intmax(inta,intb)if(a>b)returna;elsereturnb;intgo(boolstage)inti,j,num,tmp,ans;if(stage=RIGH

19、T_TO_LEFT)num=0;ans=0;for(i=1;i<=n;i+)if(posi=RIGHT)(num+;if(houri>ans)ans=houri;if(9)returnans;ans=INFINITY;for(i=1;i<=n-1;i+)if(posi=RIGHT)for(j=i+1;j<=n;j+)if(posj=RIGHT)(posi=LEFT;posj=LEFT;tmp=max(houri,hourj)+if(tmp<ans)ans=tmp;posi=RIGHT;posj=RIGHT;returnans;if(stage=LEFT_TO_RI

20、GHT)(ans=INFINITY;for(i=1;i<=n;i+)if(®)(posi=RIGHT;tmp=if(tmp<ans)ans=tmp;returnans;)return0;)intmain()(inti;cin>>n;for(i=1;i<=n;i+)(cin>>houri;posi=RIGHT;)cout<<goRIGHT_TO_LEFT)<<endl;return0;)2.(烽火传递)烽火台又称烽燧，是重要的军事防御设施，一般建在险要处或交通要道上。一旦有敌情发生，白天燃烧柴草，通过浓烟表达信息；夜晚燃

21、烧干柴，以火光传递军情。在某两座城市之间有n个烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确地传递，在连续的m个烽火台中至少要有一个发出信号。现输入n、m和每个烽火台发出信号的代价，请计算总共最少花费多少代价，才能使敌军来袭之时，情报能在这两座城市之间准确传递。例如，有5个烽火台，他们发出信号的代价依次为1,2,5,6,2,且m为3,则总共最少花费代价为4,即由第2个和第5个烽火台发出信号。#include<iostream>#include<cstring>usingnamespacestd;constintSIZE=100;intn,m,r,valueSI

22、ZE,heapSIZE,posSIZE,homeSIZE,optSIZE;/hepi表示用顺序数组储存的堆heap中第i个元素的值posi表示opti在堆heap中的位置，即heapposi=optihomei表示heapi在序歹Uopt中的位置，即opthomei=heapivoidswap(inti,intj)交换堆中的第i个和第j个元素(inttmp;poshomei=j;poshomej=i;tmp=heapi;headi=headj;heapj=tmp;tmp=homei;homei=homej;homej=tmp;)voidadd(intk)/在堆中插入optk(inti;r+;h

23、eapr=CD;posk=r;i=r;while(i>1)&&(heapi<heapi/2)(swap(i,i/2);i/=2;)voidremove(intk)/在堆中删除optk(inti,j;i=posk;swap(i,r);r-;if(i=r+1)return;while(i>1)&&(heapi<heapi/2)(swap(i,i/2);i/=2;)while(i+i<=r)(if(i+i+1<=r)&&(heapi+i+1<heapi+i)j=i+i+1;elseif(heai>heap

24、j)(i=j;)elsebreak;intmain()(inti;cin>>n>>m;for(i=1;i<=n;i+)cin>>valuei;r=0;for(i=1;i<=m;i+)(opti=valuei;add(i);)for(i=m+1;i<=n;i+)(opti=®remove(®);add(i);)cout<<heap1<<endl;return0;1.十六进制，A1=10*16+1*00,2=2*(1/16)所以答案选C2.考察计算机基础知识，一个字节有8个二进制位组成，即1byte=

25、8bits,往后是1kb=1024b,1mb=1024kb,所以答案选A3 .A考查语言基础之表达式计算之逻辑运算。口诀：一真或真，一假且假，p和非p不相往来。A选项中(正八Q)V(?PA?Q/、和7P同真同假，且P和7P必有一真，故A项正确；B选项中，若P为FalseQ为False则QV(中八Q)V(PA7Q)=&FVF=False故B项错误；C选项中，若P为FalseQ为False则PVQV(PA?Q)V(?DAQ)=P/QVFVF=False故C项错误；D选项中，若P为FalseQ为True则4 .考查计算机基础知识值计算机基础。一般来说，linux下可执行文件没有扩展名，lin

26、ux不根据扩展名判断文件类型，而是根据文件的内容来判断，windows下可执行文件的扩展名为exe,汇编语言编译的可执行文件扩展名为com；dll,即动态链接库文件，是一种可执行文件，它允许程序共享执行特定任务所必须的代码和资源，故选D5 .考查进制转换，7*7在十进制中应该是等于49的，但是在题目所对应的进制中等于41,4*12+1=49,说明题目所对应的进制是12,故12*12在12进制中应该是100,选A6 .考查计算机的基础知识，计算机基本工作原理是存储程序和程序控制，它是由美籍匈牙利数学家冯诺依曼提出的，因此冯诺依曼被称为“计算机之父”，故选D7 .考察语言基础值表达式计算。前缀表达

27、式的算法是构造一个运算符栈，满足入栈的两个数能和离栈顶最近的运算符进行运算时进行计算并整理到栈顶，在题目所给出的表达式中，首先+入栈，3入栈，*入栈，2入栈，+入栈，5入栈，12入栈，此时+512可以进行运算得到17,*217得到34,+334得到37,所以最后答案就是37.选C8 .考察计算机硬件系统，高速缓冲存储器是存在于主存与CPU之间的一级存储器，有静态存储芯片组成，容量比较小，但是速度比主存快的多，接近于CPU的速度，在计算机存储系统的层次结构中，是介于中央处理器和主存储器之间的高速小容量存储器，它和主存储器一起构成一级的存储器，高速缓冲存储器和主存储器之间的信息调度和传送是有硬件自

28、动进行的。故选B9 .考察二叉树的存储，对于一颗完全二叉树，树的根节点在1位置，i节点的的左子节点为2*i,右子节点为2*i+1o且对于任意节点而言，其父节点为i/2,向下取整。故选C10 .A:全国青少年信息学奥林匹克联赛(NationalOlympiadinInformaticsinProvinces,简称NOIP)自1995年至今已举办16次。B:1984年邓小平指出：“计算机的普及要从娃娃做起。”教育部和中国科协委托中国计算机学会举办了全国青少年计算机程序设计竞赛(简称：NOI),1984年参加竞赛的有8000多人。C:1987年，保加利亚的Sendov教授在联合国教科文组织第24届全

29、体会议上，倡议举行国际信息学奥林匹克，定名为InternationalOlympiadinInformatics,简称IOI。D:IOI2006期间，部分亚洲与太平洋地区参赛团领队在多次领队会协商的基础上，经IOI主席、IOI国际委员会与科学委员会批准决定从2007年开始举办该项赛事二,多项选择题：1.BCD,在R3入栈之前，堆栈应该是R1,R2因此，R2肯定在R1之前出栈，所以R2不可能是最后一个出栈的，除此之外，其他元素都有可能。2 .AD,这三种语言都是抽象层次较高的高级语言，溶蚀也是编译语言，需要编译运行3 .ABD,冒泡排序与插入排序与选择排序都不需要额外的空间，而基数排序需要额外的

30、哈希空间。4 .AC。补码特性，正0和负0表示相同，最高位产生进位的话，由于计算机的运算器内存空间是固定的，所以会将新产生的最高位去掉，不会溢出。5 .B,显然根节点是A,然后有前序遍历第一个节点是B,后序遍历倒数第二个节点是D可以得到，B属于左子树的根节点，D属于右子树的根节点。由于D是右子树的根节点，故左子树只有BC两个节点。6 .B.Href超文本应用，a标签的href树形用于指定超链接目标的URL,name属性用来指定ANCHOR的名称。7,拓扑排序从入度等于0的节点出发，只要求有边的直接或间接指向关系的节点的出现次序，并没有要求没有直接或间接相连的节点的关系，故入度为0的点不一定在入

31、度大于0的节点前面。8.D.因为点(1,1,1)与点(2,0,0)形成的向量为(1,-1,-1)因为法向量与平面上向量的乘积为0,所以D满足要求。9.BCD如果要删除一个双向链表的一个节点P,则P的右节点的左指针应该指向P现在的左节点，P的左节点的右指针应该指向现在P节点的右节点，故答案BCD10.ABC。百度可知，答案ABC三.问题求解：1.yyxyxxyyxyxyxxxxyx注意在解得时候只知道1->x;2->y;3->''至于4,5是不能沿用上一个而是这个新的的，所以4->yyxy;5->xx;6->xyx。2.12首先理解回路：闭合环

32、路，因为不存在由奇数边构成的简单回路，由于是无向图，所以最多12条3.18设T的队列顺序为a1,a2,a3an，设bi为前i项数之和，贝Ub0=0,b1=a1,b2=a1+a2,b3=a1+a2+a3。如队列T中的数之和恰好为9,实际上即是找到某个bj和bi，使得bj-bi=9。由题意可知bi取值范围为1-32,现将这32个数构造为集合1,10,2,11,，8,17,18,27,19,28,23,32,24,25,26,这17个集合中的任一个集合不能包含两个或两个以上的，否则它们的差为9。例如设n=17时，队列T为111111111011111111,即b1=1,b2=2,b8=8,b9=18,b10=19,b11=20b17=26,它们中没有任意两个数是在同一集合内的，所以不存在数之和恰好等于9。故根据抽屉原理可得，当n=18时，至少存在两个在同一个集合，即它们的差为9。因此，答案为n=18o四.1 .分析一下代码的意思，对于数组中的每一个元素，找到大于等于他的个数A,如果这个个数A=m的话，就输出这个数。(输出数组中符合条件的数，条件是，这个数组中大于等于该数值的元素个数为m)所以输出应该是：162 .分析一下代码的意思，其实是类似于归并排序合并两个有序的小数组时候的操作一样