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

#第十六屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題及答案（提高組）（總12頁）-本頁僅作為文檔封面，使用時(shí)請直接刪除即可--內(nèi)頁可以根據(jù)需求調(diào)整合適字體及大小-

第十六屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題(提高組Pascal語言二小時(shí)完成)??全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效??一?單項(xiàng)選擇題(共10題，每題1.5分，共計(jì)15分。每題有且僅有一個(gè)正確選項(xiàng))與十六進(jìn)制數(shù)A1.2等值的十進(jìn)制數(shù)是()。101.2B.111.4C.161.125D.177.25一個(gè)字節(jié)(byte)由()個(gè)二進(jìn)制位組成。8B.16C.32D.以上都有可能以下邏輯表達(dá)式的值恒為真的是()。PV(-iPAQ)V(-iPA-iQ) B.QV(-iPAQ)V(PA-iQ)C.PVQV(PA-iQ)V(-iPAQ) D.PV-iQV(PA-iQ)V(-iPA-iQ)TOC\o"1-5"\h\zLinux下可執(zhí)行文件的默認(rèn)擴(kuò)展名為( )。A.exeB.comC.dll D.以上都不是如果在某個(gè)進(jìn)制下等式7*7二41成立，那么在該進(jìn)制下等式12*12=( )也成立。A.100B.144C.164D.196提出"存儲程序”的計(jì)算機(jī)工作原理的是( )?？藙诘?香農(nóng)B.戈登?摩爾C.查爾斯?巴比奇D.馮?諾伊曼前綴表達(dá)式"+3前綴表達(dá)式"+3A.23B.252+512"的值是(C.37D.65主存儲器的存取速度比中央處理器(CPU)的工作速度慢得多，從而使得后者的效率受到影響。而根據(jù)局部性原理，CPU所訪問的存儲單元通常都趨于聚集在一個(gè)較小的連續(xù)區(qū)域中。于是，為了提高系統(tǒng)整體的執(zhí)行效率，在CPU中引入了( )。A.寄存器B.高速緩存C.閃存D.外存完全二叉樹的順序存儲方案，是指將完全二叉樹的結(jié)點(diǎn)從上至下、從左至右，依次存放到一個(gè)順序結(jié)構(gòu)的數(shù)組中。假定根結(jié)點(diǎn)存放在數(shù)組的1號位置，則第k號結(jié)點(diǎn)的父結(jié)點(diǎn)如果存在話，應(yīng)當(dāng)存放在數(shù)組的( )號位置。A.2kB.2k+1C.k/2下取整D.(k+1)/2下取整

10?以下競賽活動中歷史最悠久的是（ ）。全國青少年信息學(xué)奧林匹克聯(lián)賽（NOIP）全國青少年信息學(xué)奧林匹克競賽（NOI）國際信息學(xué)奧林匹克競賽（IOI）亞太地區(qū)信息學(xué)奧林匹克競賽（APIO）二、不定項(xiàng)選擇題（共10題，每題1.5分，共計(jì)15分。每題有一個(gè)或多個(gè)正確選項(xiàng)。多選或少選均不得分）1.元素R仁R2、R3、R4、R5入棧的順序?yàn)镽仁R2、R3、R4、R5。如果第1個(gè)1.出棧的是R3,那么，第5個(gè)出棧的可能是（ ）。A.R1 B.R2 C.R4 D.R52.PascaIi吾u2.PascaIi吾u%

