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

1、第十六届全国青少年信息学奥林匹克联赛初赛试题（ 提高组 C+ 语言 两小时完成 ） 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 、单项选择题 （共 10 题，每题 1.5 分，共计 15 分。每题有且仅有一个正确选项。 ）2一个字节（ byte ）由（ ）个二进制组成。 A 8B16上都有可能3以下逻辑表达式的值恒为真的是（）。A . PV（n PA Q）V （n P心 Q） BC . PV QV（ PAn Q）V（n PA Q）D4 Linux 下可执行文件的默认扩展名是 （ ） 。A. exeB. com都不是C32D .以QV(n PA Q)V(PAn Q)PVnQV( PAn

2、QV (n PAn Q)C.dllD.以上5 如果在某个进制下等式7*7=41 成立，那么在该进制下等式 12*12= （A. 100B. 144C. 164）也成立。D. 1966 提出“存储程序”的计算机工作原理的是（A.克劳德 ?香农B.戈登?摩尔）。C.查尔斯 ?巴比奇D.冯?诺依曼7 前缀表达式“ + 3 * 2 + 512 ” 的值是（ ）。A. 23B. 25C. 37D. 61与十六进制数 A1.2 等值的十进制数是（)A 101.2B 111.4C 161.125D 177.25&主存储器的存取速度比中央处理器（CPU）的工作速度慢的多，从而使得后者的效率受到影响。而

3、根据局部性原理，CPU所访问的存储单元通常都趋于一个较小的连续区域中。于是，为了提高系统 整体的执行效率，在 CPU中引入了（）。A 寄存器B 高速缓存C 闪存D 外存9完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序 结构的数组中。假定根结点存放在数组的 1 号位置上，则第 k 号结点的父结点如果存在的话，应当 存放在数组中的（）号位置。A 2kB 2k+1C k/2 下取整D （k+1）/210以下竞赛活动中历史最悠久的是（）。A 全国青少年信息学奥林匹克联赛（NOIP）B. 全国青少年信息学奥林匹克竞赛（NOI）C. 国际信息学奥林匹克竞赛（101 ）

4、D .亚太地区信息学奥林匹克竞赛（API0）、不定项选择题 （共 10题，每题 1.5 分，共计15 分。每题正确答案的个数不少于1。多选或少选均不得分）。1 .兀素R1、R2、R3 R4R5入栈的顺序为R1、R2、R3R4、R5。如果第1个出栈的是 R3,那么第5 个出栈的可能是 （) 。A . R1B . R2C . R4D. R52. Pascal 语言，C 语言和C+语言都属于（) 。A .高级语言B.自然语言C.解释性语言D.编译性语言3.原地排序是指在排序过程中 算法。以下属于原地排序的有A .冒泡排序B（ 除了存储待排序元素以外的 ） 辅助空间的大小与数据规模无关的排序 （ ）

5、。.插入排序C .基数排序D .选择排序4. 在整数的补码表示法中，以下说法正确的是（ ）。A .只有负整数的编码最高位为 1B .在编码的位数确定后，所能表示的最小整数和最大整数的绝对值相同C .整数 0只有一个唯一的编码D .两个用补码表示的数相加时，如果在最高位产生进位，则表示运算溢出5. 颗二叉树的前序遍历序列是ABCDEFG后序遍历序列是 CBFEGD，则根结点的左子树的结点个数可能是（）。A . 0B. 2C. 4D. 66 .在下列HTML语句中，可以正确产生一个指向N0I官方网站的超链接的是（）。A.<a url="">欢迎访问N0I 网站 &l

6、t;/a>B.<a href="">欢迎访问N0I 网站 </a>C.<a></a>D.<a name"">欢迎访问NOI 网站 </a>7.关于拓扑排序，下列说法正确的是（） 。A .所有连通的有向图都可以实现拓扑排序B .对同一个图而言，拓扑排序的结构是唯一的C .拓扑排序中入度为 0的结点总会排在入度大于 0的结点的前面D .拓扑排序结果序列中的第一个结点一定是入度等于 0 的点8 .一个平面的法线是指与该平面垂直的直线。过点（ ）。（1,1,1） 、（ 0,3,0 ）、

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

8、ink=p->rlink;p->rlink->llink = p->llink; delete p;C . p->rlink->llink = p->llink;p->rli nk->lli nk ->rl ink = p->rl ink; delete p;D . p->llink->rlink = p->rlink;p->llink->rlink->link = p->llink; delete p;10 .今年（2010年）发生的事件有（）。A 惠普实验室研究员Vi nay Deo

