信息学奥赛试题及答案.doc

信息学奥赛试题一、填空题（共20题，每题1.5分，共计30分。每题有5个备选答案，前10个题为单选题（即每题有且只有一个正确答案，选对得分），后10题为不定项选择题（即每题有1至5个正确答案，只有全部选对才得分）。1.微型计算机的性能主要取决于（ ）。A） 内存 B） 主板 C） 中央处理器 D） 硬盘 E） 显示器2.能将高级语言程序转换为目标程序的是( ).A）调试程序 B）解释程序C）编辑程序 D）编译程序E）连接程序3A=11001010B,B=00001111B,C=01011100B,则ABC=( )A）01011110 B） 00001111 C）01011100 D） 11001110 E) 110010104.计算机设备，既是输入设备，又是输出设备的是( )。 A)键盘 B)触摸屏 C)扫描仪 D)投影仪 E)数字化仪 5.计算机病毒传染的必要条件是( ) 。A) 在内存中运行病毒程序 B) 对磁盘进行读写操作C) 在内存中运行含有病毒的可执行程序 D) 复制文件 E)删除文件6已知队列(13，2，11，34，4l，77，5，7，18，26，15)，第一个进入队列的元素是13，则第五个出队列的元素是( )。 A)5 B)41 C)77 D)13 E)18 7.在使用E-mail前，需要对Outlook进行设置，其中ISP发送电子邮件的服务器称为( )服务器。A)POP3 B)SMTP C)DNS D)FTP E)HTTP8.对给定的整数序列(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)9. 编号为1到13的纸牌顺时针排成一圈，有人从编号为1的牌从数字1开始顺时针数下去，1，2，3，,一圈又一圈,问当数到数字n ,所在的纸牌编号为多少?A) n mod 13 B)1+(n-1) mod 13 C)(n+1) mod 13-1 D)(n+1) mod 13 E) (n-1) mod 13 10.对下图进行广度优先拓朴排序得到的顶点序列正确的是( ).A) 1,2,3,4,5,6 B) 1,3,2,4,5,6 C) 1,3,2,4,6,5D) 1,2,3,4,6,5, E) 1,3,2,4,5,611.下列属于冯.诺依曼计算机模型的核心思想是( ).A) 采用二进制表示数据和指令; B) 采用”存储程序”工作方式C) 计算机硬件有五大部件(运算器、控制器、存储器、输入和输出设备)D) 结构化程序设计方法 E) 计算机软件只有系统软件12CPU访问内存的速度比访问下列哪个(些)存储设备要慢( )。 A)寄存器 B)硬盘 C)软盘 D)高速缓存 E)光盘 13下列电子邮件地址，哪个(些)是正确的( )。A) B).jpC)162.105.111. 22 D) E) 14数字图像文件可以用下列哪个(些)软件来编辑( )。 A)画笔(Paintbrush) B)记事簿(Notepad) C)Photoshop D)WmRAR E)MidiSoft 15下列哪个(些)软件不是操作系统软件的名字( )。 A)Windows XP B)DOS C)Linux D)OS2 E)ArchInfo 16.下面关于算法的正确的说法是( )A)算法必须有输出 B)算法必须在计算机上用某种语言实现C)算法不一定有输入 D)算法必须在有限步执行后能结束 E)算法的每一步骤必须有确切的定义17下列逻辑运算正确的是（ ）。A) A（A + B ）= A B) A +（AB）= AC) A（B + C ）= AB + AC D)A +（BC）=（A + B）（A + C） E) A+1=A18.下列关于排序说法正确的是( ).A) 插入排序、冒泡排序是稳定的 B) 选择排序的时间复杂性为O(n2)C) 选择排序、希尔排序、快速排序、堆排序是不稳定的D) 希尔排序、快速排序、堆排序的时间复杂性为O(nlog2n)E) 快速排序是速度最快的排序19.对于一个大小为3的栈，若输入队列为123456，则下列输出队列有可能的是（ ）。A) 123456 B)654321 C)432165 D)431256 E)32165420. 设有一个含有13个元素的Hash表(012),Hash函数是:H(key)=key % 13,其中% 是求余数运算。用二次探查法解决冲突,则对于序列(、31、20、33、18、53、27),则下列说法正确的是( ) 。A)27在1号格子中 B) 33在6号格子中 C) 31在5号格子中 D) 20在7号格子中E) 18在4号格子中二.问题求解（5分*2=10分）1.某年级学生共选修6门课程，期末考试前，必须提前将这6门课程考完，每人每天只在下午至多考一门课程，设6门课程分别为c1，c2，c3，c4，c5，c6，S(ci)为学习ci的学生集合。已知S(ci)S(c6)，i=l，2，5，S(ci)S(ci+1)，i=1，2，3，4，S(c5)S(c1) ，问至少安排天才能考完这6门课程。2设有一棵k*树，其中只有度为0和k两种结点，设n0，nk分别表示度为0和度为k的结点个数，试求出n0和nk之间的关系(n0=数学表达式，数学表达式仅含nk、k和数字)。三.阅读程序写出正确的程序运行结果(4 *8分=32分)1 program t1；varn，k，s：longint；begin readln(n);k:=0；s:=1；while s = n dobegink:=k+1;n:=n-s;s:=s+6*kend;writeln (k)end.输入:1000000 输出:2. program t2;var x,y1,y2,y3:integer; beginreadln(x);y1:=0;y2:=1;y3:=1;while y20) then am：= pi-pi-1 else am：= pi； m：= m+1： while (m1) and (arn-1=0) do begin m ；= m-1； bm ：= l； end； if (m0) then wi：=bm-1 else wi：=b0； am-1 ：= am-1-1； for j ：= 0 to m-1 do bj ；= bj+1； while (m1) and (am-1=0) do begin m ：= m-1； bm ：=1； end;end;for i ：= 0 to n-1 do begin write(wi)； write( ); end；writeln( )；end 输入：44 6 6 6输出：4. program t4； const u：array14 of integer = (0，5，3，1)； v：array14 0f integer = (0，7，6，5)； var a，b，c，d，e，f，x，y，z： integer； begin read (a，b，c，d，e，f)； z ：= f + e + d + (c+3) div 4； y ：= 5 * d + u c mod 4 ； if (by) thenbeginz ：= z+ (b-y+8) div 9；x ：= (b-y+8) div 9 * 9- (b-y) * 4+11*e+Vc mod 4；endelsex ：= (y-b) *4+11*e+vc mod 4；if (ax) thenz ：= z + (a-x+35) div 36； writeln(z)； end输入: 4 7 9 20 56 47输出: 四.完善程序题(2分+3*4分+2分+4*3分=28分)1问题描述：工厂在每天的生产中，需要一定数量的零件，同时也可以知道每天生产一个零件的生产单价。在N天的生产中，当天生产的零件可以满足当天的需要，若当天用不完，可以放到下一天去使用，但要收取每个零件的保管费，不同的天收取的费用也不相同。问题求解：求得一个N天的生产计划(即N天中每天应生产零件个数)，使总的费用最少。输入：N(天数N=29) 每天的需求量(N个整数)每天生产零件的单价(N个整数)每天保管零件的单价(N个整数)输出：每天的生产零件个数(N个整数)例如：当N=3时，其需要与费用如下： 第一天 第二天 第三天 需要量 25 15 30 生产单价 20 30 32 保管单价5 10 0 生产计划的安排可以有许多方案，如下面的三种： 第一天 第二天 第三天 总的费用 25 15 30 25*20+15*30+30*32=1910 40 0 30 40*20+15*5+30*32=1835 70 0 0 70*20+45*5+30*10=1925 程序说明：bln：存放每天的需求量cln：每天生产零件的单价dn：每天保管零件的单价en：生产计划程序：program exp5;vari,j,n,yu,jO,j1,s:integer;b, c, d, e: arrayO.30 of integer;beginreadln(n);for i:=1 to n do readln(bi ,ci ,di);for i:=1 to n do ei:=0;_(1)_:=10000;cn+2:=0;bn+1:=0;j=1;while (jO=n) do begin yu:=cjO;j1:=jO;s:=bjO; while _(2)_dobegin _(3)_j1:=j1+1;s:=s+bj1;end; _(4)_j0:=j1+1:end;for i:=1 to n do write(eI:4);readln;end.2. 问题描述将一个含有运算符为：(、)、+、-、*、/、(乘幂运算)、(求负运算)的中缀表达式，如：(1+2)*5)2-(3+5)/2转化为后缀表达式，如：12+5*235+2/-解题思路将中缀表达式转化为后缀表达式，首先规定运算符的优先数如下：运算符( ) +， *，/ 优先数0 1 2 3 4 51若输入是运算量，则将该运算量输出；2若是左括号“(”，则将该符号的优先数压入设置的运算符堆栈ep中去；3输入运算符优先数是2，3，4，5时，如果栈空，则将运算符的优先数进栈。如果栈不空，则将它与栈顶元素进行比较，倘若优先数大于栈顶元素的优先数，则进栈；小于顶元的，则顶元退栈并输出该运算符，然后再继续比较，直到大于顶元或栈空时进栈；4若是右括号“)”，同时栈顶元又为左括号“(”，则栈顶元退栈，并抹去右括号“)”否则转3处理；5输入完而栈非空，则将栈内内容逐一退栈并输出。所有输出的结果就为后缀表达式。过程中用到的相关数据结构如下：type arraydata = array1.100 of string20;const fh:array1.8 of string1=(,),+,-,*,/,);b:array1.8 of byte =(0,1,2,2,3,3,4,5);var d: arraydata; 存储运算量及运算符号i,j,m,k: byte;过程程序procedure hzbds(var d: arraydata; var m: byte );var: array 1. 100 of byte; i,p,k ,bi:byte; bl: boolean;beginp:=O;k:=1;bj:=0;while k=m dobeginifdk=( thenbeginp:=p+1;ep:=1endelse begin for i:=2 to 8 do if _(1)_ then begin b1:= true; repeat if _(2)_ then begin p:= p+1 ;ep:=i;bj:= 1 ;b1:= false end else if _(3)_ then if ep 1 then begin p:=p+1;ep:=i;bj:=1;b1:=false end else if dk ) then begin p:=p+1;ep:=i;bj:=1;b1:=false end else begin_(4)_;bj:= 1 ;b1:= false;end else beginwrite(fhep , ) ;p:=p-1end; until b1 = false; end if _(5)_ then write(dk , ) else bj:=0; end; k:=k+1endb1:= true;repeatif p=0 then b1:= falseelse b