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

2、項，(中5共使，計用為 任計1算一5機種 科分高學A. 沒有區別忽略不計C. 按行讀的方式要高于數組的存儲方式。B. 有一些區別，但機器處理速度很快，可D. 按列讀的方式要高一些E. 取決在 Pascal 語言中，表達式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的均衡的二叉樹是指：如果去掉葉結點及相應的樹枝，它應該是高度為n-1的滿二叉樹。A. 101A. 3352.53350.5D. 3350.1151B. 11C. 12D. 13B.C. 3352.1161E.前4個答案都不對E. 210 的 臺0. 最序。將5個數的序列排序，不論原先的順序如何，最少都可以通過（）次比較，完成從小到大的1EA. 6B. 7C. 8.設A=B=D=true C=E=false，以下邏輯運算表達式值為真的有(A. (AA B) V(CAD)VE B.(A AB)

4、VC) A DA E)12. A. (8234) 10B. (202A) 162D. (2042) 16(203.設棧S的初始狀態為空，元素a, b, c, d, e依次入棧，以下出棧序列不可能出現的有（）。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結個 A. ACCESS是結點在（ C. Oracle的下二列1。叉各6樹數.的據 A. gcc/g+先庫

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

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

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

8、通路中，只允許由一個小三角形走到另一個與其有公共邊的且位 于同四閱讀程序寫結果(共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. *注：本例中，給定的輸入數據可以避免分母為0或下標越界。)輸入：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個城 市，構成一個宀完全法任 何之兩一城是市圖 遺傳算法是求解該可題的一個很有效的近似算法。在該算法中，一個個體為一條環路，其編碼方(1) 選定中間一段作為互換段，該段的起止下標為t1 , t2，隨機生成t1 , t2后，互換兩段。(2)

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

16、 對應的項標記為 0，星號內數字 2,9,10,11 對應的項標記為 1 ，并且按順序 對 應關系為: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);讀入數組元素 a1 至am，a0=0 ，略。procedure wrt1(var a:arr1;m:integer);輸出數組元素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