9、lalikar自称证明了 吐NPB .英特尔公司收购计算机安全软件公司迈克菲（McAfee）C .苹果公司发布iPhone 4手机D .微软公司发布 Windows 7操作系统三问题求解（共 2题，每空5分，共计10分）1. LZW编码是一种自适应词典编码。在编码的过程中，开始时只有一部基础构造元素的编码词典， 如果在编码的过程中遇到一个新的词条，则该词条及一个新的编码会被追加到词典中，并用于后继 信息的编码。举例说明，考虑一个待编码的信息串："xyx yy yy xyx"。初始词典只有 3个条目，第一个为x,编码为1;第二个为y，编码为2;第三个为空格，编码为3 ;于是串

10、"xyx ”的编码为1-2-1（其中-为编码分隔符），加上后面的一个空格就是1-2-1-3。但由于有了一个空格，我们就知道前面的“ xyx”是一个单词，而由于该单词没有在词典中，我们就可以自适应的把这个词条添加到词典 里，编码为4,然后按照新的词典对后继信息进行编码，以此类推。于是，最后得到编码：121-3-2-2-3-5-3-4。我们可以看到，信息被压缩了。压缩好的信息传递到接受方，接收方也只要根据基础词典就可以完成对该序列的完全恢复。解码过程是编码过程的逆操作。现在已知初始词典的3个条目如上述，接收端收到的编码信息为2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-

11、6，则解码后的信息串是a?2.无向图G有7个顶点，若不存在由奇数条边构成的简单回路，则它至多有条边。3 .记T为一队列，初始时为空，现有n个总和不超过32的正整数依次入列。如果无论这些数具体为何值，都能找到一种出队的方式，使得存在某个时刻队列T中的数之和恰好为 9,那么n的最小值是。四阅读程序写结果（共 4题，每题8分，共计32 分）1 .#in clude<iostream>using n amespace std;int mai n()const int SIZE=10;int dataSIZE,i,j,c nt,n,m;cin»n»m;for(i=1;i&

12、lt;=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) cn t+;if (cn t=m)cout<<datai<<e ndl;return 0;输入：5 296 -8 0 16 87输出：2.#in clude<iostream>using n amespace std;int mai n()const int SIZE=100;int n a, nb,aS

13、IZE,bSIZE,i,j,k;cin»na;for(i=1;i<=n a;i+)cin> >ai;cin»nb;for(i=1;i<=n b;i+)cin> >bi;i=1;j=1;while( (i<=na)&&(j<=nb) ) if(ai<=bj)cout<<ai<<' ' i+;elsecout<<bj<<' ' j+;if(i<=na)for(k=i;k<=na;k+) cout<<ak&l

14、t;<' 'if(j<=nb)for(k=j;k<=nb;k+) cout<<bk<<' 'return 0;输入：51 3 5 7 942 6 10 14输出： 3#include<iostream>using namespace std;const int NUM=5;int r(int n)int i;if(n<=NUM)return 0; for(i=1;i<=NUM;i+)if( r(n-i)<0)return i;return -1;int main()int n;cin>

15、>n;cout<<r(n)<<endl;return 0;输入：16输出： 4#include<iostream> #include<cstring> using namespace std;const int SIZE=100;int n,m,rSIZE;bool mapSIZESIZE,found;bool successful()int i;for(i=1;i<=n;i+) if(!mapriri%n+1) return false;return true;void swap(int *a,int *b)int t;t=*a;*

