第十二屆全國青少年信息學(xué)奧林匹克聯(lián)賽提高組初賽試題(全面版)資料

1、第十二屆全國青少年信息學(xué)奧林 匹克聯(lián)賽提高組初賽試題（全面 版）資料第十二屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（ 提高組 Pascal 語言 二小時完 成）由 OIFans 整理收集 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 1D. ALUE.）上一個ROI芯片上的程D. 內(nèi)存條E. 硬單A.控制器B.運算器C.寄存器項RAM選在以擇題BIOS （基本輸入輸出系統(tǒng)）是一組固化在計算機(jī)內(nèi)（各序。（°，不是CP的組成部分。（ A. 控制器B. CPUC. 主板共盤A. 沃爾夫獎題下，D. 圖靈獎B. 諾貝爾獎E. 南丁格爾獎C. 菲爾茲獎4題世界1在頂. 編級5的程 獎分時

2、項，(中5共使，計用為 任計1算一5機(jī)種 科分高學(xué)A. 沒有區(qū)別忽略不計C. 按行讀的方式要高于數(shù)組的存儲方式。B. 有一些區(qū)別，但機(jī)器處理速度很快，可D. 按列讀的方式要高一些E. 取決在 Pascal 語言中，表達(dá)式A. 441B. 42(21 xor 2) 的值是(C.23D.24E.25A. not a=0 or not b=0b=0) D. (a<>0)or(b<>0)B. not(a=0)a nd(b=0)E. (a<>0)a nd (b<>0)C. not(a=0 andA. 1,2, 3, 4, 57, 6B. 1,2, 4, 5

3、, 7C. 1,4, 3,車 D. 1,4, 3, 7, 2站呈E. 1,4, 3, 7, 5狹高度為n的均衡的二叉樹是指：如果去掉葉結(jié)點及相應(yīng)的樹枝，它應(yīng)該是高度為n-1的滿二叉樹。A. 101A. 3352.53350.5D. 3350.1151B. 11C. 12D. 13B.C. 3352.1161E.前4個答案都不對E. 210 的 臺0. 最序。將5個數(shù)的序列排序，不論原先的順序如何，最少都可以通過（）次比較，完成從小到大的1EA. 6B. 7C. 8.設(shè)A=B=D=true C=E=false，以下邏輯運算表達(dá)式值為真的有(A. (AA B) V(CAD)VE B.(A AB)

4、VC) A DA E)12. A. (8234) 10B. (202A) 162D. (2042) 16(203.設(shè)棧S的初始狀態(tài)為空，元素a, b, c, d, e依次入棧，以下出棧序列不可能出現(xiàn)的有（）。21 A. a, b, c, e, d)1 C. a, e, c, b, d6B. b, c, a, e, dD. d, c, e, b, a1+4.( A. 3 2 1 4 6 53已 C. 2 3 1 5 4 6)知8B. 3 2 1 5 4 6D. 2 3 1 4 6 516的5結(jié)個 A. ACCESS是結(jié)點在（ C. Oracle的下二列1。叉各6樹數(shù).的據(jù) A. gcc/g+先庫

5、在根 C. Turbo C遍統(tǒng)列1各軟歷7. 以下斷電之后將不能保存數(shù)據(jù)的有（是A.硬盤B. ROM中件1，中B. SQL ServerD. FoxproB. Turbo PascalD. free pascal)。C. 顯存D. RAM1以，8. 在下列關(guān)于計算機(jī)語言的說法中，正確的有（）2關(guān)屬系A(chǔ). Pascal和C都是編譯執(zhí)行的高級語言系于3型數(shù)據(jù)庫為B. 高級語言程序比匯編語言程序更容易從一種計算機(jī)移植到另一種計算機(jī)上C. C+是歷史上的第一個支持面向?qū)ο蟮挠嬎銠C(jī)語言D. 高級語言比匯編語言更高級，是因為它的程序的運行效率更高19. 在下列關(guān)于計算機(jī)算法的說法中，正確的有（）。A. 一

