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

1、第十二屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽提高組試題（Pascal ） 一、 單項(xiàng)選擇題 （共 10 題，每題 1.5 分，共計(jì) 15 分.）。 1. 以下各項(xiàng)中不是CPU組成部分: A. 控制器 B. 運(yùn)算器 C. 寄存器 D. ALU E. RAM 2. BIOS(基本輸入輸出系統(tǒng))是一組固化在計(jì)算機(jī)內(nèi)（ ）上一個(gè) ROM 芯片上的程序。 A. 控制器 B. CPU C. 主板 D. 內(nèi)存條 E. 硬盤 3.在下面各世界頂級(jí)的獎(jiǎng)項(xiàng)中，為計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域作出杰出貢獻(xiàn)的科學(xué)家設(shè)立的獎(jiǎng)項(xiàng)是（ ）。 A. 沃爾夫獎(jiǎng) B. 諾貝爾獎(jiǎng) C. 菲爾茲獎(jiǎng) D. 圖靈獎(jiǎng) E. 南丁格爾獎(jiǎng) 4在編程時(shí)（使用

2、任一種高級(jí)語言，不一定是 Pascal），如果需要從磁盤文件中輸入一個(gè)很大的二維 數(shù)組（例如 1000*1000 的 double 型數(shù)組），按行讀（即外層循環(huán)是關(guān)于行的）與按列讀（即外層循 環(huán)是關(guān)于列的）相比，在輸入效率上（）。 A. 沒有區(qū)別 B. 有一些區(qū)別，但機(jī)器處理速度很快，可忽略不計(jì) C. 按行讀的方式要高一些 D. 按列讀的方式要高一些 E. 取決于數(shù)組的存儲(chǔ)方式。 5在 Pascal 語言中，表達(dá)式 (21 xor 2)的值是（ ） A. 441 B. 42 C.23 D.24 E.25 6(此題取消)在 Pascal 語言中，判斷 a 不等于 0 且 b 不等于 0 的正確的

3、條件表達(dá)式是（ ） A. not a=0 or not b=0 B. not(a=0)and(b=0) C. not(a=0 and b=0) D. (a0)or(b0) E. (a0)and (b0) 7某個(gè)車站呈狹長形，寬度只能容下一臺(tái)車，并且只有一個(gè)出入口。已知某時(shí)刻該車站狀態(tài)為空，從這一時(shí)刻開始的出入記錄為：“進(jìn)，出，進(jìn)，進(jìn)，進(jìn)，出，出，進(jìn)，進(jìn)，進(jìn)，出,出”。假設(shè)車輛入站的 順序?yàn)?1，2，3，則車輛出站的順序?yàn)椋?）。 A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 4, 3, 7, 6 D. 1, 4, 3, 7, 2 E. 1, 4, 3, 7,

4、5 8高度為 n 的均衡的二叉樹是指：如果去掉葉結(jié)點(diǎn)及相應(yīng)的樹枝，它應(yīng)該是高度為 n-1 的滿二叉樹。在這里，樹高等于葉結(jié)點(diǎn)的最大深度，根結(jié)點(diǎn)的深度為 0，如果某個(gè)均衡的二叉樹共有 2381 個(gè)結(jié)點(diǎn)， 則該樹的樹高為（ ）。 A. 10 B. 11 C. 12 D. 13 E. 210 1 9. 與十進(jìn)制數(shù) 1770.625 對(duì)應(yīng)的八進(jìn)制數(shù)是（ ）。由OIF收集 A. 3352.5 B. 3350.5 C. 3352.1161 D. 3350.1151 E. 前 4 個(gè)答案都不對(duì) 10將 5 個(gè)數(shù)的序列排序，不論原先的順序如何，最少都可以通過（）次比較，完成從小到大的排序。 A. 6 B. 7