16、a=*b;*b=t;void perm(int left,int right)int i;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);int main()int x,y,i;cin>>n>>m;memset(ma

17、p,false,sizeof(map);for(i=1;i<=m;i+)cin>>x>>y;mapxy=true;mapyx=true;for(i=1;i<=n;i+)ri=i;found=false;perm(1,n);if(!found)cout<<"No solution!"<<endl;return 0;输入：9 121 22 33 44 55 66 11 72 73 84 85 96 9输出： 五完善程序 ( 第 1 题，每空 2 分，第 2 题，每空 3 分，共 28 分 )1 (过河问题 ) 在一个月

18、黑风高的夜晚 , 有一群人在河的右岸 ,想通过唯一的一根独木桥走到河的左 岸.在伸手不见五指的黑夜里,过桥时必须借照灯光来照明 ,不幸的是 ,他们只有一盏灯 .另外, 独木桥上最多能承受两个人同时经过 , 否则将会坍塌 . 每个人单独过独木桥都需要一定的时间 , 不同的人要 的时间可能不同 . 两个人一起过独木桥时 , 由于只有一盏灯 ,所以需要的时间是较慢的那个人单独过 桥所花费的时间现在输入N(2<=N<1000)和这N个人单独过桥需要的时间，请计算总共最少需要多少 时间 , 他们才能全部到达河左岸 .例如,有3个人甲、乙、丙，他们单独过桥的时间分别为1、2、4,则总共最少需要

19、的时间为7.具体方法是 :甲、 乙一起过桥到河的左岸 ，甲单独回到河的右岸将灯带回 ，然后甲、 丙在一起过桥到河 的左岸 , 总时间为 2+1+4=7.#include<iostream>#include<cstring>using namespace std;const int SIZE=100;const int INFINITY = 10000;const bool LEFT=true;const bool RIGHT =false;const bool LEFT_TO_RIGHT=true;const bool RIGHT_TO_LEFT=false;int n

20、,hourSIZE;bool posSIZE;int max(int a,int b)if(a>b)return a;elsereturn b;int go(bool stage)int i,j,num,tmp,ans;if(stage=RIGHT_TO_LEFT)num=0;ans=0;for(i=1;i<=n ;i+)if(posi=RIGHT)nu m+;if( houri>a ns)an s=houri;if()return ans;an s=INFINITY;for(i=1;i<=n _1;i+)if(posi=RIGHT)for(j=i+1;j<=n

21、;j+) if(posj=RIGHT)posi=LEFT;posj=LEFT;tmp=max(houri,hourj)+ if(tmp<a ns)an s=tmp;posi=RIGHT;posj=RIGHT;return ans;if(stage=LEFT_TO_RIGHT)an s=INFINITY;for(i=1;i<=n ;i+)if()posi=RIGHT;tmp=if(tmp<a ns)an s=tmp;return ans;return 0;int main()int i;cin>>n;for(i=1;i<=n;i+)cin>>hou

22、ri;posi=RIGHT;cout<<goRIGHT_TO_LEFT)<<endl;return 0;2. (烽火传递) 烽火台又称烽燧，是重要的军事防御设施，一般建在险要处或交通要道上。一旦有 敌情发生，白天燃烧柴草，通过浓烟表达信息；夜晚燃烧干柴，以火光传递军情。在某两座城市之 间有 n 个烽火台，每个烽火台发出信号都有一定的代价。为了使情报准确地传递，在连续的 m 个烽 火台中至少要有一个发出信号。现输入n、 m 和每个烽火台发出信号的代价，请计算总共最少花费多少代价，才能使敌军来袭之时，情报能在这两座城市之间准确传递。例如，有5个烽火台，他们发出信号的代价依次

23、为 1, 2, 5, 6, 2,且m为3,则总共最少花费代 价为 4，即由第 2 个和第 5 个烽火台发出信号。#include<iostream>#include<cstring>using namespace std;const int SIZE=100;int n,m,r,valueSIZE,heapSIZE,posSIZE,homeSIZE,optSIZE;hepi表示用顺序数组储存的堆heap中第i个元素的值posi表示 opti在堆 heap 中的位置，即 heapposi=opti/homei 表示 heapi 在序列 opt 中的位置,即 opthome

24、i=heapivoid swap(int i,int j)/ 交换堆中的第 i 个和第 j 个元素int tmp;poshomei=j;poshomej=i;tmp=heapi;headi=headj;heapj=tmp;tmp=homei;homei=homej;homej=tmp;void add(int k) 在堆中插入 optkint i;r+;heapr= ;posk=r; ;i=r;while( (i>1) && (heapi<heapi/2)swap(i,i/2);i/=2;void remove(int k)/ 在堆中删除 optkint i,j;i

25、=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<he api+i) j=i+i+1;else;if(heai>heapj);i=j; elsebreak;int mai n()int i;cin»n»m;for(i=1;i<=n ;i+)cin> >valuei;r=0;for(i=1;i&l

26、t;=m;i+)opti=valuei; add(i);for(i=m+1;i<=n ;i+)opti= ;remove();add(i);cout<<heap1<<e ndl;return 0;1. 十六进制，A1 = 10 * 16 + 1 * 0 0.2 = 2 *(1/16 )所以答案选 C2 .考察计算机基础知识，一个字节有8个二进制位组成，即1byte = 8bits ，往后是1kb = 1024b ,1mb = 1024kb, 所以答案选 A3. A。考查语言基础之表达式计算之逻辑运算。口诀：一真或真，一假且假，p和非p不相往来。A选项中(扌人Q)V

