2019余姚程序设计竞赛小学组初赛试题final

2019年余姚市程序设计竞赛初赛试题（C++/Pascal语言二小时完成）••全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效••一.单项选择题（共20题，每题2分，共计40分。每题有且仅有一个正确答案。）1、已知英文字母a的ASCII代码值是十进制数97,那么字母e的ASCII代码十六进制表示值是（ ）A）64H B）65H C）66H D）1012、美籍匈牙利数学家冯•诺依曼对计算机科学发展所做出的贡献包括（）。A）提出理想计算机的数学模型，成为计算机科学的理论基础。B）提出存储程序工作原理，对现代电子计算机的发展产生深远影响。C）采用集成电路作为计算机的主要功能部件。D）指出计算机性能将以每两年翻一番的速度向前发展。3、IPv6地址是由（）位二进制数码表示的。TOC\o"1-5"\h\zA）16B）32 C）128 D）644、目前计算机芯片（集成电路）制造的主要原料是（），它是一种可以在沙子中提炼出的物质。A）硅B）铜 C）锗 D）铝5、彩色显示器所显示的色彩，是由红色、蓝色和（）色混合而成的。A）黄B）绿 C）橙 D） 紫6、以下字符串中，字典序最小的（ ）。A）YYOI2019B）YYOICC）YYOIC++D）YYOIP7、佳佳在网上购买了一个空间，建设了一个网站。那么，他向网站上上传网页时最有可能采用的网络协议是（ ）。A）HTTPB）TCPC）POP3D）FTP8、下列著名人物中，不是计算机相关领域专家的是A）王选B）图灵C）冯诺依曼D）屠呦呦9、小明一回到家，第一件事情就是对电脑喊一声“开机”，该台电脑就乖乖地开机了。这种现象说明了该台电脑使用的技术是（）A）网络技术B）语音识别技术C）字符识别技术 D）自动关机技术10、如果将人体比作计算机，那么人体的记忆中枢相当于以下计算机部件的：（）A）运算器 B）中央处理器 C）控制器 D）内存

