2015年宁波市第30届中小学生计算机程序设计竞赛-初中

2015年宁波市第30届中小学生计算机程序设计竞赛初中组初赛试题第1页共8页2015年宁波市第30届中小学生计算机程序设计竞赛初中组初赛试题（说明：答案请写在答题卷上。考试时间120分钟，满分100分）一、选择题（每题有且仅有一个正确答案，选对得1.5分，选错.不选或多选均不得分）1、关于硬盘下面的说法哪个是不正确的：A)最新的商用固态硬盘（SSD），读写速度很快，均可超过500MB/s。B)传统的机械硬盘（HDD），价格便宜，存储容量大，但是读写速度较慢。C)混合硬盘（HHD）是机械硬盘和固态硬盘结合。D)硬盘的读写速度会越来越快，甚至超过CPU运算的速度，不再需要内存、缓存等。2、关于计算机内存下面的说法哪个是正确的：A)计算机内存严格说来包括主存（memory）、高速缓存（cache）和寄存器（register）三个部分。B)1MB内存通常是指1024*1024*1024字节大小的内存。C)随机存储器（RAM）的意思是它可以随时读写，而且速度很快，通常作为操作系统或其他正在运行中的程序的临时数据存储媒介。D)一般内存中的数据即使在断电的情况下也能保留数小时以上。3、关于微型计算机主板下面说法哪个是正确的：A)现在微机主板的集成度非常高，中央处理器、显卡、声卡等都可以集成在主板上。B)BIOS芯片，用于控制基本输入输出，就被集成在主板上。C)若要提高显示效果，安装的独立显卡，其数据处理和传输必须和主板相互独立。D)一般主板上有多个内存插槽，可以插入多条内存，但是只能接一块硬盘。4、关于CPU下面哪个说法是不正确的：A)CPU全称为中央处理器（或中央处理单元）。B)CPU可以直接运行Pascal语言。C)CPU的工艺水平越来越高，可以将集成电路中电子元器件体积做得更小，单位面积内容纳更多的电子元器件。D)CPU工艺改进中著名的摩尔定律，最早是由Intel公司创始人之一戈登·摩尔提出的。5、关于ASCII码和汉字编码，下面哪个说法是正确的：A)ASCII码就是键盘上所有键的唯一编码。B)一个ASCII码使用一个字节的内存空间就能够存放，而汉字需要两个字节。C)汉字编码空间更大，包含了所有的ASCII编码。D)ASCII是第二代ASC码的意思，而简体中文一般使用GB2312编码。6、下列软件中是操作系统的是：A)WordB)PDFReaderC)AndroidD)WPS7、关于互联网，下面的说法哪一个是正确的：2015年宁波市第30届中小学生计算机程序设计竞赛初中组初赛试题第2页共8页A)新一代互联网使用的IPv6标准是IPv4标准的升级与补充，使用64位二进制表示。B)互联网的入网域名指向主机IP地址，一个域名可以指向多个IP。C)IPv6标准也可以和使用IPv4标准的主机相互通信。D)IPv6只是一个理想模型，还未开始使用。8、关于HTML下面哪种说法是正确的：A）HTML实现了文本、图形、声音乃至视频信息的统一编码。B）最新的HTML标准为HTML5，是HTML的第五次重大修改。C）HTML全称为超文本传输协议。D）HTML本身只能做出静态效果，动态效果必须借助Flash来实现。9、机器语言是用二进制代码表示的计算机能直接识别和执行的一种机器指令的集合，一般由高级程序设计语言编译生成。关于机器语言，下面哪个说法是正确的：A)同一个机器语言指令集在不同型号的计算机上不通用。B)机器语言直接交给CPU运行，因此使用机器语言编写程序代码更短，速度更快。C)机器语言的指令集合中加入注释，会使得文件变长，运行速度变慢。D)以上说法都不对。10、已知大写字母A的ASCII编码为65（十进制），则十进制70表示ASCII码中的字符为：A)DB)EC)FD)G11、若根节点的深度为1，1024个节点的二叉树，深度最少是A)9B)10C)11D)1212、有六个元素ABCDEF从左至右依次顺序进入队列，在进队过程中会有元素从队首出队列，且最终所有元素出队列。问下列唯一合法的出队序列？A)EDCFABB)ABCDEFC)CDFEBAD)BCDAEF13、后缀表达式abc+*d-中，a=1,b=2,c=3,d=4,则该后缀表达式的值是：A)3B)-1C)5D)114、无向完全图是图中每对顶点之间都恰有一条边的简单图。已知无向完全图G有5个顶点，则它共有（）条边A)10B)25C)5D)415、深度优先搜索时，控制与记录搜索过程的数据结构是（）：A)链表B)队列C)栈D)散列表16.有一个由2015个整数构成的顺序表，假定表中的元素已经按降序排列，采用二分查找定位一个元素。则最多需要几次比较就能确定是否存在所查找的元素：A)2015次B)10次C)11次D)12次17、在含有2015个元素的双向链表中查询是否存在关键字为key的元素，最坏情况下运行的查找次数是（）。A)2014次B)2015次C)11次D)12次2015年宁波市第30届中小学生计算机程序设计竞赛初中组初赛试题第3页共8页18、一个正整数在十六进制下有200位，则它在二进制下最多可能有（）位。A)798B)799C)800D)80119、2014年美国计算机科学家莱斯利·兰波特，因提出多核与分布协作算法，获得（）大奖，奖金为25万美元。A)诺贝尔信息学奖B)图灵奖C)菲尔兹奖D)以上选项都不对20、以下哪一位是目前唯一一个获得过有“计算机界的诺贝尔奖”之称的“图灵奖”的美籍华人：A)李政道B)杨振宁C)莫言D)姚期智二、问题求解（每小题5分，共10分）1．原字符串中任意一段连续的字符所组成的新字符串称为子串。则字符“AAABBC”共有不同的非空子串。2．小明在玩一个数字游戏，他随手在纸上写下了一个三位数abc，接着将这个三位数各个数位上数字全部排列写下，依次为acb，bac，bca，cab，cba这五个数。现在，小明算出后面写下的五个数的和为1340，请你猜出小明写下的这个三位数为。三、阅读程序写结果（每题8分，共32分）1．vara,b,c,t:longint;beginreadln(a,b,c);ifabthenbegint:=a;a:=b;b:=t;end;ifacthenbegint:=a;a:=c;c:=t;end;ifbcthenbegint:=b;b:=c;c:=t;end;writeln(a,'',b,'',c);end.2．varn,i,ans:integer;beginreadln(n);输入：102015输出：2015年宁波市第30届中小学生计算机程序设计竞赛初中组初赛试题第4页共8页ans:=0;fori:=1tondoif(nmodi)=0thenans:=ans+i;writeln(ans);end．3．varn,i,j,t,ans:longint;x,y:array[0..500]oflongint;beginreadln(n);fori:=1tondoreadln(x[i],y[i]);fori:=1ton-1doforj:=1ton-idobeginifx[j]x[j+1]thenbegint:=x[j];x[j]:=x[j+1];x[j+1]:=t;end;ify[j]y[j+1]thenbegint:=y[j];y[j]:=y[j+1];y[j+1]:=t;end;end;ans:=0;fori:=1tondoans:=ans+abs(i-x[i])+abs(i-y[i]);writeln(ans);end.输入：25输出：2015年宁波市第30届中小学生计算机程序设计竞赛初中组初赛试题第5页共8页4．vara:array[1..20]oflongint;f:Array[0..20000]ofboolean;i,n:longint;proceduredfs(t,sum:longint);beginiftnthenbeginf[sum]:=true;exit;end;dfs(t+1,sum);dfs(t+1,sum+a[t]);end;beginreadln(n);fori:=1tondoread(a[i]);dfs(1,0);fori:=1to20000doifnotf[i]thenbreak;writeln(i);end.输入：6111221566566输出：输入：91248163264128256输出：2015年宁波市第30届中小学生计算机程序设计竞赛初中组初赛试题第6页共8页四．程序填空（前2空，每空2分，后8空，每空3分，共28分）1．(螺旋矩阵)一个n行m列的螺旋矩阵可由如下方法生成：从矩阵的左上角（第1行第1列）出发，初始时向右移动；如果前方是未曾经过的格子，则继续前进，否则右转；重复上述操作直至经过矩阵中所有格子。根据经过顺序，在格子中依次填入1,2,3,...,n2，便构成了一个螺旋矩阵。输入n和m，输出一个螺旋矩阵，同一行中相邻两个数字中间有一个空格，行末没有空格。varn,m,i,j,t,s:longint;a:array[-1..11,-1..11]oflongint;dx:array[1..4]oflongint=(-1,0,0,1);dy:array[1..4]oflongint=(0,-1,1,0);beginreadln(n,m);i:=1;j:=1;t:=1;s:=1;//t表示当前要填的数值，s表示当前填的方向；a[i,j]:=t;while①dobegininc(t);i:=i+dx[s];j:=②;if(in)or(i1)or(③)or(j1)or(a[i,j]0)thenbegini:=i-dx[s];j:=j-dy[s];dec(t);s:=s+1;ifs=5then④;continue;end;a[i,j]:=t;end;fori:=1tondobeginforj:=1tom-1dowrite(a[i,j],'');writeln(⑤);end;end.输入：44输出：123412131451116156109872015年宁波市第30届中小学生计算机程序设计竞赛初中组初赛试题第7页共8页2.（二叉树先序遍历）给出一棵二叉树的中序与后序排列。求出它的先序排列，其中树结点用不同的大写字母表示，例如输入BADCE，BDECA分别表示中序和后序，输出：ABCDE表示先序遍历。varmid,last:string;proceduredfs(mid,last:string);vari,len:longint;root:char;beginiflength(mid)=0thenexit;len:=length(mid);root:=①;fori:=1tolendoif②thenbreak;③;dfs(copy(mid,1,i-1),④);dfs(⑤,copy(last,i,len-i));end;beginreadln(mid);readln(last);dfs(mid,last);writeln;end.2015年宁波市第30届中小学生计算机程序设计竞赛初中组初赛试题第8页共8页2015宁波初中组（Pascal语言）参考答案与评分标准一、单项选择题：（每题1.5分）1.D2.C3.B4.B5.B6.C7.C8.B9.A10.C11.C12.B13.D14.A15.C16.C17.B18.C19.B20.D二、问题求解：（共2题，每空5分，共计10分）1．172．214三、阅读程序写结果（共4题，每题8分，共计32分）1.1015202.313.84.512四．完善程序(前2空，每空2分，后8空，每空3分，共28分)（说明：以下各程序填空可能还有一些等价的写法）1.①tn*m或者n*mt或者tn*m②j+dy[s]③jm或者mj④s:=1或者s:=2或者s:=s-4或者dec(s,4)⑤a[i,m]或者a[i,j+1]2.①last[len]或者last[length(mid)]或者last[length(last)]②mid[i]=root或者root=mid