27、 (?PA ?Q必和?P同真同假，且P和?P必有一真，故A项正确；B选项中，若P为FalseQ为False 贝U QV (中A Q)V (PA ?Q)=V FV F=False故 B 项错误；C 选项中，若 P 为 False Q 为 False 贝UPV QV (PA ?Q)V (扌A Q)=FV QV FV F=False故 C 项错误；D 选项中，若 P 为 False Q 为 True 贝U4. 考查计算机基础知识值计算机基础。一般来说，linux下可执行文件没有扩展名，linux 不根据扩展名判断文件类型，而是根据文件的内容来判断，windows 下可执行文件的扩展名为exe，汇编语

28、言编译的可执行文件扩展名为com ； dll ，即动态链接库文件，是一种可执行文件，它允许程序共享执行特定任务所必须的代码和资源，故选D5. 考查进制转换，7 * 7在十进制中应该是等于49的，但是在题目所对应的进制中等于41，4 * 12+ 1 = 49，说明题目所对应的进制是12，故12 * 12 在12进制中应该是100，选A6. 考查计算机的基础知识，计算机基本工作原理是存储程序和程序控制，它是由美籍匈牙利数学家冯诺依曼提岀的，因此冯诺依曼被称为“计算机之父”，故选D7. 考察语言基础值表达式计算。前缀表达式的算法是构造一个运算符栈，满足入栈的两个数能和离栈顶最近的运算符进行运算时进行

29、计算并整理到栈顶，在题目所给出的表达式中，首先+入栈，3入栈，*入栈，2入栈，+入栈，5入栈，12入栈，此时+5 12 可以进行运算得到17，*2 17 得到34，+ 3 34得到37，所以最后答案就是37.选C8. 考察计算机硬件系统，高速缓冲存储器是存在于主存与CPU之间的一级存储器，有静态存储芯片组成，容量比较小，但是速度比主存快的多，接近于CPU的速度，在计算机存储系统的层次结构中，是介于中央处理器和主存储器之间的高速小容量存储器，它和主存储器一起构成一级的存储器，高速缓冲存储器和主存储器之间的信息调度和传送是有硬件自动进行的。故选B9. 考察二叉树的存储，对于一颗完全二叉树，树的根节

30、点在1位置，i节点的的左子节点为2*i ，右子节点为2*i+1 。且对于任意节点而言，其父节点为i/2,向下取整。故选 C10. A:全国青少年信息学奥林匹克联赛(National Olympiad in Informatics in Provinces，简称NOIP )自1995年至今已举办16次。B:1984 年邓小平指岀：“计算机的普及要从娃娃做起。”教育部和中国科协委托中国计算机学会举办了全国青少年计算机程序设计竞赛(简称：NOI )，1984年参加竞赛的有8000多人。C:1987年，保加利亚的 Sendov教授在联合国教科文组织第24届全体会议上,倡议举行国际信息学奥林匹克，定名为

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

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

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

34、不存在由奇数边构成的简单回路，由于是无向图，所以最多12条3.18 设T的队列顺序为 a1,a2,a3an，设bi为前i项数之和，贝U b0=0 ，b仁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为1111111110 11111111 ，即b1=1,b2 =2

35、,b8=8, b9 =18, b10=19,b1仁20b17=26,它们中没有任意两个数是在同一集合内的，所以不存在数之和恰好等于9。故根据抽屉原理可得，当n=18时，至少存在两个在同一个集合，即它们的差为9。因此，答案为 n=18。四.1. 分析一下代码的意思，对于数组中的每一个元素，找到大于等于他的个数A，如果这个个数 A=m的话，就输岀这个数。(输岀数组中符合条件的数，条件是，这个数组中大于等于该数值的元素个数为m)所以输岀应该是：162. 分析一下代码的意思，其实是类似于归并排序合并两个有序的小数组时候的操作一样的，这里是输岀 两个有序的小数组，使得最后的输岀有序。输岀：1 2 3 5 6 7 9 143.4考察递归的思想，r(0)-r(5) 都会返回0, r(6)递归