A.高級語言C語言和C++語言都屬于（B.自然語言C.解釋性語言D.編譯性語言原地排序是指在排序過程中（除了存儲待排序元素以外的）輔助空間的大小與數(shù)據(jù)規(guī)模無關(guān)的排序算法。以下屬于原地排序的有（）。冒泡排序 B.插入排序 C.基數(shù)排序D.選擇排序在整數(shù)的補(bǔ)碼表示法中，以下說法正確的是（ ）。只有負(fù)整數(shù)的編碼最高位為1在編碼的位數(shù)確定后，所能表示的最小整數(shù)和最大整數(shù)的絕對值相同整數(shù)0只有唯一的一個(gè)編碼兩個(gè)用補(bǔ)碼表示的數(shù)相加時(shí)，如果在最高位產(chǎn)生進(jìn)位，則表示運(yùn)算溢出5.一棵二叉樹的前序遍歷序列是ABCDEFG,后序遍歷序列是CBFEGDA,則根結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)個(gè)數(shù)可能是（）。A.0B.2C?4D.6在下列HTML語句中，可以正確產(chǎn)生一個(gè)指向N0I官方網(wǎng)站的超鏈接的是( )O<aurl二"”>歡迎訪問NOI網(wǎng)站</a><ahref=^^">歡迎訪問NOI網(wǎng)站</a><a>http://www.noi.cn</a><aname=n”>歡迎訪問NOI網(wǎng)站</a>關(guān)于拓?fù)渑判?，下面說法正確的是（ ）。所有連通的有向圖都可以實(shí)現(xiàn)拓?fù)渑判驅(qū)ν粋€(gè)圖而言，拓?fù)渑判虻慕Y(jié)果是唯一的拓?fù)渑判蛑腥攵葹?的結(jié)點(diǎn)總會排在入度大于0的結(jié)點(diǎn)的前面拓?fù)渑判蚪Y(jié)果序列中的第一個(gè)結(jié)點(diǎn)一定是入度為0的點(diǎn)8.一個(gè)平面的法線是指與該平面垂直的直線。過點(diǎn)（UJ）v（0.3,0）、（2.0,0）的平面的法線是（ ）。

