第十六屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題及答案

第十六屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題及答案(提高組)(總12頁)--本頁僅作為文檔封面，使用時請直接刪除即可----10第十六屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題〔提高組 Pascal語言 二小時完成〕●● 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 ●●一.單項選擇題〔101.515確選項〕與十六進制數(shù)A1.2等值的十進制數(shù)是〔 〕。A．101.2 B.111.4 C.161.125 D.177.25一個字節(jié)〔byte〕由〔 〕個二進制位組成。A.8 B.16 C.32 D.以上都有可能以下規(guī)律表達式的值恒為真的是〔 〕。P∨(﹁P∧Q)∨(﹁P∧﹁Q) B.Q∨(﹁P∧Q)∨(P∧﹁Q)C. P∨Q∨(P∧﹁Q)∨(﹁P∧Q) D.P∨﹁Q∨(P∧﹁Q)∨(﹁P∧﹁Q)Linux下可執(zhí)行文件的默認(rèn)擴展名為〔 〕。exe B.com C.dll D.以上都不是假設(shè)在某個進制下等式7*7=41成立，那么在該進制下等式12*12=( 也成立。A.100 B.144 C.164 D.196提出“存儲程序”的計算機工作原理的是〔 〕?？藙诘隆は戕r(nóng) B.戈登·摩爾 C.查爾斯·巴比奇 馮·諾伊曼7.前綴表達式“+3*2+5 12”的值是〔 A.23 B.25 C.37 D.65主存儲器的存取速度比中心處理器〔CPU〕的工作速度慢得多，從而使得后原理，CPU所訪問的存儲單元通常都趨于聚攏在一個較小的連續(xù)區(qū)域中。于是，為了提高系統(tǒng)整體的執(zhí)行效率，在CPU中引入了〔 〕。存放器 B.高速緩存 C.閃存 D.外存1〔〕號位置。2kB.2k+1C.k/2D.(k+1)/2以下競賽活動中歷史最悠久的是〔 〕。全國青少年信息學(xué)奧林匹克聯(lián)賽〔NOIP〕全國青少年信息學(xué)奧林匹克競賽〔NOI〕國際信息學(xué)奧林匹克競賽〔IOI〕亞太地區(qū)信息學(xué)奧林匹克競賽〔APIO〕二、不定項選擇題〔101.515正確選項。多項選擇或少選均不得分〕入棧的挨次為R1、R2、R3、R4、R5。假設(shè)第1個出棧的是R3，那么，第5個出棧的可能是〔 〕。R1 B.R2 C.R4 D.R5Pascal語言、C語言和C++語言都屬于〔 〕。高級語言 B.自然語言 C.解釋性語言 D.編譯性語言指在排序過程中〔除了存儲待排序元素以外的〕關(guān)心空間的大小與數(shù)據(jù)規(guī)模無關(guān)的排序算法。以下屬于原地排序的有〔 〕。冒泡排序 B.插入排序 C.基數(shù)排序 D.選擇排序在整數(shù)的補碼表示法中，以下說法正確的選項是〔 〕。只有負(fù)整數(shù)的編碼最高位為1在編碼的位數(shù)確定后，所能表示的最小整數(shù)和最大整數(shù)確實定值一樣整數(shù)0只有唯一的一個編碼兩個用補碼表示的數(shù)相加時，假設(shè)在最高位產(chǎn)生進位，則表示運算溢出后序遍歷序列是CBFEGDA，則根結(jié)點的左子樹的結(jié)點個數(shù)可能是〔 〕。A.0 B.2 C.4 D.6在以下HTML語句中，可以正確產(chǎn)生一個指向NOI官方網(wǎng)站的超鏈接的是〔 〕。<aurl=”“:///“://NOI</a><ahref=”“:///“://NOI</a><a>“:///“://</a><aname=”“:///“://NOI</a>關(guān)于拓?fù)渑判?，下面說法正確的選項是〔 〕。全部連通的有向圖都可以實現(xiàn)拓?fù)渑判驅(qū)ν粋€圖而言，拓?fù)渑判虻慕Y(jié)果是唯一的拓?fù)渑判蛑腥攵葹?的結(jié)點總會排在入度大于0的結(jié)點的前面拓?fù)渑判蚪Y(jié)果序列中的第一個結(jié)點肯定是入度為0的點個平面的法線是指與該平面垂直的直線。過點(1,1,1)、(0,3,0)、(2,0,0)的平面的法線是〔 〕。A.過點(1,1,1)、(2,3,3)的直線B.過點(1,1,1)、(3,2,1)的直線C.過點(0,3,0)、(-3,1,1)的直線D.過點(2,0,0)、(5,2,1)的直線rlink，分別指向該結(jié)點的前驅(qū)和后繼。p，則下面語句序列中正確的選項是〔〕。p^.rlink^.llink:=p^.rlink; p^.llink^.rlink:=p^.llink;dispose(p);p^.llink^.rlink:=p^.rlink; p^.rlink^.llink:=p^.llink;dispose(p);p^.rlink^.llink:=p^.llink; p^.rlink^.llink^.rlink:=p^.rlink; dispose(p);p^.llink^.rlink:=p^.rlink; p^.llink^.rlink^.llink:=p^.llink; dispose(p);今年〔2023年〕發(fā)生的大事有〔 〕?；萜赵囼炇覡幷搯TVinayDeolalikar自稱證明白P≠NP英特爾公司收購了計算機安全軟件公司邁克菲〔McAfee〕iPhone4Windows7三、問題求解〔3515〕LZW的編碼會被追加到詞典中，并用于后繼信息的編碼。舉例說明，考慮一個待編碼的信息串：“xyxyyyyxyx”。初始時詞典中3x，1；y，2；第三個為3。于是，串“xyx”1-2-1〔其中“-”為編碼分隔。但由于有了一個空格，我們就知道前面的“xyx”是一個單詞，而由于該單詞沒有消滅在詞典中，我們就可4。然后，依據(jù)的詞典，對后繼信息進展編碼，依此類推。于是，最終得到編碼：1-2-1-3-2-2-3-5-3-4。2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6，則解碼后的信息串是“ ”。邊。記T為一個隊列，初始時為空?，F(xiàn)有n個總和不超過32的正整數(shù)依次入論這些數(shù)具體為何值，都能找到一種出隊的方式，使得存在某個時刻隊列T中的數(shù)之和恰好為9，那么n的最小值是 。四、閱讀程序?qū)懡Y(jié)果〔4728〕1constSIZE=10;vari,j,cnt,n,m:integer;data:array[1..SIZE]ofinteger;beginreadln(n,m);fori:=1tondoread(data[i]);fori:=1tondobegincnt:=0;forj:=1tondoif(data[i]<data[j])or((data[j]=data[i])and(j<i))theninc(cnt);ifcnt=mthenwriteln(data[i]);end;end.5 296 -8 0 16 87輸出：2、constSIZE=100;varna,nb,i,j,k:integer;a,b:array[1..SIZE]ofinteger;beginreadln(na);fori:=1tonadoread(a[i]);readln(nb);fori:=1tonbdoread(b[i]);i:=1; j:=1;while(i<=na)and(j<=nb)dobeginifa[i]<=b[j]thenbeginwrite(a[i],‘‘);inc(i);endelsebeginwrite(b[j],‘‘);inc(j);end;end;ifi<=nathenfork:=itonadowrite(a[k],‘‘);ifj<=nbthenfork:=jtonbdowrite(b[k],‘‘);end.51313574261014輸出：3、constNUM=5;varn:integer;functionr(n:integer):integer;vari:integer;beginifn<=NUMthenbeginr:=n;exit;end;fori:=1toNUMdoifr(n-i)<0thenbeginr:=i;exit;end;r:=-1;end;beginreadln(n);writeln(r(n));end.輸入：16 輸出：4、constSIZE=100;varn,m,x,y,i:integer;r:array[1..SIZE]ofinteger;map:array[1..SIZE,1..SIZE]ofboolean;found:boolean;functionsuccessful:boolean;vari:integer;beginfori:=1tondoifnotmap[r[i]][r[imodn+1]]thenbeginsuccessful:=false;exit;end;successful:=true;end;procedureswap(vara,b:integer);vart:integer;begint:=a; a:=b; end;procedureperm(left,right:integer);vari:integer;beginiffoundthen exit;ifleft>rightthenbeginifsuccessfulthenbeginfori:=1tondowrite(r[i],‘‘);found:=true;end;exit;end;fori:=lefttorightdobeginswap(r[left],r[i]);perm(left+1,right);swap(r[left],r[i]);end;end;beginreadln(n,m);fillchar(map,sizeof(map),false);fori:=1tomdobeginreadln(x,y);map[x][y]:=true;map[y][x]:=true;end;fori:=1tondor[i]:=i;found:=false;perm(1,n);ifnotfoundthenwriteln(‘Nosolution!’);end.9 121 22 33 44 55 66 11 72 73 84 85 96 9輸出：四、完善程序〔12102.527〕過河問題〕在一個月黑風(fēng)高的夜晚，有一群人在河的右岸，想通地唯一的一根獨木橋走到河的左岸。在這伸手不見五指的黑夜里，過橋時必需借助燈光來照明。不幸的是，他們只有一盞燈。另外，獨木橋上最多承受兩個人同時經(jīng)過，否則就會坍塌。每個人單獨過橋都需要肯定的時間，不同的人需要的時間可能不同。兩個人一起過橋時，由于只有一盞燈，全部需要的時間是較慢的那n〔2<=n<100〕n要的時間，請計算總共最少需要多少時間，他們才能全部到達河的左岸。1、2、4，則總共最2+1+4=7。constSIZE=100;INFINITY=10000;LEFT=true;RIGHT=false;LEFT_TO_RIGHT=true;RIGHT_TO_LEFT=false;varn,i:integer;time:array[1..SIZE]ofinteger;pos:array[1..SIZE]ofboolean;functionmax(a,b:integer):integer;beginifa>bthenmax:=aelsemax:=b;end;functiongo(stage:boolean):integer;vari,j,num,tmp,ans:integer;beginif(stage=RIGHT_TO_LEFT)thenbeginnum:=0;ans:=0;fori:=1tondoifpos[i]=RIGHTthenbegininc(num);iftime[i]>ansthenans:=time[i];end;if ① thenbegingo:=ans;exit;end;ans:=INFINITY;fori:=1ton-1doifpos[i]=RIGHTthenforj:=i+1tonthenifpos[j]=RIGHTthenbeginpos[i]:=LEFT;pos[j]:=LEFT;tmp:=max(time[i],time[j])+② ;iftmp<ansthenans:=tmp;pos[i]:=RIGHT;pos[j]:=RIGHT;end;go:=ans;endelseif(stage=LEFT_TO_RIGHT)thenbeginans:=INFINITY;fori:=1tondoif③ thenbeginpos[i]:=RIGHT;tmp:=④;iftmp<ansthenans:=tmp;⑤;end;

end;go:=ans;endelsego:=0;beginreadln(n);fori:=1tondobeginread(time[i]);pos[i]:=RIGHT;end;writeln(go(RIGHT_TO_LEFT));end.〕烽火臺又稱烽燧，是重要的軍事防范措施，一般建在險要處或交通要道上。一旦有敵情發(fā)生，白天燃燒柴草，通過濃煙表達信息；夜晚燃燒n號都有肯定的代價。為了使情報準(zhǔn)確地傳遞，在連續(xù)m個烽火臺中，至少要有費多少代價，才能使敵軍來襲之時，情報能在這兩座城市之間準(zhǔn)確傳遞。1、2、5、6、2，m3，4，25constSIZE=100;varn,m,r,i:integer;value,heap,pos,home,opt:array[1..SIZE]ofinteger;heapi//pos[iopt[iheapheap[pos[i]]=opt[i]heap[i]optopt[home[i]]=heap[i]procedureswap(i,j:integer);vartmp:integer;beginpos[home[i]]:=j;pos[home[j]]:=i;tmp:=heap[i];heap[i]:=heap[j];heap[j]:=tmp;tmp:=home[i];home[i]:=home[j];home[j]:=tmp;end;procedureadd(k:integer); vari:integer;begininc(r);heap[r]:=① ;pos[k]:=r;② ;i:=r;while(i>1)and(heap[i]<heap[idiv2])dobeginswap(i,idiv2);i:=idiv2;end;end;procedureremove(k:integer); vari,j:integer;begini:=pos[k];swap(i,r);dec(r);ifi=r+1then exit;while(i>1)and(heap[i]<heap[idiv2])dobeginswap(i,idiv2);i:=idiv2;end;whilei+i<=rdobeginif(i+i+1<=r)and(heap[i+i+1]<h