11、一个正整数在十六进制下有200位，则它在二进制下最多可能有()位。A)798B)799C)800D)80112、后缀表达式abc+*d-中，a=1,b=2,c=3,d=4则该后缀表达式的值是：A)3B)-1C)5D)113、十进制小数0.625转成二进制数是( )。A)0.1B)0.101C)0.011D)0.0114、对于栈来说,若进栈序列为1、2、3、4、5、6,进栈过程中可以出栈，则下列出栈序列中不可能的是()。A)134256B)243165C)345621D)14562315、若根节点的深度为1，1024个节点的二叉树，深度最少是A)9 B)10C)11D)1216、一棵二叉树前序遍历为ABDECFGH，后序遍历为EDBGFHCA，以下可能的中序遍历有()。A)BDEAFGCHB)EDBAGFCHC)DBEAFGCHD)DEBAFCGH17、深度优先搜索时，控制与记录搜索过程的数据结构是( )：A)链表B)队列C)栈D)散列表18、给定一个长度为5的进队序列(每个元素互不相同)，一共存在的出队序列种数为：A)1B)5C)25D)4219、有如下程序段，该程序段运行时，在控制台输入5,则输出的内容为( )。C++代码：#include<bits/stdc++.h>usingnamespacestd;intmain(){intn;stringst;st="";cin>>n;for(inti=1;i<=n;i++){for(intj=1;j<=i;j+=2)st=st+"*";cout<<st<<endl;)return0;Pascal代码：varn,i,j:longint;st:string;beginPascal代码：varn,i,j:longint;st:string;beginreadln(n);st:='';fori:=1tondobeginj：=1;whilej<=idobeginst:=st+'*';j：=j+2;end;writeln(st);end;end.余姚市程序设计初赛2******************************A)B)C)D)20、某二分查找的算法程序段如下:C++代码C++代码i=1;j=10;scanf("%d",&Key);while(i<=j){m=(i+j)/2;if(Key<=a[m])j=m-1;elsei=m+1;)Pascal代码i:=1;j:=10;readln(Key);while(i<=j)dobeginm:=(i+j)div2;ifKey<=a[m]thenj:=m-1elsei:=m+1;end;数组元素a[1]到a[10]的值依次为“12,19,27,27,27,31,38,46,55,72”。控制台输入“27”后运行程序段，运行结束后，下列说法不正确的是：A)程序运行结束后j不等于1B)j=m-1被执行了2次C)该次程序运行后，m存储最左边的Key值的位置D)将m=(i+j)/2(或m:=(i+j)div2)改成m=(i+j+1)/2(或m:=(i+j+1)div2)分别执行程序段后，m的值相同。二.阅读程序(程序输入不超过定义变量、数组或字符串定义的范围；判断题正确填勺”,错误填“F"；无特殊说明，判断题1分，选择题2分，共计30分)C++代码：1#include<bits/stdc++.h>C++代码：1#include<bits/stdc++.h>2usingnamespacestd;3intmain(){4intx;5scanf("%d",&x);6boolflag=true;7for(inti=2;i<=x-1;i++)8if(x%i==0)9{10printf("%d\n",i);11flag=false;12break;13)14if(flag)printf("Yes'n");15elseprintf("No\n");16return0;17)Pascal代码：1var2i,x:longint;3flag:boolean;4begin5readln(x);6flag:=true;7fori:=2tox-1do8ifxmodi=0then9begin10writeln(i);11flag:=false;12break;13end;14ifflagthenwriteln('Yes')15elsewriteln('No');16end.判断题：1)程序运行后，在控制台输入-1,会导致程序崩溃程序2)若将第7行“区-1”改成(C++)“sqrt(x)”、(Pascal)”trunc(sqrt(x))运行结果不会改变(当输入的x为大于1的整数)。程序3)程序第6行，变量flag可以不赋初值，不影响程序运行结果。4)程序第12行的“break”语句删除，会影响程序运行结果。选择题5)该程序段时间复杂度为：A)O(1) B)O(n) C)O(lgn)D)O(sqrt(n))6)当输入x为39时，A)3 B)控制台输出的第一行为：38 C)YesD)No7)当输入x为97时，A)7 B)控制台输出的第一行为：97 C)YesD)No2.C++代码：Pascal代码：1#include<bits/stdc++.h>1var2usingnamespacestd;2 a,f,sum:array[0..200000]oflongint;3inta[200001],f[200001],sum[200001],n;3n,i,maxx,tmp:longint;4inttmp=1e9+7;4functionyes(a,b:longint):longint;5intmaxx=-1e9-7;5begin6intyes(inta,intb){6ifa>bthenexit(b)7if(a>b)returnb;7elseexit(a);8elsereturna;8end;9)9begin10intmain(){10readln(n);11scanf("%d",&n);11fori:=1tondoread(a[i]);12for(inti=1;i<=n;i++)12tmp:=1000000007;13 scanf("%d",&a[i]);13maxx:=-1000000007;14for(inti=1;i<=n;i++){14fori:=1tondo15 sum[i]=sum[i-1]+a[i];15begin16 tmp=yes(sum[i-1],tmp);16 sum[i]:=sum[i-1]+a[i];17 f[i]=sum[i]-tmp;17 tmp:=yes(sum[i-1],tmp);18)18 f[i]:=sum[i]-tmp;19for(inti=1;i<=n;i++)19end;20 if(f[i]>maxx)20fori:=1tondoif(f[i]>maxx)thenmaxx:=f[i];21 maxx=f[i];22writeln(maxx);22printf("%d\n",maxx);23end.23)完成下面的判断题和单选题判断题TOC\o"1-5"\h\z1）若将18行的f[i]>maxx改成f[i]>=maxx结果不会改变（ ）2）若输入n=200000个数，每个数的范围-20000<=a[i]<=20000,变量可能产生越界错误（ ）3）最终输出结果小于输入的n个数之和（ ）4）yes（a,b）函数中，去掉“else”（Pascal代码同时在上一句后加上“;”）运行结果不变（ ）选择题5）下列那个表达式是不存在的（ ）A）a[0] B）a[1101]C）a[200001]D）a[200000]6）若输入n为10,接下来依次输入“-12-101234-726”，则输出结果为：（ ）A）11 B）12 C）2 D）187）若输入的n为100,每个数-100<=a[i]<=100,以下选项中不可能输出的结果为（）A）-10000 B）-100 C）0D）9999余姚市程序设计初赛5余姚市程序设计初赛53.C++代码：Pascal代码：1#include<bits/stdc++.h>1var2usingnamespacestd;2x,f,head,tail:longint;3intx,f;3stack1,stack2:array[0..10000005]oflongint;4intstack1[10000005],stack2[10000005];4begin5intmain()5readln(x);6(6head:=0;tail:=1;7scanf("%d",&x);7stack1[head]:=x;8inthead=0,tail=1;8stack2[head]:=1;9stack1[head]=x;9whilehead<taildo10stack2[head]=1;10begin11while(head<tail){11head:=head+1;12head++;12ifstack1[head]=xthen13if(stack1[head]==x){13begin14printf("%d\n",stack2[head]-1);14writeln(stack2[head]-1);15return0;15halt;16)16end;17tail++;17inc(tail);18stack1[tail]=stack1[head]-stack2[head];18stack1[tail]:=stack1[head]-stack2[head];19stack2[tail]=stack2[head]+1;19stack2[tail]:=stack2[head]+1;20tail++;20inc(tail);21stack1[tail]=stack1[head]+stack2[head];21stack1[tail]:=stack1[head]+stack2[head];22stack2[tail]=stack2[head]+1;22stack2[tail]:=stack2[head]+1;23)23end;24return0;24end.25)判断题：1)运行x=1时输出为12)这个算法的复杂度是多项式的3)当程序成功运行时x改为-x时答案不会改变4)(C++)第10行、(Pascal)第8行1改为0,且输出语句中去掉-1答案不变选择题：5)当输入x=4时，输出为：A)3B)2C)1D)程序已停止工作6)当输入x=8时，输出为：A)3 B)4C)5 D)67)若有无限时间和无限空间x=10000时，输出为：A)143B)142C)141D)140三.完善程序(每空3分，共30分)1、(开关灯问题)小明在邮局值夜班，十分无聊，他对邮局内的200个信筒(编号为0到199),全部打开。然后每隔一个信筒关闭一个(2,4,6,…)。然后每隔两个信筒进行检查(3,6,9,…)，若开着，则关上；若关着，则打开，接着再每隔3个(4,8,12,…)作类似工作。问最后结果哪些信筒开着。余姚市程序设计初赛余姚市程序设计初赛6C++代码：#include<bits/stdc++.h>usingnamespacestd;#definemaxn200intmain(){inti,j,open[maxn];for(i=0;i<maxn;i++)open[i]=1;for(i=2;i<maxn;i++){TOC\o"1-5"\h\z① ；while(② ){open[j]=③j= ④ ；))for(i=0;i<maxn;i++)if(⑤ )cout<<i<<"";cout<<endl;return0;)Pascal代码：constmaxn=200;vari,j:longint;open:array[0..maxn]oflongint;beginfori:=0tomaxn-1doopen[i]:=1;fori:=2tomaxn-1dobegin① ；while②dobeginopen[j]:=③,j:=④;end;end;fori:=0tomaxn-1doif⑤then