5、 C. 8 D. 9 E. 10 二、 不定項(xiàng)選擇題（共 10 題，每題 1.5 分，共計(jì) 15 分。多選少選均不得分）。 11. 設(shè)A=B=D=true，C=E=false，以下邏輯運(yùn)算表達(dá)式值為真的有（ ）。 AB)(CD) A. ( E B.(AB)C)DE) C. A(BCDE) D. (A(BC) DE 12. (2010)16 + (32)8的結(jié)果是（ ）。 A. (8234)10 B. (202A)16 C. (100000000110)2 D. (2042)16 13. 設(shè)棧S的初始狀態(tài)為空，元素a, b, c, d, e 依次入棧，以下出棧序列不可能出現(xiàn)的有（ ）。 A. a

6、, b, c, e, d B. b, c, a, e, d C. a, e, c, b, d D. d, c, e, b, a 14. 已知 6 個(gè)結(jié)點(diǎn)的二叉樹的先根遍歷是 1 2 3 4 5 6（數(shù)字為結(jié)點(diǎn)的編號(hào)，以下同），后根遍歷是 3 2 5 6 4 1，則該二叉樹的可能的中根遍歷是（ ）由OIF收集 A. 3 2 1 4 6 5 B. 3 2 1 5 4 6 C. 2 3 1 5 4 6 D. 2 3 1 4 6 5 15. 在下列各數(shù)據(jù)庫系統(tǒng)軟件中，以關(guān)系型數(shù)據(jù)庫為主體結(jié)構(gòu)的是（ ）。 A. ACCESS B. SQL Server C. Oracle D. Foxpro 16.在下

7、列各軟件中，屬于 NOIP 競賽（復(fù)賽）推薦使用的語言環(huán)境有（ ）。 A. gcc/g+ B. Turbo Pascal C. Turbo C D. free pascal 17. 以下斷電之后將不能保存數(shù)據(jù)的有（ ）。 A. 硬盤 B. ROM C. 顯存 D. RAM 18. 在下列關(guān)于計(jì)算機(jī)語言的說法中，正確的有（ ）。 A. Pascal和C都是編譯執(zhí)行的高級(jí)語言 ;B. 高級(jí)語言程序比匯編語言程序更容易從一種計(jì)算機(jī)移植到另一種計(jì)算機(jī)上 ;C. C+是歷史上的第一個(gè)支持面向?qū)ο蟮挠?jì)算機(jī)語言 ; D. 高級(jí)語言比匯編語言更高級(jí)，是因?yàn)樗某绦虻倪\(yùn)行效率更高 19. 在下列關(guān)于計(jì)算機(jī)算法的

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

9、戰(zhàn)術(shù)，為了取得好成績，就得拼時(shí)間、拼體力 D. 為了取得好成績，不光要看智力因素，還要看非智力因素。優(yōu)秀選手應(yīng)該有堅(jiān)韌不拔的意志，有嚴(yán)謹(jǐn)求實(shí)的作風(fēng)，既要努力奮進(jìn)，又要?jiǎng)俨或湐〔火H 三問題求解（共 2 題，每題 5 分，共計(jì) 10 分） 1將 2006 個(gè)人分成若干不相交的子集，每個(gè)子集至少有 3 個(gè)人，并且： （1）在每個(gè)子集中，沒有人認(rèn)識(shí)該子集的所有人。 （2）同一子集的任何 3 個(gè)人中，至少有 2 個(gè)人互不認(rèn)識(shí)。 （3）對(duì)同一子集中任何 2 個(gè)不相識(shí)的人，在該子集中恰好只有 1 個(gè)人認(rèn)識(shí)這兩個(gè)人。 則滿足上述條件的子集最多能有 個(gè)？ 2將邊長為 n 的正三角形每邊 n 等分，過每個(gè)分點(diǎn)分別

10、做另外兩邊的平行線，得到若干個(gè)正三角形，我們稱為小三角形。正三角形的一條通路是一條連續(xù)的折線，起點(diǎn)是最上面的一個(gè)小三角形，終點(diǎn)是最 下面一行位于中間的小三角形。在通路中，只允許由一個(gè)小三角形走到另一個(gè)與其有公共邊的且位于同一行或下一行的小三角形，并且每個(gè)小三角形不能經(jīng)過兩次或兩次以上（圖中是 n=5 時(shí)一條通路的例 子）。設(shè) n=10，則該正三角形的不同的通路的總數(shù)為_ _。 一、單項(xiàng)選擇題1. E 2. C 3. D 4. E 5. C 6. （滿分） 7. C 8. B 9. A 10. B 二、不定項(xiàng)選擇題：（每題1.5分） 11. ABC 12. AB 13. C 14. BC 15.

11、 ABCD 16. AD 17. CD 18.AB 19. BD 20. （滿分，空白0分） 三、問題求解：（每題 5分） 1. 401 2. 9! （或362880） 四、閱讀程序?qū)懡Y(jié)果 1. -13，57 （對(duì)1個(gè)數(shù)給4分，無逗號(hào)扣1分） 2. 6 28 496 8128 33550336 （前2個(gè)對(duì)1個(gè)數(shù)給1分，后3個(gè)對(duì)1個(gè)數(shù)給2分） 3. 11 4. 6 2 5 4 3 7 9 9 7 3 4 5 2 6（數(shù)字之間無空格扣2分）四閱讀程序?qū)懡Y(jié)果（共 4 題，每題 8 分，共計(jì) 32 分） 1. Program ex401; var u,v:array0.3 of integer; i,

