搜索
第页共12页1第20届中小学生计算机程序设计竞赛初赛试题学校姓名准考证号（说明：答案请写在答题卷上。考试时间120分钟，满分120分）一、选择题(每小题2分，共40分)下列各题A、B、C、D四个选项中，只有一个选项是正确的，请将正确选项写在答题卷相应位置上，答在试卷上不得分。1、构成运算器需要多个部件，（）不是构成运算器的部件。A、加法器B、累加器C、地址寄存器D、ALU(算术逻辑部件)2、在主存和CPU之间增加Cache的自的是（）。A、增加内存容量B、为程序员编程提供方便C、解决CPU与内存间的速度匹配问题D、提高内存工作的可靠性3、操作系统功能不包括（）。A、提供用户操作界面B、管理系统资源C、提供应用程序接口D、提供HTML4、系统软件是（）的软件。A、向应用软件提供系统调用等服务B、与具体硬件逻辑功能无关C、在应用软件基础上开发D、并不具体提供人机界面5、关于计算机的使用和维护，下列叙述中错误的是（）。A、计算机要经常使用，不要长期闲置不用B、在计算机附近应避免磁场干扰C、为了延长计算机的寿命，应避免频繁开关计算机D、为了省电，每次最好只打开一个程序窗口6、Windows“回收站”占用的是（）中的空间。A、主存B、软盘C、光盘D、硬盘7、ASCII码是对（）实现编码的一种方法。A、语音B、汉字C、图形图像D、字符8、程序设计语言的定义一般应包（）几个方面。第页共12页2A、语法、语义和语句B、语法、语义和语用C、语义、语句和语用D、语法、语用和语句9、与十进制数254等值的二进制数是（）。A、11111110B、11101111C、11111011D、1110111010、对于二维数组a[1..4，3..6]，设每个元素占两个存储单元，若以行为主序存储，则元素a[3，4]相对于数组空间起始地址的偏移量是（）。A、12B、14C、16D、1811、在第一趟排序之后，一定能把数据表中最大或最小元素放在其最终位置上的排序算法是（）。A、冒泡排序B、基数排序C、快速排序D、归并排序12、在一颗非空二叉树中，叶子节点的总数比度为2的节点总数多（）个。A、-1B、0C、1D、213、一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（）。A、23415B、54132C、23145D、1543214、TCP/IP网络的体系结构分为应用层、传输层、网络互联层和网络接口层。属于传输层协议的是（）。A、TCP和ICMPB、IP和FTPC、TCP和UDPD、ICMP和UDP15、使用IE浏览器浏览网页时，出于安全方面的考虑，需要禁止执行JavaScript，可以在IE中（）。A、禁用ActiveX控件B、禁用cookieC、禁用没有标记为安全的ActiveX控件D、禁用脚本16、某数码相机的分辨率设定为1600×1200象素，颜色深度为256色，若不采用压缩存储技术，则32M字节的存储卡最多可以存储（）张照片。A、8B、17C、34D、6917、在以下关于电子邮件的叙述中，“（）”是不正确的。A、打开来历不明的电子邮件附件可能会传染计算机病毒B、在网络拥塞的情况下，发送电子邮件后，接收者可能过几个小时后才能收到C、在试发电子邮件时，可向自己的Email邮箱发一封电子邮件D、电子邮箱的容量指的是用户当前使用的计算机上，分别给电子邮箱的硬盘容量18、关于发送和接收电子邮件，下列叙述中正确的是（）。A、发送方和接收方必须同时开机才能传送电子邮件B、接收方不能与发送方相同第页共12页3C、同一E-Mail帐户不能同时设置在多台计算机上D、同一台计算机上可以设置多个E-Mail帐户19、目前多媒体计算机中对动态图象数据压缩常采用（）。A、JPEGB、GIFC、MPEGD、BMP20、为了在Internet上浏览网页，需要在客户端安装浏览器，不属于浏览器软件的时（）。A、InternetExplorerB、FireworksC、HotJavaD、NetscapeCommunicator二、问题解答(每小题10分，共20分)1．在书架上放有编号为1，2，．．．，n的n本书。现将n本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来的位置上。例如：n=3时：原来位置为：123放回去时只能为：312或231这两种问题：求当n=5时满足以上条件的放法共有多少种？（不用列出每种放法）2．如果一棵m度树中有n1个度为1的结点，n2个度为2的结点，……有nm个度为m的结点，求该树中叶结点的的个数。三、阅读程序(每小题10分，共30分)请阅读下列各题程序，并将程序的正确运行结果写在答题卷相应位置上，答在试卷上不得分。1、PROGRAMcx1;VARa:ARRAY[1..100]OFINTEGER;p,n,m,i:INTEGER;BEGINREADLN(n,m);FORi:=1TO100DOa[i]:=0;p:=1;REPEATa[p]:=a[p]+1;IFa[p]nTHENBEGINa[p]:=0;p:=p-1;第页共12页4ENDELSEBEGINp:=p+1;a[p]:=a[p-1];END;IFpmTHENBEGINFORi:=1TOmDOWRITE(a[i]);WRITELN;p:=p-1;END;UNTILp1;END..输入：42程序运行的结果是：2、PROGRAMcx2;VARn,i,j:LONGINT;s:ARRAY[1..100]OFINTEGER;BEGINREADLN(n);i:=0;REPEATINC(i);IFODD(n)THENs[i]:=1ELSEs[i]:=0;n:=nSHR1;UNTILn=0;FORj:=iDOWNTO1DOWRITE(s[j]);WRITELN;END.输入：2004程序运行的结果是：3、PROGRAMcx3;VARpath:ARRAY[1..1000]OFINTEGER;total,n:INTEGER;PROCEDUREfind(k,sum,dep:INTEGER);VARb,d:INTEGER;第页共12页5BEGINIFsum=nTHENBEGINWRITE(n,'=',path[1]);FORd:=2TOdep-1DOWRITE('*',path[d]);WRITELN;INC(total);EXIT;END;IFsumnTHENEXIT;FORb:=TRUNC(n/sum)+1DOWNTOkDOBEGINpath[dep]:=b;find(b,sum*b,dep+1);END;END;BEGINREADLN(n);total:=0;find(2,1,1);WRITELN('total:',total);READLN;END.输入：8程序运行的结果是：四、程序填空(每空3分，共30分)请阅读下列各题的题意及程序，并将程序的空缺部分填空完善，填空的内容写在答题卷相应位置上，答在试卷上不得分。1、问题描述：本程序是一个用栈实现“老鼠走迷宫问题”的子程序。其中迷宫由二维数组maze[1..m,1:p]of0..1表示，若数组元素的值为1，表示对应的位置不通行；若为0，表示可通行。迷宫的入口为maze[1,1],出口为maze[m,p]。为了便于处理迷宫周围的边界，把数组扩充为maze[0..m+1,0..p+1]，使得周围附加一圈的数组元素值均取为1，以表示老鼠不得走离边界。同时，用二维数组mark[0..m+1,0..p+1]of0..1记录在迷宫内所走过的位置，以避免重复。老鼠在位置[I,j]上，可能向周围八个方向的位置走动（只要周围的位置为0值），参看下图。⑧[i-1,j-1]⑦[i,j-1]①[i-1,j][i,j][i-1,j+1②[i,j+1]③第页共12页6在程序中这八种可能的走动，可用下表表示。qmove[q].amove[q].b1-102-1130141151061-170-18-1-1程序：PROGRAMmg;CONSTm=10;p=10;n=100;TYPEoffsets=RECORDa,b:-1..1END;iterms=RECORDx:1..m;y:1..p;dir:1..9END;VARmaze,mark:array[0..11,0..11]of0..1;move:ARRAY[1..8]OFoffsets;stack:ARRAY[1..n]OFitems;top:-1..n;i,j:INTEGER;PROCEDUREpath;LABEL99;VARposition:items;d,g,h,I,j,q:INTEGER;BEGINmark[1,1]:=1;top:=1;第页共12页7stack[1].x:=1;Stack[1].y:=1;stack[1].dir:=1;WHILEtop0DOBEGINposition:=①；top:=top-1;iI:=position.x;j:=position.y;d:=position.dir;WHILEd=8DOBEGINg:=I+move[d].a;h:=j+move[d].b;IF②THENBEGINFORq:=1TOtopDOwriteln(stack[q].x,(stack[q].y);WRITELN(I,j);WRITELN(m,p);GOTO99END;IF③THENBEGINmark[g,h]:=1;position.x:=I;position.y:=j;④;IFtop=nTHENBEGINWRITELN(“stackfull”);GOTO99ENDELSEBEGINtop:=top+1;stack[top]:=positionEND;i:=g;j:=h;d:=1ENDELSE⑤ENDEND;WRITELN(“nopathinmaze”);99:END;BEGINFORi:=0TOm+1DOFORj:=0TOp+1DOIF(i=0)OR(i=m+1)OR(j=0)OR(j=p+1)THEN第页共12页8maze[i,j]:=1ELSEREAD(maze[i,j]);FORi:=1TO8DOREADLN(move[i].a,move[i].b);pathEND.2．问题描述：本程序输入一个无回路有向图的所有有向边，对图中的结点进行拓扑排序输出。有向图中的n个结点v1，v2，…，vn分别以整数1，2，…，编号，用整数对（I，j）表示结点vi到结点vj的有向边。譬如，某计算机系开设如下九门课程：V1程序设计V2高等数学V3数据结构V4汇编语言V5线性代数V6人工智能V7图形学V8数值分析V9算法分析选修每门课程所需前导课程可用如下一个无回路有向图表示。求出图上结点的拓扑排序序列，便可以确定学生选修各门课程的先后顺序。本程序采用的拓扑排序的基本要点是：（1）为每个结点设置一个计数器，初值分别为指向该结点的有向边条数。（2）将所有计数器值为0的结点勾链在一起。（3）在输出计数器值为0的结点序号后，就修改由该结点出发的所有有向边所指的结点的相应计数器。程序：PROGRAMlist(input,output);CONSTnmax=100;TYPEnextnode=^node;node=RECORDVertex:integer;V2V1V3V5V8V4V9V6V7第页共12页9Link:nextnode;END;headnodes=RECORDcount:integer;link:nextnodeEND;adjacencylists=ARRAY[1..nmax]OFheadnodes;VARa:adjacencylists;w:nextnode;p,q,n,I:integer;PROCEDUREtopologicalorder(VARadlist:adjacencylists;n:INTEGER);VARi,j,k,top:integer;ptr:nextnode;done:BOOLEAN;BEGINtop:=0;FORi:=1TOnDOIFadlist[i].count=0THENBEGIN