write(i,'');writeln;end.①处应填( )C++：A)j=iPascal：A)j:=i)Bj=i+1 C)j=i-1 Dj++)Bj:=i+1C)j:=i-1Dinc(j)②处应填( )C++：A)j<maxn)Bj<=maxnC)i<maxnDi<=maxnPascal：A)j<maxn)Bj<=maxnC)i<maxnDi<=maxn③处应填( )C++：A)open[j]-1B1-open[j]C)open[j-1]Dopen[j-i]Pascal：A)open[j]-1B1-open[j]C)open[j-1]Dopen[j-i]④处应填( )C++：A)i-j Bi+j Cj-iDj*2Pascal：A)i-j Bi+j Cj-iDj*2⑤处应填( )C++：A)open[i]==-1B)open[i]==0C)open[i]==1D)open[i]==2Pascal：A)open[i]=-1B)open[i]=0C)open[i]=1Dopen[i]=22、(高精度加法)编写一个高精度加法程序，可以实现100位以内两个非负整数加法运算。输入两行，每行一个合法的十进制大整数。要求输出两数之和。例如:输入：C++代码：#include<bits/stdc++.h>usingnamespacestd;intk1,k2,c1,c2,m,c[105];chars1[105],s2[105];intmain(){scanf("%s",s1+1);scanf("%s",s2+1);k1=strlen(s1+1);k2=strlen(s2+1);if(① )m=k1;elsem=k2;inti=m+1;while(i>1){if(k1>0)c1=s1[k1]-'0';elsec1=0;if(k2>0)c2=s2[k2]-'0';elsec2=0;TOC\o"1-5"\h\zc[i-1]= ② ;c[i]= ③;k1=k1-1;k2=k2-1;④ ;)for(i=1;i<=m+1;i++)if(⑤ )printf("%d",c[i]);return0;)Pascal代码：vari,k1,k2,c1,c2,m:longint;s1,s2:string;c:array[1..105]oflongint;beginreadln(s1);readln(s2);k1:=length(s1);k2:=length(s2);if①thenm:=k1elsem:=k2;i:=m+1;whilei>1dobeginifk1>0thenc1:=ord(s1[k1])-ord('0')