noip2010提高组初赛试题解析

（C++语言二小时完成●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效与16进制数A1.2等值的10进制数是 ） ） ） 到影响。而根据局部性原理，CPU所的单元通常都趋于在一个较小的连续区域中。于是，为了提高系统整体的执行效率，在CPU中引入了（ 一个顺序结构的数组中。假定根结点存放在数组的1号位置，则第K号结点的父结点如果 C.k/2下取 ）二.选择题（共10题，每题1.5分，共计15分。每题有一个或多个正确选项。多选元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第一个出栈的是R3，那么第五个出栈的可能是（ C.0只有唯一的一个编码一颗二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左 在下列HTML语句中，可以正确产生一个指向NOI的超的是 <a ">欢迎NOI<a ">欢迎NOI <a ">欢迎NOI （1,1,1（1,1,1（0,3,0（2,0,0双向链表中有两个指针域llink和rlinkp指向链表中P,则下面语句序列中正确的是 ）A.p->rlink->llink=p-p->llink->rlink=p->llink;deleteB.P->llink->rlink=p-p->rlink->llnik=p->llink;deleteC.p->rlink->llink=p-p->rlink->llink->rlink=p->rlink;deleteD.p->llink->rlink=p-p->llink->rlink->llink=p->llink;delete 苹果公司发布4三、问题求解（3515分LZW编码是一种自适应词典编码。在编码的过程中，开始时只有一部基础构造元素的举例说明，考虑一个待编码的信息串：“xyxyyyyxyx”3个条目，第x,1y23；于是串“xyx”的编码1-2-1（其中-为编码分隔符），1-2-1-3。但由于有了一个空4，然后按照新的词典对后继信息进行编码，以此类 无向图G有7个顶点，若不存在由奇数条边构成的简单回路，则它至多有 记T为一队列，初始时为空，现有n个总和不超过32的正整数依次入列。如果无论这些数具体为何值，都能找到一种出队的方式，使得存在某个时刻队列T中的数之和恰好为9，那么n的最小值是 四.阅读程序写结果（4728分#include<iostream>usingnamespacestd;intmain()constintSIZEintdata[SIZE],i,j,cnt,n,m;for(i=1;i<=n;i++)for(i=1;i<=n;i++){cnt=0;for(j=1;j<=n;if((data[i]<data[j])||(data[j]==data[i]&&j<i))if(cnt==m)}return}596-8016#include<iostream>usingnamespacestd;int{constintintna,nb,a[SIZE],b[SIZE],i,j,k;for(i=1;i<=na;i++)for(i=1;i<=nb;i++)while((i<=na)&&(j<=nb)){if(a[i]<=b[j]){cout<<a[i]<<’‘;}elsecout<<b[j]<<’‘;}}if(i<=for(k=i;k<=na;k++)cout<<a[k]<<’‘;if(j<=for(k=j;k<=nb;k++)cout<<b[k]<<’‘;return}5135742610#include<iostream>usingnamespaceconstintNUM=5;intr(intn){inti;returnn;returni;return-}int{intn;return0;}#include<iostream>usingnamespacestd;constintsize=100;intboolbool{inti;returnfalse;return}voidswap(int*a,int{intt;}voidperm(intleft,int{inti;{{cout<<r[i]<<'}}{}}int{intx,y,i;{}cout<<"Nosoloution!"<<endl;return0;}91234569五、完善程序（12102.527分1.(过河问题)在一个月黑风高的夜晚,的左岸.在伸手不见五指的黑夜里,过桥时必须借照灯光来照明,不幸的是,他们只有一盏灯.另外,独木桥上最多能承受两个人同时经过,否则将会坍塌.每个人单独过独木桥都需要一定的时间,不同的人要的时间可能不同.两个人一起过独木桥时,由于只有一盏灯,所以需要的时间(<=N1000和这N的时间,,例如,3个人甲、乙、丙,124,则总共最少需要的时间为7.具体方法是:甲乙一起过桥到河的左岸,甲单独回到河的右岸将灯带回,然后甲,丙在一起过桥到河的左岸,2+1+4=7。#include<iostream>usingnamespaceconstintsize=100;constintinfinity=10000;constboolLeft=true;constboolRight=false;constboolleft_to_right=true;constboolright_to_left=false;intn,hour[size];boolpos[size];intmax(inta,int{returna;return}intgo(bool{inti,j,num,tmp,ans;{{} （1）)returnans;{ （2）}return}{ （3）{ （4）;（5）}return}return}int{inti;{}return0;}，2（有敌情发生，白天燃烧柴草，通过浓烟表达信息：夜晚燃烧，以火光传递军情。在某两座城市之间有n个烽火台，每个烽火台发出信号都有一定的代价。为了使准确的传递，mn、m和每个烽火台发出的信号的代价，请计算总共最少需要话费多少代价，才能使敌军来袭之时能在这两座城市之间准确的传，425个烽火台发出信号。#include<iostream>usingnamespacestd;constintsize=100;int//heap[i]表示用顺序数组的堆heap中第i个元素的值//pos[i]表示opt[i]在堆heap中的位置，即//home[i]表示heap[i]在序列opt中的位置，即voidswap(inti,int//交换堆中的第ij个元素{inttmp;}voidadd(int//在堆中插入{inti; （1）（2）;while((i>1)&&{}}voidremove(int//在堆中删除{inti,j;r--while((i>1)&&{}{if((i+i+1<=r)&&(heap[i+i+1]<heap[i+i]))（3）;{ }}}int{inti;{}{ （5）; }return0;}简单的进制转换，(A1.2)16=1016+1+216-1=161.125,因此答案选CABABAAAABA考查Linux基础知识，exe和com均是windows下的可执行文件，dll是动态库D。10=（196）10；（196）10=（144）12144B。克劳德·香农（ClaudeElwoodShannon，数学家、信息论的创始人；戈登·摩MooreInBabbage，十九世纪的英国数学家，发明了世界上第一台机械计算机器——差分机；约翰·冯·诺依曼（Johnvon ann）提出“程序”的计算机工作原理，该理论的要点是：数字计算机的数制采用二进制，计算机应该按照程序顺序执行。人们把冯·诺依曼的这个理论称为冯·诺依曼体系结构。因此答案选择D。2时弹出两操作数和操作符运算后再压栈。因此前缀表达式“+3*2+512”运算时是先依次存入+3*2+5125和“+1217，172又是连续2个操作数，取出“*3434+3=37C。来暂存指令、数据和位址。在处理器的控制部件中，包含的寄存器有指令寄存器(IR)和程序计数器(PC)。在处理器的算术及逻辑部件中，包含的寄存器有累加器(ACC)。高速缓存是为了大幅提升系统的执行效率，在CPU与主器之间，使用速度最快之SRAM来作为CPU的数据快取区，目的是为了让数据的速度适应CPU的处理速度，其基于的原理是内存中“程序执行与数据的局域性行为”，即一定程序执行时间和空间内，被的代码集中于一部分。器按照用途可分为主器和辅助器，主器又称内器（简称内存B。的编号为[i/2],ii/2,它是双亲结点的左孩子，i为奇数时，其双亲结点的编号为(i-1)/2C。考查对信息学竞赛的了解程度。1984年邓小平：“计算机的普及要从娃娃做起。”NOI二、选择在栈底。因此答案选ACD。自然语言通常是指一种自然地随文化演化的语言，如英语、汉语、法语等，与之相对应的是如编程语言等为计算机而设的“人造”语言。计算机语言具有高级语言和低级语言之分。低级语言分机器语言（计算机语言具有高级语言和低级语言之分。低级语言分机器语言（二进制语言）和汇编语言（符号语言，这两种语言都是面向机器的语言，和具体机器的指令系统密切相关，难学难记，于是人们又发明了更加易用的所谓高级语言。在这种语言下，其语法和结构更类似普通英文，且由于远离对硬件的直接操作，使得一般人经过学习之后都可以编程。如C/C++,Pascal等。编译性语言写的程序须编译成机器语言文件才可执行，比如exe文件，以后要运行的话就不用重新翻译了，直接使用编译的结果就行了（exe文件，因为翻译只做了一次，运行时不需要翻译，所以编译型语言的程序一般执行效率较高。解释型语言编写的程序不需要编译，只是在运行程序的时候才翻译，比如解释性basic语言，专门有一个解释器能够直接执行basic程序，每个语句都是执行的时候才翻译。这样解释性语言每执行一次就要翻译一次，效率比较低。但兼容性高。因此答案选AD。理解各种排序的基本原理即能选择正确的答案，其中基数排序又叫“桶排序点是数据规模越大，辅助空间就越大。答案为ABD。为“1”A正确。例如8位补码能够表示数的范围是-128~12710000000表示最小值-128, 最大值127，因此选项B不正确。+0的补码就是其原码，也就是说是00000000而已（8位来说，-0的补码是其反码加1，其反码是11111111，当然，其反码加1后就是溢出一个进位后，仍然是00000000，因此整数0只有唯一一个编码。因此选项C正确。位，是由计算机来判断的。计算机中常用的溢出判别称为双判别法。因此选项D不正二叉树的遍历，首先前序遍历顺序是根节点--左--右，而后序遍历顺序是左--右--根节点，A是根节点，又由后序遍历知D必然是右的根节点，D前面的ABC中A是根节点剩下的BC两个节点必然是左的，因此答案选B。HTML的格式是<ahref=””></a>BA到BBA立体几何知识，设向量（x,y,z）垂直于该平面，则向量（x,y,z）垂直于该平n0，则两向量垂直。根据题意，位于该平V3=（0，3，0）-（2，0，0）=（-2，3，0）根据向量的点积，列出方程组如下： --因此，所有为（32，1）倍数的向量均为该平面的垂直线。四个答案中：A（111）-（2，33）=（-1，-2，-2）B（11，1）-（32，1）=（-2，-1，0）C（03，0）-（-311）=（3，2，-1）D（200）-（5，21）=（-3，-2，-1）只有D符合条件，故选D。考查双向链表知识，双向链表参见下图：模拟程序运行即可，故答案为BCD p Windows7200910月由微软发布的。因此答案为ABC634>25>1612。参考图形如下：本题可用抽屉原理求解。设ai为各正整数值，则T的队列顺序为a1a2ani项数之和，则b0=0b1a1b2a1a2b3a1a2a3…。如队列T的数之和恰好为9，实际上即是找到某个bjbi，使得bjbi9。由题意可知bi取值范围为1-32，现将这32个数构造为集合{1,10},{2,11},,{8,17},{{19,28},…,{23,32},{24},{25},{26}，这17个集合中的任一个集合不能包含两个或两个以上的bi，否则它们的差为9。例如设n=17时，队列T为