6、個正確的算法至少要有一個輸入C. 判斷一個算法的好壞，主要依據(jù)它在某臺計算機(jī)上具體實現(xiàn)時的運行時間D. 目前仍然存在許多涉及到國計民生的重大課題，還沒有找到能夠在計算機(jī)上實施的有效算法20. 在下列關(guān)于青少年信息學(xué)競賽的說法中，你贊成的是（）（本題不回答為0分,答題一律滿分）。A. 舉行信息學(xué)競賽的目的，是為了帶動廣大青少年學(xué)科學(xué)、愛科學(xué)，為造就一大批優(yōu)秀的計算機(jī)科 學(xué)與技術(shù)人才奠定良好的基礎(chǔ)B. 如果競賽優(yōu)勝者不能直接保送上大學(xué)，我今后就不再參與這項活動了C. 準(zhǔn)備競賽無非要靠題海戰(zhàn)術(shù)，為了取得好成績，就得拼時間、拼體力D. 為了取得好成績，不光要看智力因素，還要看非智力因素。優(yōu)秀選手應(yīng)該有

7、堅韌不拔的意志，有 嚴(yán)謹(jǐn)求實的作風(fēng)，既要努力奮進(jìn)，又要勝不驕敗不餒三問題求解（共2題，每題5分，共計10分）1將2006個人分成若干不相交的子集，每個子集至少有3個人，并且：（1）在每個子集中，沒有人認(rèn)識該子集的所有人。（2）同一子集的任何3個人中，至少有 2個人互不認(rèn)識。（3）對同一子集中任何2個不相識的人，在該子集中恰好只有1個人認(rèn)識這兩個人。則滿足上述 條件的子集最多能有個？2. 將邊長為n的正三角形每邊n等分，過每個分點分別做另外兩邊的平行線，得到若干個正三角形, 我們稱為小三角形。正三角形的一條通路是一條連續(xù)的折線，起點是最上面的一個小三角形，終點是 最下面一行位于中間的小三角形。在

8、通路中，只允許由一個小三角形走到另一個與其有公共邊的且位 于同四閱讀程序?qū)懡Y(jié)果(共4題，每題 8分，共計 32分)1. Program ex401;varu,v:array0.3 of in teger;i,x,y:i nteger;beginx:=10; y:=10;for i:=0 to 3 do read(ui);v0：=(u0+u1+u2+u3) div 7; v1:=u0 div (u1-u2) div u3);v2:=u0*u1 div u2*u3; v3:=v0*v1;x:=(v0+v1+2)-u(v3+3) mod 4;if (x>10) thenelsey:=y+20+

9、(v2*100-v3) div (uv0 mod 3*5);writel n (x,',',y);end. *注：本例中，給定的輸入數(shù)據(jù)可以避免分母為0或下標(biāo)越界。)輸入：9 3 9 4輸出：2.Program ex402;con stm:array0.4 of integer=(2,3,5,7,13);var i,j:i nteger; t: longint; beg infor i:=0 to 4 do begi nt:=1;for j:=1 to mi-1 dot:=t*2;t:=(t*2-1)*t; write (t,' '); en d;writel

10、n;en d.輸出:3. Program ex403;Co nstNN=7; TypeArr1=array0.30 of char;var s:arr1;k,p:i nteger;fun cti on fun 1(s:arr1; a:char; n:i nteger):i nteger;var j:integer; beginj:=n;while (a<sj)a nd(j>0) do dec(j);fun 1:=j;end;Function fun2(s:arr1; a:char; n:integer):integer;var j:integer; beginj：=1；while

