2019余姚程序設(shè)計競賽小學組初賽試題final

2019年余姚市程序設(shè)計競賽初賽試題（C++/Pascal語言二小時完成）??全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效??一.單項選擇題（共20題，每題2分，共計40分。每題有且僅有一個正確答案。）1、已知英文字母a的ASCII代碼值是十進制數(shù)97,那么字母e的ASCII代碼十六進制表示值是（ ）A）64H B）65H C）66H D）1012、美籍匈牙利數(shù)學家馮?諾依曼對計算機科學發(fā)展所做出的貢獻包括（）。A）提出理想計算機的數(shù)學模型，成為計算機科學的理論基礎(chǔ)。B）提出存儲程序工作原理，對現(xiàn)代電子計算機的發(fā)展產(chǎn)生深遠影響。C）采用集成電路作為計算機的主要功能部件。D）指出計算機性能將以每兩年翻一番的速度向前發(fā)展。3、IPv6地址是由（）位二進制數(shù)碼表示的。TOC\o"1-5"\h\zA）16B）32 C）128 D）644、目前計算機芯片（集成電路）制造的主要原料是（），它是一種可以在沙子中提煉出的物質(zhì)。A）硅B）銅 C）鍺 D）鋁5、彩色顯示器所顯示的色彩，是由紅色、藍色和（）色混合而成的。A）黃B）綠 C）橙 D） 紫6、以下字符串中，字典序最小的（ ）。A）YYOI2019B）YYOICC）YYOIC++D）YYOIP7、佳佳在網(wǎng)上購買了一個空間，建設(shè)了一個網(wǎng)站。那么，他向網(wǎng)站上上傳網(wǎng)頁時最有可能采用的網(wǎng)絡(luò)協(xié)議是（ ）。A）HTTPB）TCPC）POP3D）FTP8、下列著名人物中，不是計算機相關(guān)領(lǐng)域?qū)＜业氖茿）王選B）圖靈C）馮諾依曼D）屠呦呦9、小明一回到家，第一件事情就是對電腦喊一聲“開機”，該臺電腦就乖乖地開機了。這種現(xiàn)象說明了該臺電腦使用的技術(shù)是（）A）網(wǎng)絡(luò)技術(shù)B）語音識別技術(shù)C）字符識別技術(shù) D）自動關(guān)機技術(shù)10、如果將人體比作計算機，那么人體的記憶中樞相當于以下計算機部件的：（）A）運算器 B）中央處理器 C）控制器 D）內(nèi)存

11、一個正整數(shù)在十六進制下有200位，則它在二進制下最多可能有()位。A)798B)799C)800D)80112、后綴表達式abc+*d-中，a=1,b=2,c=3,d=4則該后綴表達式的值是：A)3B)-1C)5D)113、十進制小數(shù)0.625轉(zhuǎn)成二進制數(shù)是( )。A)0.1B)0.101C)0.011D)0.0114、對于棧來說,若進棧序列為1、2、3、4、5、6,進棧過程中可以出棧，則下列出棧序列中不可能的是()。A)134256B)243165C)345621D)14562315、若根節(jié)點的深度為1，1024個節(jié)點的二叉樹，深度最少是A)9 B)10C)11D)1216、一棵二叉樹前序遍歷為ABDECFGH，后序遍歷為EDBGFHCA，以下可能的中序遍歷有()。A)BDEAFGCHB)EDBAGFCHC)DBEAFGCHD)DEBAFCGH17、深度優(yōu)先搜索時，控制與記錄搜索過程的數(shù)據(jù)結(jié)構(gòu)是( )：A)鏈表B)隊列C)棧D)散列表18、給定一個長度為5的進隊序列(每個元素互不相同)，一共存在的出隊序列種數(shù)為：A)1B)5C)25D)4219、有如下程序段，該程序段運行時，在控制臺輸入5,則輸出的內(nèi)容為( )。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.余姚市程序設(shè)計初賽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;數(shù)組元素a[1]到a[10]的值依次為“12,19,27,27,27,31,38,46,55,72”。控制臺輸入“27”后運行程序段，運行結(jié)束后，下列說法不正確的是：A)程序運行結(jié)束后j不等于1B)j=m-1被執(zhí)行了2次C)該次程序運行后，m存儲最左邊的Key值的位置D)將m=(i+j)/2(或m:=(i+j)div2)改成m=(i+j+1)/2(或m:=(i+j+1)div2)分別執(zhí)行程序段后，m的值相同。二.閱讀程序(程序輸入不超過定義變量、數(shù)組或字符串定義的范圍；判斷題正確填勺”,錯誤填“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行“區(qū)-1”改成(C++)“sqrt(x)”、(Pascal)”trunc(sqrt(x))運行結(jié)果不會改變(當輸入的x為大于1的整數(shù))。程序3)程序第6行，變量flag可以不賦初值，不影響程序運行結(jié)果。4)程序第12行的“break”語句刪除，會影響程序運行結(jié)果。選擇題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結(jié)果不會改變（ ）2）若輸入n=200000個數(shù)，每個數(shù)的范圍-20000<=a[i]<=20000,變量可能產(chǎn)生越界錯誤（ ）3）最終輸出結(jié)果小于輸入的n個數(shù)之和（ ）4）yes（a,b）函數(shù)中，去掉“else”（Pascal代碼同時在上一句后加上“;”）運行結(jié)果不變（ ）選擇題5）下列那個表達式是不存在的（ ）A）a[0] B）a[1101]C）a[200001]D）a[200000]6）若輸入n為10,接下來依次輸入“-12-101234-726”，則輸出結(jié)果為：（ ）A）11 B）12 C）2 D）187）若輸入的n為100,每個數(shù)-100<=a[i]<=100,以下選項中不可能輸出的結(jié)果為（）A）-10000 B）-100 C）0D）9999余姚市程序設(shè)計初賽5余姚市程序設(shè)計初賽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、(開關(guān)燈問題)小明在郵局值夜班，十分無聊，他對郵局內(nèi)的200個信筒(編號為0到199),全部打開。然后每隔一個信筒關(guān)閉一個(2,4,6,…)。然后每隔兩個信筒進行檢查(3,6,9,…)，若開著，則關(guān)上；若關(guān)著，則打開，接著再每隔3個(4,8,12,…)作類似工作。問最后結(jié)果哪些信筒開著。余姚市程序設(shè)計初賽余姚市程序設(shè)計初賽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.①處應(yīng)填( )C++：A)j=iPascal：A)j:=i)Bj=i+1 C)j=i-1 Dj++)Bj:=i+1C)j:=i-1Dinc(j)②處應(yīng)填( )C++：A)j<maxn)Bj<=maxnC)i<maxnDi<=maxnPascal：A)j<maxn)Bj<=maxnC)i<maxnDi<=maxn③處應(yīng)填( )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]④處應(yīng)填( )C++：A)i-j Bi+j Cj-iDj*2Pascal：A)i-j Bi+j Cj-iDj*2⑤處應(yīng)填( )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、(高精度加法)編寫一個高精度加法程序，可以實現(xiàn)100位以內(nèi)兩個非負整數(shù)加法運算。輸入兩行，每行一個合法的十進制大整數(shù)。要求輸出兩數(shù)之和。例如:輸入：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')