b2=2,…b8

b9

b11=20b17=26,它们中没有任意两个数是在同一集合内的，所以不存在数之和恰好等于9故根据抽屉原理可得，当n=18时，至少存在两个bi在同一个集合，即它们的差为9。因此，答案为n=18。简单模拟题，程序从五个数中找到一个数，使得有m个数比该数字大。输出结果6。简单算法题，考的是归并排序，程序对两个有序数组的数进行归并操作并输出有序数列。输出结果为12356791014。考查递归，可寻找到规律，即下面的式子： 因此输出结果为4考查图论知识里的哈密尔顿图，即由指定的起点前往指定的终点，途中经过所有其他169548327。答案如下：①num2（num3或num②pos[iLEFT（LEFT④hour[igo(RIGHT_TO_LEFT)（go(RIGHT_TO_LEFThour[i]）Cpascaltime[i]+go(RIGHT_TO_LEFT)（或go(RIGHT_TO_LEFT)+⑤pos[i]=分析：本题描述的实际是一个网上流行的Flash趣味小游戏，游戏中是一家5口人过河，每个人单独过桥时间为1，3，6，8，12，我们最容易想到的方案是用最快的人（用1来指代该人）来充当工具，但实际上这并不是最优的，正确方案是：（1）131带灯回来，时间为3+1=4秒；（2）812过河（最优选择，3带灯回来，时间为12+3=15秒；（3）161带灯回来，时间为6+1=7秒；（4）13过河，时间为3秒；共计花费29秒。明白了思路，程序就好编写了。本程序采用的是递归方式穷举所有可能以获得最优解，关键函数go()代码注释如下：intgo(boolstage)//stage用于控制这一步是从左岸到右岸还是从右岸到左岸{inti,j,num,tmp,ans;//num为人数，ans为花费的总时间if(stage==right_to_left)//如果这一步是从右岸到左岸{{num++;//统计没过河的人数ans=hour[i];//获取最慢的人花费的时间给}if(num<=2)//如果右岸只剩两个人returnans