小学信息奥试卷2009年石狮市信息学奥林匹克竞赛普及组试卷1

2009年石狮市信息学奥林匹克竞赛普及组试卷（Pascal语言）作者：林中清涧来源：原创人气：675评论：0推荐等级：★★★★★录入人：陈凯兵录入时间：2009/6/27关键字：2009年石狮市信息学奥林匹克竞赛普及组试卷（Pascal语言）（考试时间：120分钟）学校：_________________班级：______________姓名：______________●●全部试题答案要求写在答卷纸上，写在试卷上一律无效。●●一.选择一个正确答案代码(A/B/C/D)，填入括号内（每题1.5分，共30分）1.在下面各世界顶级的奖项中，为计算机科学与技术领域做出杰出贡献的科学家设立的奖项是()。A.沃尔夫奖B.诺贝尔奖C.菲尔兹奖D.图灵奖2.以下哪个不是计算机的输入设备()。A.绘图仪B.光笔C.扫描仪D.传真机3.以下断电之后仍能保存数据的是()。A.硬盘B.寄存器C.显存D.内存4.以下哪个协议可以用于邮件发送()。A.FTPB.HTTPC.IMAPD.SMTP5.一位艺术家有20000幅真彩色图像，每幅图像约占3M空间。如果将这些图像以位图形式保存在DCD光盘上（一张DCD光盘的容量按6000M计算），大约需要（）张DCD光盘。A.1B.10C.100D.10006.(3721)8+(A)16的运算结果是（）。A.(3736)8B.(2018)10C.(7DB)16D.(1111110001)27.在深度为7的满二叉树中，叶子结点的个数（）。A.32B.31C.64D.638.已知7个结点的二叉树的前序遍历为DBACEGF(字母表示结点编号，以下同)，中序遍历是ABCDEFG，则该二叉树的后序遍历是（）。A.ACBFGEDB.ABCEFGDC.CAFGEBDD.CBFEGAD9.在计算机中，防火墙的作用是（）。A.防止火灾蔓延B.防止网络攻击C.防止计算机死机D.防止使用者误删除数据10.在编程时（使用任一种高级语言，不一定是Pascal），如果需要从磁盘文件中输入一个很大的二维数组（例如1000*1000的double型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（）。A.没有区别B.有一些区别，但机器处理速度很快，可忽略不计C.按行读的方式要高一些D.取决于数组的存储方式。11.在下列关于计算机算法的说法中，不正确的是（）。A.一个正确的算法至少要有一个输入B.算法的改进，在很大程度上推动了计算机科学与技术的进步C.判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性D.目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法12.设栈S的初始状态为空，元素a,b,c,d,e依次入栈，以下出栈序列不可能出现的有（）A.a,b,c,e,dB.b,c,a,e,dC.a,e,c,b,dD.d,c,e,b,a13.下列诸因素中，对微机工作影响最小的是()A.尘土B.噪声C.温度D.湿度14.目前，常用的文字处理软件WPS，应属于（）。A.应用软件B.系统软件C.工具软件D.管理软件15.个人计算机属于（）。A.巨型机B.中型机C.小型机D.微型机16.（）是存储在计算机内有结构的数据集合。A.数据库系统B.数据库C.数据结构D.数据库管理系统17.下列关于数据库系统的叙述中正确的是（）。A.数据库系统减少了数据冗余B.数据库系统避免了一切冗余C.数据库系统中数据的一致性是指数据类型的一致性D.数据库系统比文件系统能管理更多的数据18.栈和队列共同特点是（）。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点19.计算机网络最大的优点是（）。A.数据传送速度快B.传送的数据量大C.数据传送的可靠性高D.实现资源共享20.在微机系统中，用户可用的内存容量是指（）。A.ROM的容量B.RAM的容量C.硬盘的容量D.ROM和RAM的容量二．问题求解（每题5分，共10分）21.（寻找假币问题）现有80枚硬币，其中有一枚是假币，其重量稍轻，所有真币的重量都相同，如果使用不带砝码的天平称重，最少需要称几次，就可以找出假币？请指出第一次的分组称重方法。22.（最优排序问题）将数组{3,7,1,6,2,4,8,5}中的元素按从小到大的顺序排列，每次可以交换任意两个元素，求最少的交换次数。请写出具体的交换过程，并说明理由。三.阅读程序（4题，7’+7’+8’+8’，共30分）23.阅读以下程序，写出程序的运行结果。programprog1;vari,j,t:longint;m:array[0..3]oflongint=(3,5,7,9);beginfori:=0to3dobegint:=1;forj:=1tom[i]-1dot:=t*2;write((t-3)*t,'');end;end.输出：_____________________________24.阅读以下程序，写出程序的运行结果。programprog2;varn,i:integer;beginread(n);i:=2;while(i*i=n)dobeginwhile(nmodi=0)dobeginwrite(i,'*');n:=ndivi;end;inc(i);end;write(n);end.输入：9828输出：_______________________________25.阅读以下程序，写出程序的运行结果。programprog3;constNmax=100;vara:array[0..Nmax,0..Nmax]ofinteger;n,m:integer;i,j,ans,val:integer;procedureDFS(x,y:integer);beginif(x0)or(x=n)or(y0)or(y=m)thenexit;if(a[x][y]=0)thenexit;a[x][y]:=0;DFS(x,y-1);DFS(x,y+1);DFS(x-1,y);DFS(x+1,y);end;beginread(n,m);fori:=0ton-1doforj:=0tom-1doread(a[i][j]);ans:=0;fori:=0ton-1doforj:=0tom-1doif(0=a[i][j])thenbeginDFS(i,j);ans:=ans+1;end;writeln('ans=',ans);end.输入：56011001110101010010000111101110输出：_______________________________26.阅读以下程序，写出程序的运行结果。programprog4;vara,x:array[0..99]ofinteger;n,i,tmp,finish:integer;beginread(n);fori:=1tondoa[i]:=0;fori:=1tondoread(x[i]);finish:=0;while(finish=0)dobeginif(nmod2=1)thenbegina[n-1]:=x[n];i:=n-3;while(i=2)dobegina[i]:=x[i+1]-a[i+2];i:=i-2;end;a[1]:=x[1]-a[2];i:=3;while(i=n)dobegina[i]:=x[i-1]-a[i-2];i:=i+2;end;endelsebegina[n-1]:=x[n];i:=n-3;while(i=1)dobegina[i]:=x[i+1]-a[i+2];i:=i-2;end;a[2]:=x[1]-a[1];i:=4;while(i=n)dobegina[i]:=a[i-1]-a[i-2];i:=i+2;end;end;fori:=1tondobegintmp:=a[i];a[i]:=x[i];x[i]:=tmp;if(x[i]0)thenfinish:=1;end;end;fori:=1tondowrite(a[i],'');writeln();end.输入：5510190输出：_______________________________四.完善程序(每空3分，共30分)27.函数MaxMin求出数组a中的最大值和最小值，其中参数n为数组a中的元素个数。参数min带回最小值，通过函数MaxMin返回最大值max。请填空实现上述功能。programprog5;typearr=array[0..6]ofinteger;vara:arr=(4,6,12,2,9,5,10);min:integer;functionMaxMin(n:integer;varmin:integer):integer;varmax,i:integer;beginmax:=a[0];;fori:=1ton-1dobeginif(a[i]max)thenmax:=a[i]elseif()thenmin:=a[i];end;MaxMin:=max;end;beginwriteln('maxvalueis',MaxMin(7,min));writeln('minvalueis',min);end.28.求全排列中下一个排列的算法：设当前排列为P1P2,…,Pn，则下一个排列可按如下算法完成：(1)．求满足关系式Pi-1Pi的i的最大值，设为mi，即mi=max{i|Pi-1Pi,i=2..n}(2)．求满足关系式Pmi-1Pj的j的最大值，设为mj，即mj=max{j|Pmi-1Pj,j=mi..n}(3)．Pmi-1与Pmj互换得(P)=P1P2,…,Pn(4)．{P}=P1P2,…,Pmi-1Pmi,…,Pn部分的顺序逆转，得P1P2,…,Pmi-1PnPn-1,…,Pmi便是下一个排列。(5).当mi=1的时候，需要特殊处理。例：设P1P2P3P4=3421(1)．mi=max{i|Pi-1Pi,i=2..n}=2(2)．mj=max{j|Pmi-1Pj,j=1..n}=2(3)．P1与P2交换得到4321(4)．4321的321部分逆转得到4123即是3421的下一个排列。请填空实现上述功能。programprog6;typearr=array[0..19]ofinteger;varP:arr;i,n:integer;procedureNEXT_permutation(varP:arr;n:integer);vari,j,mi,mj,t,tmp:integer;beginmi:=1;fori:=ndownto2dobeginif(P[i-1]P[i])thenbegin;break;end;end;if(mi1)thenbeginmj:=mi;forj:=ndowntomidobeginif()thenbeginmj:=j;break;end;end;tmp:=P[mi-1];P[mi-1]:=P[mj];P[mj]:=tmp;end;fort:=mitodobegin;P[t]:=P[n-t+mi];P[n-t+mi]:=tmp;end;end;beginread(n);fori:=1tondoread(P[i]);NEXT_permutation(P,n);fori:=1tondowrite(P[i],'');writeln();end.29.多项式相加问题以下程序是实现用两个多项式的加法运算。多项式的每一个项由一个记录来实现，其包含两个变量：系数cc和幂次pp。例如：下面的两个多项式A(x)=2x1000+3x3+1B(x)=x4+10x3+3x2+1计算结果C(x)=A(x)+B(x)=2x1000+x4+13x3+3x2+2其中A(x),B(x),C(x)分别用三个不同的一维数组实现。程序中多项式的输入输出形式：项数，按降幂的顺序（项，系数）。以上样例表示为：输入：32100033104141033210输出：521000141333220programprog7;con