信息学奥赛试题及答案

信息学奥赛试题一、填空题(共20题，每题1.5分，共计30分。每题有5个备选答案，前10个题为单选题(即每题有且只有一个正确答案，选对得分)，后10题为不定项选择题(即每题有1至5个正确答案，只有全部选对才得分)。.微型计算机的性能主要取决于()。A)内存B)主板C)中央处理器D)硬盘E)显示器.能将高级语言程序转换为目标程序的是().A调试程序B)解释程序C)编辑程序D)编译程序E)连接程序,A=11001010B,B=00001111B,C=01011100则AVBAC=()A01011110B)00001111C)01011100D)11001110E)11001010.计算机设备，既是输入设备，又是输出设备的是()oA)键盘B)触摸屏C)扫描仪D)投影仪E)数字化仪.计算机病毒传染的必要条件是()。A)在内存中运行病毒程序B)对磁盘进行读写操作C)在内存中运行含有病毒的可执行程序D)复制文件E)删除文件.已知队列(13,2,11,34,41,77,5,7,18,26,15),第一个进入队列的元素是13,则第五个出队列的元素是()。A)5B)41C)77D)13E)18.在使用E-mail前，需要对Outlook进行设置，其中ISP发送电子邮件的服务器称为()服务器。A)POP3B)SMTPC)DNSD)FTPE)HTTP.对给定的整数序列(54,73,21,35,67,78,63,24,89)进行从小到大的排序时，采用快速排序的第一趟扫描的结果是().A)(24,21,35,54,67,78,63,73,89)B)(24,35,21,54,67,78,63,73,89)C)(24,21,35,54,67,63,73,78,89)D)(21,24,35,54,63,67,73,78,89)E)(24,21,35,54,67,63,73,78,89).编号为1到13的纸牌顺时针排成一圈，有人从编号为1的牌从数字1开始顺时针数下去，1,2,3,……,一圈又一圈，问当数到数字n,所在的纸牌编号为多少？A)nmod13B)1+(n-1)mod13C)(n+1)mod13-1D)(n+1)mod13E)(n-1)mod13.对下图进行广度优先拓朴排序得到的顶点序列正确的是().A)1,2,3,4,5,6B)1,3,2,4,5,6C)1,3,2,4,6,5D)1,2,3,4,6,5,E)1,3,2,4,5,6.下列属于冯.诺依曼计算机模型的核心思想是().A)采用二进制表示数据和指令；B)采用“存储程序”工作方式C)计算机硬件有五大部件(运算器、控制器、存储器、输入和输出设备)D)结构化程序设计方法E)计算机软件只有系统软件.CPU®问内存的速度比访问下列哪个(些)存储设备要慢()。A)寄存器B)硬盘C)软盘D)高速缓存E)光盘.下列电子邮件地址，哪个(些)是正确的()。A)wang@B)cai@.jpC)2D)E).数字图像文件可以用下列哪个(些)软件来编辑()。A)画笔(Paintbrush)B)记事簿(Notepad)C)PhotoshopD)WmRARE)MidiSoft.下列哪个(些)软件不是操作系统软件的名字()。A)WindowsXPB)DOSC)LinuxD)OS/2E)Arch/Info.下面关于算法的正确的说法是()A)算法必须有输出B)算法必须在计算机上用某种语言实现C)算法不一定有输入D)算法必须在有限步执行后能结束E)算法的每一步骤必须有确切的定义.下列逻辑运算正确的是()。A)A•(A+B)=AB)A+(A・B)=AC)A-(B+C)=A•B+A•CD)A+(B-Q=(A+B)-(A+C)E)A+1=A.下列关于排序说法正确的是().A)插入排序、冒泡排序是稳定的B)选择排序的时间复杂性为O(n2)C)选择排序、希尔排序、快速排序、堆排序是不稳定的D)希尔排序、快速排序、堆排序的时间复杂性为O(nlog2n)E)快速排序是速度最快的排序.对于一个大小为3的栈，若输入队列为123456,则下列输出队列有可能的是()。A)123456B)654321C)432165D)431256E)321654.设有一个含有13个元素的Hash表(0~12),Hash函数是:H(key尸key%13,其中％是求余数运算。用二次探查法解决冲突，则对于序列(8、31、20、33、18、53、27),则下列说法正确的是()。A)27在1号格子中B)33在6号格子中C)31在5号格子中D)20在7号格子中E)18在4号格子中二.问题求解(5分*2=10分).某年级学生共选修6门课程，期末考试前，必须提前将这6门课程考完，每人每天只在下午至多考一门课程，设6门课程分别为c1,c2,c3,c4,c5,c6,S(ci)为学习ci的学生集合。已知S(ci)nS(c6)w?,i=l,2,...,5,S(ci)AS(ci+1)丰?i=1,2,3,4,S(c5)AS(c1)w?,问至少安排天才能考完这6门课程。.设有一棵k*树，其中只有度为0和k两种结点，设n0,nk分别表示度为0和度为k的结点个数，试求出n0和nk之间的关系(n0=数学表达式，数学表达式仅含nk、k和数字)。三.阅读程序写出正确的程序运行结果(4*8分=32分)programt1；varn,k,s：longint；beginreadln(n);k:=0；s:=1;whiles<=ndobegink:=k+1;n:=n-s;s:=s+6*kend;writeln(k)end.输入:1000000输出：programt2;varx,y1,y2,y3:integer;beginreadln(x);y1:=0;y2:=1;y3:=1;whiley2<=xdobeginy1:=y1+1;y3:=y3+2;y2:=y2+y3;end;writeln(y1);end.输人：x=400输出：programt3；varm,n,i,j:integer;p,w,a,b:array[0..19]ofinteger;beginread(n)；m：=0；fori:=0ton-1dobeginread(p[i])；b[i]:=1；end；fori：=0ton-1dobeginif(i>0)thena[m]：=p[i]-p[i-1]elsea[m]：=p[i];m：=m+1：while((m>1)and(a[rn-1]=0))dobeginm；=m-1；b[m]：=l；end;if(m>0)thenw[i]=b[m-1]elsew[i]:=b[0];a[m-1]:=a[m-1]-1；forj：=0tom-1dob[j];=b[j]+1;while((m>1)and(a[m-1]=0))dobeginm:=m-1；b[m]:=1；end;end;fori=0ton-1dobeginwrite(w[i]);write('');end;writeln('')；end.输入：44666输出：programt4；constTOC\o"1-5"\h\zarray[1..4]ofinteger=(0,5,3,1);array[1..4]0finteger=(0,7,6,5);vara,b,c,d,e,f,x,y,z：integer；beginread(a,b,c,d,e,f)；z：=f+e+d+(c+3)div4；y：=5*d+u[cmod4]if(b>y)thenbeginz：=z+(b-y+8)div9;x:=((b-y+8)div9*9-(b-y))*4+11*e+V[cmod4]endelsex:=(y-b)*4+11*e+v[cmod4]；if(a>x)thenz:=z+(a-x+35)div36writeln(z)；end.输入：479205647输出：四.完善程序题（2分+3*4分+2分+4*3分=28分）.问题描述：工厂在每天的生产中，需要一定数量的零件，同时也可以知道每天生产一个零件的生产单价。在N天的生产中，当天生产的零件可以满足当天的需要，若当天用不完，可以放到下一天去使用，但要收取每个零件的保管费，不同的大收取的费用也不相同。问题求解：求得一个N天的生产计划（即N天中每天应生产零件个数），使总的费用最少。输入：N（天数N<=29）每天的需求量（N个整数）每天生产零件的单价（N个整数）每天保管零件的单价（N个整数）输出：每天的生产零件个数（N个整数）例如：当N=3时，其需要与费用如下：11111第f।।1第二天1I1第三天1111髻萝得11rru交里1II251111530111生产单价1II20|113032111保管单价11151।1110।।0生产计划的安排可以有许多方案，如下面的三种:।।1第f1I1第二天1第三天11总的费用112511530125*20+15*30+30*32=19101114010301|40*20+15*5+30*32=1835|111|70।।10।01|70*20+45*5+30*10=1925程序说明：bln]：存放每天的需求量cln]:每天生产零件的单价d[n]：每天保管零件的单价e[n]：生产计划程序：programexp5;vari,j,n,yu,jO,j1,s:integer;b,c,d,e:array[O..30]ofinteger;beginreadln(n);fori:=1tondoreadln(b[i],c[i],d[i]);fori:=1tondoe[i]:=0;(1):=10000;c[n+2]:=0;b[n+1]:=0;j=1;while(jO<=n)dobeginyu:=c[jO];j1:=jO;s:=b[jO];while(2)dobegin(3)j1:=j1+1;s:=s+b[j1];end;⑷j0:=j1+1:end;fori:=1tondowrite(e[I]:4);readln;end.2.问题描述]将一个含有运算符为：(、)、+、-、*、/、八(乘幕运算)、~(求负运算)的中缀表达式,如：((1+2)*5)A2-(3+5)/2转化为后缀表达式，如：12+5*2A35+2/-.[解题思路]将中缀表达式转化为后缀表达式，首先规定运算符的优先数如下:111运算符11〜11(111〜1)1111+，一1111*111111优先数10111111121111131141,।।।/5.若输入是运算量，则将该运算量输出；.若是左括号“(”，则将该符号的优先数压入设置的运算符堆栈e[p]中去；.输入运算符优先数是2,3,4,5时，如果栈空，则将运算符的优先数进栈。如果栈不空,则将它与栈顶元素进行比较，倘若优先数大于栈顶元素的优先数，则进栈；小于顶元的，则顶元退栈并输出该运算符，然后再继续比较，直到大于顶元或栈空时进栈；.若是右括号“)”，同时栈顶元又为左括号“(”，则栈顶元退栈，并抹去右括号“)”否则转3处理；.输入完而栈非空，则将栈内内容逐一退栈并输出。所有输出的结果就为后缀表达式。过程中用到的相关数据结构如下：typearraydata=array[1..100]ofstring[20];constfh:array[1..8]ofstring[1]XT,')',』','-','*','/','〜','A');b:array[1..8]ofbyte=(0,1,2,2,3,3,4,5);vard:arraydata;{存储运算量及运算符号}i,j,m,k:byte;[过程程序]procedurehzbds(vard:arraydata;varm:byte);var:array[1..100]ofbyte;i,p,k,bi:byte;bl:boolean;beginp:=O;k:=1;bj:=0;whilek<=mdobeginifd[k]='('thenbeginp:=p+1;e[p]:=1endelsebeginfori:=2to8doif(1)thenbeginb1:=true;repeatif—(2)―thenbeginp:=p+1;e[p]:=i;bj:=1;b1:=falseendelseif(3)thenife[p]<>1thenbeginp:=p+1;e[p]:=i;bj:=1;b1:=falseendelseifd[k]<>')'thenbeginp:=p+1;e[p]:=i;bj:=1;b1:=falseendelsebegin⑷;bj:=1;b1:=false;endelsebeginwrite(fh[e[p]],'');p:=p-1end;untilb1=false;endif(5)thenwrite(d[k],'')elsebj:=0;end;k:=k+1endb1:=true;repeatifp=0thenb1:=falseelsebeginwrite(