11、(a>sj)a nd(j< n) do in c(j);fun 2:=j;en d;beginfor k:=1 to NN do sk:=chr(ord('A')+2*k+1);k:=fu n1(s,'M',NN)+fu n2(s,'M',NN);writel n( k);en d.輸出：4. program ex404;procedure digit (n, m:l ongin t);var n 2:i nteger;beginif(m>0) the n begi nn 2:=n mod 10;write( n2:2);if(

12、m>1) the ndigit (n div 10,m div 10);n2:=n mod 10; write(n2:2); end;en d;beginwrite In (' In put a nu mber:');readl n( x);x2:=1;while(x2<x) do x2:=x2*10;x2:=x2 div 10; digit(x,x2); write In;en d.輸入：9734526輸出：五.完善程序（前5空，每空2分，后6空，每空 3分，共28分）(選排 12 132123 32列31程序：下面 Program ex501; Var i,n,

13、k:integer;程 a:array1.1O of in teger;序coun t:l ongint;的 功Procedure perm2(j:i nteger);臺匕冃匕是 var i,p,t:i nteger;利用 begin遞ifthen歸方begi n法for i:=k to n do beg in in c(co un t);t:=ak; ak:=ai; ai:=t;fordowrite(ap:1);write(' ');t:=ak;ak:=ai;ai:=t;if (count mod 5=0) then writeln;end; exit; end;for i:

14、=j to n do begin ;t:=aj; ;end end; beginwriteln('Entry n,k (k<=n):'); read(n,k);count:=0;for i:=1 to n do ai:=i; ;end.(TSR可題的交叉算子)TSP可題(TravelingSalesman Problem)描述如下：給定n個城 市，構(gòu)成一個宀完全法任 何之兩一城是市圖 遺傳算法是求解該可題的一個很有效的近似算法。在該算法中，一個個體為一條環(huán)路，其編碼方(1) 選定中間一段作為互換段，該段的起止下標(biāo)為t1 , t2，隨機(jī)生成t1 , t2后，互換兩段。(2)

15、 互換后，在每個新的排列中可能有重復(fù)數(shù)字，因而不能作為新個體的編碼，一般再做兩步處理：(2.1) 將兩個互換段中，共同的數(shù)字標(biāo)記為 0，表示已處理完。(2.2) 將兩個互換段中其余數(shù)字標(biāo)記為 1 ，按順序?qū)⒒Q段外重復(fù)的數(shù)字進(jìn)行替換。 例如：莒n=12,兩個個體分別是：間都到有a2: 3 2 1 12 * 6 7 10 11 * 8 5 4 9t1=5，t2=8 。上述每一行中，兩個星號間的部分為互換段。假定數(shù)組的下標(biāo)從 1開始，互換后有：a1: 1 3 5 4 * 6 7 10 11 * 10 12 8 11a2: 3 2 1 12 * 2 6 7 9 * 8 5 4 9然后，將數(shù)字 6,7

16、 對應(yīng)的項標(biāo)記為 0，星號內(nèi)數(shù)字 2,9,10,11 對應(yīng)的項標(biāo)記為 1 ，并且按順序 對 應(yīng)關(guān)系為:10<->2 ，11<->9。于是，將 a19=10 替換為 a19=2 ，將 a22=2 替換為 a22=10 ， 類 似再做第 2組替換。這樣處理后，就得到了兩個新個體：a1: 1 3 5 4 6 7 10 11 2 12 8 9a2: 3 10 1 12 2 6 7 9 8 5 4 11(3) 輸出兩個新個體的編碼。 程序：program ex502;type arr1=array1.20 of integer;var a1,a2,kz1,kz2:arr1; n,

17、k,t1,t2:integer;function rand1(k:integer):integer;var t:integer;begin t:=0;while (t<2) or(t>k) do t:=random(k+1)-2; rand1:=t;end;procedure read1(var a:arr1;m:integer);讀入數(shù)組元素 a1 至am，a0=0 ，略。procedure wrt1(var a:arr1;m:integer);輸出數(shù)組元素a1至 am，略。var i,j,t,kj:integer; beginfor i:=t1 to t2 do begint:

18、=a1i;end;for i:=1 to n doif (i<t1)or(i>t2) then begin kz1i:=-1;kz2i:=-1;end elsebegin ; end;for i:=t1 to t2 do for j:=t1 to t2 doif(a1i=a2j) thenend;begin ; break;for i:=t1 to t2 do if(kz1i=1) then beginfor j:=t1 to t2 do if(kz2j=1) thenbegin kj:=j; break; end;for j:=1 to n do if thenbegin a1j:=a2kj;break; end;for j:=1 to n do if thenbegin a2j:=a1i; break; end;kz1i:=0;kz2kj:=0;end; end; beginwriteln('input (n>5