12、x,y:integer; begin x:=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 (x10) then y:=y+(v2*100-v3) div (uu0 mod 3*5)由OIF收集 else y:=y+20+(v2*100-v3) div (uv0 mod 3*5); writeln (x,y); end. *注：本例中，給

13、定的輸入數(shù)據(jù)可以避免分母為 0 或下標(biāo)越界。 輸入：9 3 9 4 輸出： 還有3題未列入1. E 2. C 3. D 4. E 5. C 6. （滿分） 7. C 8. B 9. A 10. B11. ABC 12. AB 13. C 14. BC 15. ABCD 16. AD 17. CD 18.AB 19. BD 20.（滿分，空白0分）三1. 401 2. 9! （或362880）五完善程序 (前 5 空，每空 2 分，后 6 空，每空 3 分，共 28 分) 1（選排列）下面程序的功能是利用遞歸方法生成從 1 到 n(n10)的 n 個(gè)數(shù)中取 k(1=ksj)and(jfun2:=

14、j; end; begin for k:=1 to NN do sk:=chr(ord(A)+2*k+1); k:=fun1(s,M,NN)+fun2(s,M,NN); writeln(k); end. 輸出： 4. program ex404; var x,x2:longint;由OIF收集 procedure digit(n,m:longint); var n2:integer; begin if(m0) then begin n2:=n mod 10; write(n2:2); if(m1) then digit(n div 10,m div 10); n2:=n mod 10; wri

15、te(n2:2); end; end; begin writeln(Input a number:); readln(x); x2:=1; while(x2x2:=x2 div 10; digit(x,x2); writeln; end. 輸入：9734526 輸出： 五完善程序 (前 5 空，每空 2 分，后 6 空，每空 3 分，共 28 分) 1（選排列）下面程序的功能是利用遞歸方法生成從 1 到 n(n10)的 n 個(gè)數(shù)中取 k(1=k=n)個(gè)數(shù)的 全部可能的排列（不一定按升序輸出）。例如，當(dāng) n=3，k=2 時(shí)，應(yīng)該輸出（每行輸出 5 個(gè)排列）： 12 13 21 23 32 31

16、程序： Program ex501; Var i,n,k:integer; a:array1.10 of integer; count:longint; Procedure perm2(j:integer); var i,p,t:integer; begin if then begin for i:=k to n do begin inc(count); t:=ak; ak:=ai; ai:=t; for do write(ap:1); write( ); t:=ak;ak:=ai;ai:=t; if (count mod 5=0) then writeln; end; exit; end;

17、for i:=j to n do begin t:=aj;aj:=ai;ai:=t;由OIF收集 ; t:=aj; ; end end; begin writeln(Entry n,k (k4-2-1-5-3。遺傳算法的核心是通過兩個(gè)個(gè)體的交叉操作，產(chǎn)生兩 個(gè)新的個(gè)體。下面的程序給出了最簡單的一種交叉算法。具體過程如下： (1)選定中間一段作為互換段，該段的起止下標(biāo)為 t1，t2，隨機(jī)生成 t1，t2 后，互換兩段。 (2)互換后，在每個(gè)新的排列中可能有重復(fù)數(shù)字，因而不能作為新個(gè)體的編碼，一般再做兩步處理： (2.1) 將兩個(gè)互換段中，共同的數(shù)字標(biāo)記為 0，表示已處理完。 (2.2) 將兩個(gè)互

18、換段中其余數(shù)字標(biāo)記為 1，按順序?qū)⒒Q段外重復(fù)的數(shù)字進(jìn)行替換。例如：n=12，兩個(gè)個(gè)體分別是：a1: 1 3 5 4 * 2 6 7 9 * 10 12 8 11 a2: 3 2 1 12 * 6 7 10 11 * 8 5 4 9 t1=5，t2=8。上述每一行中，兩個(gè)星號(hào)間的部分為互換段。假定數(shù)組的下標(biāo)從 1 開始，互換后有： a1: 1 3 5 4 * 6 7 10 11 * 10 12 8 11 a2: 3 2 1 12 * 2 6 7 9 * 8 5 4 9 然后，將數(shù)字 6,7 對(duì)應(yīng)的項(xiàng)標(biāo)記為 0，星號(hào)內(nèi)數(shù)字 2,9,10,11 對(duì)應(yīng)的項(xiàng)標(biāo)記為 1，并且按順序?qū)?應(yīng)關(guān)系為:102，

19、119。于是，將 a19=10 替換為 a19=2，將 a22=2 替換為 a22=10， 類似再做第 2 組替換。這樣處理后，就得到了兩個(gè)新個(gè)體： a1: 1 3 5 4 6 7 10 11 2 12 8 9 a2: 3 10 1 12 2 6 7 9 8 5 4 11 （3）輸出兩個(gè)新個(gè)體的編碼。 程序： program ex502; type arr1=array1.20 of integer; var a1,a2,kz1,kz2:arr1; n,k,t1,t2:integer; function rand1(k:integer):integer; var t:integer; begi

20、n t:=0; while (tk) 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，略。 procedure cross(var a1,a2:arr1;t1, t2,n:integer);由OIF收集 var i,j,t,kj:integer; begin for i:=t1 to t2 do begin t:=a1i; ; end; for i

21、:=1 to n do if (it2) then begin kz1i:=-1;kz2i:=-1; end else begin ; end; for i:=t1 to t2 do for j:=t1 to t2 do if(a1i=a2j) then begin ; break; end; for i:=t1 to t2 do if(kz1i=1) then begin for j:=t1 to t2 do if(kz2j=1) then begin kj:=j; break; end; for j:=1 to n do if then begin a1j:=a2kj;break; end

22、; for j:=1 to n do if then begin a2j:=a1i; break; end; kz1i:=0;kz2kj:=0; end; end; begin writeln(input (n5):); readln(n); writeln(input array 1:); read1(a1,n); writeln(input array 2:); read1(a2,n); t1:=rand1(n-1); repeat t2:=rand1(n-1); until(t1t2); if(t1t2) then begin k:=t1; t1:=t2; t2:=k; end; ; w

23、rt1(a1,n); wrt1(a2,n); end. * 提高組（C語言）參考答案與評(píng)分標(biāo)準(zhǔn) 一、單項(xiàng)選擇題：（每題1.5分） 1. E 2. C 3. D 4. E 5. C 6. （滿分） 7. C 8. B 9. A 10. B 二、不定項(xiàng)選擇題：（每題1.5分） 11. ABC 12. AB 13. C 14. BC 15. ABCD 16. AD 17. CD 18.AB 19. BD 20.（滿分，空白0分） 三、問題求解：（每題 5分） 1. 401 2. 9! （或362880） 四、閱讀程序?qū)懡Y(jié)果 1. -13，57 （對(duì)1個(gè)數(shù)給4分，無逗號(hào)扣1分） 2. 6 28 496

24、 8128 33550336 （前2個(gè)對(duì)1個(gè)數(shù)給1分，后3個(gè)對(duì)1個(gè)數(shù)給2分） 3. 11 4. 6 2 5 4 3 7 9 9 7 3 4 5 2 6（數(shù)字之間無空格扣2分） 五、完善程序(前5空，每空2分，后6空，每空3分) 1 j=k （或k=j） p=1;p=k;p+ perm2(j+1) aj=ai;ai=t perm2(1) 2 a1i=a2i;a2i=t kz1i=kz2i=1 kz1i=kz2j=0 a1j=a1i & kz1j=-1 a2j=a2kj & kz2j=-1 cross(a1,a2,t1,t2,n) * 提高組（C+）參考答案與評(píng)分標(biāo)準(zhǔn) 一、單項(xiàng)選擇題：（每題1.5

25、分） 1. E 2. C 3. D 4. E 5. C 6. （滿分） 7. C 8. B 9. A 10. B 二、不定項(xiàng)選擇題：（每題1.5分） 11. ABC 12. AB 13. C 14. BC 15. ABCD 16. AD 17. CD 18.AB 19. BD 20.（滿分，空白0分） 三、問題求解：（每題 5分） 1. 401 2. 9! （或362880） 四、閱讀程序?qū)懡Y(jié)果 1. -13，57 （對(duì)1個(gè)數(shù)給4分，無逗號(hào)扣1分） 2. 6 28 496 8128 33550336 （前2個(gè)對(duì)1個(gè)數(shù)給1分，后3個(gè)對(duì)1個(gè)數(shù)給2分） 3. 11 4. 6 2 5 4 3 7 9

26、9 7 3 4 5 2 6（數(shù)字之間無空格扣2分） 五、完善程序(前5空，每空2分，后6空，每空3分) 1 j=k （或k=j） p=1;p=k;p+ perm2(j+1) aj=ai;ai=t perm2(1) 2 a1i=a2i;a2i=t kz1i=kz2i=1 kz1i=kz2j=0 a1j=a1i & kz1j=-1 a2j=a2kj & kz2j=-1 cross(a1,a2,t1,t2,n) * 第十二屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題答案2006提高組（Pascal語言）參考答案與評(píng)分標(biāo)準(zhǔn)一、單項(xiàng)選擇題：（每題1.5分） 1. E 2. C 3. D 4. E 5. C 6. （滿分） 7. C 8. B 9. A 10. B 二、不定項(xiàng)選擇題：（每題1.5分） 11. ABC 12. AB 13. C 14. BC 15. ABCD 16. AD 17. CD 18.AB 19. BD 20. （滿分，空白0分）