過點(diǎn)(1JJ)x(2,3.3)的直線過點(diǎn)(1JJ)x(3.2.1)的直線過點(diǎn)(0,3,0)、(-3.1.1)的直線過點(diǎn)(2,0,0)、(5.2J)的直線9.雙向鏈表中有兩個(gè)指針域IIink和川叭分別指向該結(jié)點(diǎn)的前驅(qū)和后繼。設(shè)P指向鏈表中的一個(gè)結(jié)點(diǎn)，它的左右結(jié)點(diǎn)均非空。現(xiàn)要求刪除結(jié)點(diǎn)P,則下面語句序列中正確的是( )。p".IIink：rIink:=p：IIink;p：rIink：IIink:=p[IIink;p".rIink"?IIink八?rIink:=p".IIink：rIink:=p：IIink;p：rIink：IIink:=p[IIink;p".rIink"?IIink八?rIink:=p".IIink".rIink：IIink:=p^?IIink"?rIink:=p"?rIink;dispose(p);C?p".rIink".IIink:=p：IIink;p：rIink;dispose(p);D.p：IIink：rIink:=p：rlink;p：Ilink;dispose(p);10.今年（2010年）發(fā)生的事件有（ ）?；萜諏?shí)驗(yàn)室研究員VinayDeolaIikar自稱證明了P=/=NP英特爾公司收購了計(jì)算機(jī)安全軟件公司邁克菲（McAfee）蘋果公司發(fā)布了iPhone4手機(jī)微軟公司發(fā)布了Windows7操作系統(tǒng)三、問題求解（共3題，每題5分，共計(jì)15分）LZW是一種自適應(yīng)的詞典編碼。在編碼的過程中，開始時(shí)只有一部基礎(chǔ)構(gòu)造元素的編碼詞典，如果在編碼的過程中遇到一個(gè)新的詞條，則該詞條及一個(gè)新的編碼會被追加到詞典中，并用于后繼信息的編碼。舉例說明，考慮一個(gè)待編碼的信息串：uxyxyyyyxyxn。初始時(shí)詞典中只有3個(gè)條目，第一個(gè)為x,編碼為1;第二個(gè)為y,編碼為2；第三個(gè)為空格，編碼為3。于是，串"xyx"的編碼為1-2-1（其中為編碼分隔符），加上后面的一個(gè)空格就是1-2-1-3o但由于有了一個(gè)空格，我們就知道前面的uxyxn是一個(gè)單詞，而由于該單詞沒有出現(xiàn)在詞典中，我們就可以自適應(yīng)地把這個(gè)詞條添加到詞典里，編碼為4。然后，按照新的詞典，對后繼信息進(jìn)行編碼，依此類推。于是，最后得到編碼：1-2-1-3-2-2-3-5-3-4。我們可以看到，信息被壓縮了。壓縮好的信息傳遞到接收方，接收方也只要根據(jù)基礎(chǔ)詞典，就可以完成對該序列的完全恢復(fù)。解碼過程是編碼過程的逆操作?，F(xiàn)在，已知初始詞典的3個(gè)條目如上述，接收端收到的編碼信息為2-2-1-2-3-1-1-3-4-3-1-2T-3-5-3-6,則解碼后的信息串是無向圖G有7個(gè)頂點(diǎn)，若不存在由奇數(shù)條邊構(gòu)成的簡單回路，則它至多有邊。3?記T為一個(gè)隊(duì)列，初始時(shí)為空。現(xiàn)有n個(gè)總和不超過32的正整數(shù)依次入隊(duì)。如果無論這些數(shù)具體為何值，都能找到一種出隊(duì)的方式，使得存在某個(gè)時(shí)刻隊(duì)列T中的數(shù)之和恰好為9,那么n的最小值是 。四、閱讀程序?qū)懡Y(jié)果(共4題，每題7分，共計(jì)28分)1constSIZE=10;vari.jfent,n.m:integer;data:array[1..SIZE]ofinteger;beginreadIn(n.m);fori:=1tondoread(data[i]);fori:=1tondobeginent:=0;forj:=1tondoif(data[i]<data[j])or((data[j]=data[i])and(j<i))thennc(cnt);ifent二mthenwriteIn(data[i]);end;end.輸入：5296-80 1687輸出：2、constSIZE=100;varnafnb.i,j,k:integer;a.b:array[1..SIZE]ofinteger;beginreadln(na);fori:=1tonadoread(a[i]);readIn(nb);fori:=1tonbdoread(b[i]);：=1；j：=1；while(i<=na)and(j<=nb)dobeginifa[i]<=b[j]thenbeginwrite(a[i],'');inc(i);endeIsebeginwrite(b[j],'');inc(j);end;end;ifi<=nathenfork:=itonadowrite(a[k],'');ifj<=nbthenfork:=jtonbdowrite(b[k],'');end.輸入：5357946 10 14輸出：3、constNUM二5;varn:integer;functionr(n:integer):integer;vari:integer;beginifn<=NUMthenbeginr:=n;exit;end;fori:=1toNUMdoifr(n-i)<0thenbeginexit;end;r:二T;end;beginreadIn(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;functionsuccessfuI:booIean;vari:integer;beginfori:=1tondoifnotmap[r[i]][r[imodn+1]]thenbeginsuccessfuI:=false;exit;end;successfuI:=true;end;procedureswap(vara,b:integer);vart:integer;begint:二a; a:二b; b:二t;end;procedureperm(left.right:integer);vari:integer:beginiffoundthenexit;ifIeft>rightthenbeginifsuccessfuIthenbeginfori:=1tondowrite(r[i],'');found:=true;end;exit;end;fori:=lefttorightdobeginswap(r[left],r[i]);perm(left+1,right);swap(r[Ieft],r[i]);end;end;beginreadIn(n.m);fillchar(map,sizeof(map),faIse);fori:=1tomdobeginreadIn(x,y);map[x][y]:=true;map[y][x]:=true;end;fori:=1tondofound:=false;perm(1.n);ifnotfoundthenwriteln('Nosolution!，)；end.輸入：91212TOC\o"1-5"\h\z34561778899輸出：四、完善程序（第1空2分，其余10空，每空2.5分，共計(jì)27分）1、（過河問題）在一個(gè)月黑風(fēng)高的夜晚，有一群人在河的右岸，想通地唯一的一根獨(dú)木橋走到河的左岸。在這伸手不見五指的黑夜里，過橋時(shí)必須借助燈光來照明。不幸的是，他們只有一盞燈。另外，獨(dú)木橋上最多承受兩個(gè)人同時(shí)經(jīng)過，否則就會坍塌。每個(gè)人單獨(dú)過橋都需要一定的時(shí)間，不同的人需要的時(shí)間可能不同。兩個(gè)人一起過橋時(shí)，由于只有一盞燈，所有需要的時(shí)間是較慢的那個(gè)人單獨(dú)過橋時(shí)所花的時(shí)間?，F(xiàn)輸入n（2<=n<100）和這n個(gè)人單獨(dú)過橋時(shí)需要的時(shí)間，請計(jì)算總共最少需要多少時(shí)間，他們才能全部到達(dá)河的左岸。例如，有3個(gè)人甲、乙、丙，他們單獨(dú)過橋的時(shí)間分別為仁2、4,則總共最少需要的時(shí)間為7。具體方法是：甲、乙一起過橋到河的左岸，甲單獨(dú)回到河的右岸并將燈帶回，然后甲、丙再一起過橋到河的左岸，總時(shí)間為2+1+4二7。constSIZE二100;INFINITY=10000;LEFT=true;RIGHT=false;LEFTTORIGHT=true;MV MM JRIGHTTOLEFT=false;n,i:integer:time:array[1??SIZE]ofinteger;pos:array[1??SIZE]ofboolean;functionmax(a,b:integer):integer;beginifa>bthenmax:=aeIsemax:=b;end;functiongo(stage:booIean):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;endeIseif(stage二LEFT_T0_RIGHT)thenbeginans:=INFINITY;fori:=1tondoif③ thenbeginpos[i]:=RIGHT;tmp:二④ ；iftmp<ansthenans:=tmp;⑤ ;end;go:=ans;endeIsego:二0;end;beginreadln(n);fori:=1tondobeginread(time[i]);pos[i]:=RIGHT;end;writein(go(RIGHT_TO_LEFT));end.2、（峰火傳遞）烽火臺又稱烽燧，是重要的軍事防御措施，一般建在險(xiǎn)要處或交通要道上。一旦有敵情發(fā)生，白天燃燒柴草，通過濃煙表達(dá)信息；夜晚燃燒干柴，以火光傳遞軍情。在某兩座城市之間有n個(gè)烽火臺，每個(gè)烽火臺發(fā)出信號都有一定的代價(jià)。為了使情報(bào)準(zhǔn)確地傳遞，在連續(xù)m個(gè)烽火臺中，至少要有一個(gè)發(fā)出信號。現(xiàn)輸入mm和每個(gè)烽火臺發(fā)出信號的代價(jià)，請計(jì)算總共最少花費(fèi)多少代價(jià)，才能使敵軍來襲之時(shí)，情報(bào)能在這兩座城市之間準(zhǔn)確傳遞。例如，有5個(gè)烽火臺，它們發(fā)出信號的代價(jià)依次為仁2、5、6、2,且m為3,則總共最少花費(fèi)的代價(jià)為4,即由第2個(gè)和第5個(gè)烽火臺發(fā)出信號。constSIZE=100;n,m,r,i:integer;value,heap,pos.home,opt:array[1??SIZE]ofinteger;//heapfi]表示用順序數(shù)組存儲的堆heap中第i個(gè)元素的值//pos[i]表示opt[i]在堆heap中的位置，即heap[pos[i]]=opt[i]//home[i]表示heap[i]在序列opt中的位置,即opt[home[i]]=heap[i]procedureswap(i,j:integer)://交換堆中的第i個(gè)和第j個(gè)元素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); //在堆中插入opt[k]vari:integer:begininc(r);heap[r]:=_①pos[k]:=r;②while(i>1)and(heap[i]<heap[idiv2])dobeginswap(i.idiv2);i:=idiv2;end;end;procedureremove(k:integer); //在堆中刪除opt[k]varivj:integer;begini：=pos[k];swap(i,r);dec(r);ifi=r+1thenexit;while(i>1)and(heap[i]<heap[idiv2])dobeginswap(i.idiv2);i:=