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

1、第十四屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題(普及組Pascal語言二小時完成) 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 一、單項(xiàng)選擇題(共 20 題，每題 1.5 分。每題有且僅有一個正確答案。 ) 1微型計(jì)算機(jī)中，控制器的基本功能是()。A. 控制機(jī)器各個部件協(xié)調(diào)工作B.實(shí)現(xiàn)算術(shù)運(yùn)算和邏輯運(yùn)算C.獲取外部信息D.存放程序和數(shù)據(jù)2 .設(shè)A=True, B=False, C=True, D=False,以下邏輯運(yùn)算表達(dá)式值為真的是()。A. (AA B) V (CA A)B. (AA B) V C)ADC. (BV CV D) A DA A D. AA( DVC)A B3 .在下

2、列關(guān)于圖靈獎的說法中，不正確的是()。A 圖靈獎是美國計(jì)算機(jī)協(xié)會于1966年設(shè)立的，專門獎勵那些對計(jì)算機(jī)事業(yè)作出重要貢獻(xiàn)的個人B. 圖靈獎有“計(jì)算機(jī)界諾貝爾獎”之稱C. 迄今為止，還沒有華裔計(jì)算機(jī)科學(xué)家獲此殊榮D. 圖靈獎的名稱取自計(jì)算機(jī)科學(xué)的先驅(qū)、英國科學(xué)家阿蘭圖靈4.計(jì)算機(jī)在工作過程中，若突然停電，( )中的信息不會丟失。A. ROM 和 RAMB. CPUC. ROMD. RAM5.完全二叉樹共有A. N-12*N-1 個結(jié)點(diǎn),則它的葉節(jié)點(diǎn)數(shù)是(B. NC. 2*N)。D. 2N-16.A.在以下各項(xiàng)中,Solaris( )不是操作系統(tǒng)軟件。B. LinuxC. Windows Vist

3、aD. Sybase7.8.A.設(shè)棧S的初始狀態(tài)為空，元素 a, c, a,則棧S的容量至少應(yīng)該是(A. 6B. 5與十進(jìn)制數(shù) 28.5625 相等的四進(jìn)制數(shù)是123.21B. 131.22b，c, d, e, f依次入棧)。S,出棧的序列為b, d, f, e,C.C.）。130.22D. 3D. 130.219.A.設(shè)字符串S=Olympic”，S的非字串的數(shù)目是(28B. 29C.）。16D. 1710. Web2.0 是近年來互聯(lián)網(wǎng)的熱門概念之一， 其核心思想是互動與分享。 下列網(wǎng)站中，( ) 是典型的 Web 2.0 應(yīng)用。A. SinaB. FlickerC. YahooD. Go

4、ogle11遞歸過程或函數(shù)調(diào)用時，處理參數(shù)和返回地址，通常使用一種稱為()的數(shù)據(jù)結(jié)構(gòu)。A.隊(duì)列B.多維數(shù)組C.線性表D.棧12（2008）10+（5B）16 的結(jié)果是（）。C.（4163） 8D . （100001100011 ）2A . （833） 16B . （2089） 1013. 二叉樹T,已知其先根遍歷是 1 2 4 3 5 7 6 (數(shù)字為節(jié)點(diǎn)的編號，下同)，中根遍歷2 4 1 5 7 3 6，則該二叉樹的后根遍歷是()。A. 4 2 5 7 6 3 1B. 4 2 7 5 6 3 1C. 7 4 2 5 6 3 1D. 4 2 7 6 5 3 114. 將數(shù)組 8， 23， 4，

5、 16， 77， -5， 53， 1 00中的元素按從小到大的順序排列，每次可以交 換任意兩個元素，最少需要交換( )次。A. 4B. 5C. 6D. 715. 對有序數(shù)組 5， 13， 19， 21， 37， 56， 64， 75， 88， 92， 100進(jìn)行二分查找，成功查找元素 19 的查找長度(比較次數(shù))是()。A. 1B. 2C. 3D. 416 .面向?qū)ο蟪绦蛟O(shè)計(jì)( Object-Oriented Programming )是一種程序設(shè)計(jì)的方法論，它將對 象作為程序的基本單元， 將數(shù)據(jù)和程序封裝在對象中， 以提高軟件的重用性、 靈活性和擴(kuò)展 性。下面關(guān)于面向?qū)ο笤O(shè)計(jì)的說法中，不正確

6、的是()A. 面向?qū)ο蟪绦蛟O(shè)計(jì)通常采用自頂向下設(shè)計(jì)方法進(jìn)行設(shè)計(jì)。B. 面向?qū)ο蟪绦蛟O(shè)計(jì)方法具有繼承性(inheritanee )、圭寸裝性(encapsulation )、多態(tài)性 (polymorphism )等幾大特點(diǎn)。C. 支持面向?qū)ο筇匦缘恼Z言稱為面向?qū)ο蟮木幊陶Z言，目前較為流行的有 C+, JAVA C#等。D. 面向?qū)ο蟮某绦蛟O(shè)計(jì)的雛形來自于Simula語言，后來在 SmallTalk語言的完善和標(biāo)準(zhǔn)化的過程中得到更多的擴(kuò)展和對以前思想的重新注解。至今，SmallTalk語言仍然被視為面向?qū)ο笳Z言的基礎(chǔ)17. 在 32*32 點(diǎn)陣的“字庫”中,漢字“北”與“京”的字模占用字節(jié)數(shù)之和是

7、()。A. 512B. 256C. 384D. 12818. 設(shè) T 是一棵有 n 個頂點(diǎn)的樹,下列說法不正確的是()。A. T有n條邊B. T是連通的C. T 是無環(huán)的D. T有n-1條邊19下列不屬于 NOIP競賽推薦使用的語言環(huán)境的是()。A. Dev-C+B. Visual C+C. Free PascalD. Lazarus20.在Pascal程序中，表達(dá)式（200 or 10）的值是（）。A. 20B. 1C. 220D. 202二、問題求解(共 2 題,每題 5分,共計(jì) 10 分)1. 書架上有4本不同的書 A、B、C、D。其中A和B是紅皮的，C和D是黑皮的。把這 4 本書擺在書

8、架上，滿足所有黑皮的書都排在一起的擺法有 種。滿足A必須比C靠左，所有紅皮的書要擺在一起，所有黑皮的書要擺放在一起，共有種擺法。2 .有6個城市，任何兩個城市之間都有一條道路連接，6個城市兩兩之間的距離如下表所示，則城市1到城市6的最短距離為 。城市1城市2城市3城市4城市5城市6城市102311215城市22025312城市3 ；320365城市4153079城市51236702城市615125920三、閱讀程序?qū)懡Y(jié)果(共 4題，每題8分，共計(jì)32分)1. VAR i,a,b,c,d:integer;f:array0.3 of in teger;BEGINfor i:=0 to 3 dore

9、ad(fi);a:=f0+f1+f2+f3;a:=a div f0;b:=f0+f2+f3;b:=b div a;c:=(b*f1+a) div f2;d:=f(b div c) mod 4;if (f(a+b+c+d) mod 4f2) the nbegina:=a+b;writel n(a);end elsebeginc:=c+d; write In (c);en d;END.輸入：9 19 29 39輸出：2. procedure foo(a,b,c:integer);beginif ab the n foo(c,a,b) else writel n( a,b,c);en d;vara,

10、b,c:integer;beginread(a,b,c);foo(a,b,c);end.輸入： 3 1 2輸出： 3 typeTT=array0.20of integer;prodecure func(var ary:TT;n:integer);var i,j,x:integer;begini:=0;j:=n-1;while ij do beginwhile (i0) do inc(i);while (ij) and (aryj0) do dec(j);if i epos_f then exit;for i:=spos_m to epos_m doif firstspos_f=midi the

11、n beginroot_m:=i;break;end;solve(first,spos_f+1,spos_f+(root_m-spos_m),mid,spos_m,root_m-1); solve(first,spos_f+(root_m-spos_m)+1,epos_f,mid,root_m+1,epos_m);write(firstspos_f);end;var first,mid:string;len:integer;beginreadln(len);readln(first);readln(mid);solve(first,1,len,mid,1,len);writeln;end.輸入

12、： 7ABDCEGFBDAGECF輸出： 四完善程序(前四空，每空 2.5分，后 6空，每空 3分，共 28 分)1 .(字符串替換) 給定一個字符串 S( S僅包含大小寫字母)，下面的程序?qū)中的每個字母 用規(guī)定的字母替換，并輸出S經(jīng)過替換后的結(jié)果。程序的輸入是兩個字符串，第一個字符串是給定的字符串S,第二個字符串S由26個字母組成，它是az的任一排列，大小寫不定，S規(guī)定了每個字母對應(yīng)的替換字母：S中的第一個字母是字母A和a的替換字母，即S中的A用該字母的大寫替換，S中的a用該字母的小寫替換；S中的第二個字母是字母B和b的替換字母，即S中的B用該字母的大寫替換，S中的b用該字母的小寫替換；以

13、此類推。Var change:string;Str:string;Procedure CheckChangeRule;Var i:integer;Beginfor i:=1 to 26 do beginif thenchangei:=chr(ord(changei)-ord(A)+ord(a);end;end;Procedure ChangeString;Var len,i:integer;beginlen:=length(str);for i:=1 to len do beginif thenbeginstri:=upcase(changeord(stri-ord(A)+1);end;els

14、ebegin end;end;end;beginreadln(str);readln(change);CheckChangeRule; writeln(str);end.n( 1 w n例如序2(找第 k 大的數(shù)) 給定一個長度為 1,000,000 的無序正整數(shù)序列，以及另一個數(shù)w 1000000)，然后以類似快速排序的方法找到序列中第n大的數(shù)(關(guān)于第n大的數(shù):列1， 2， 3， 4， 5， 6中第 3 大的數(shù)是 4。)VARa:array1.1000000 of integer;n,m,ans:integer;Procedure swap(var a,b:integer);var t:in

15、teger;beginif (ab) then begint:=a; a:=b; b:=t;end;end;function FindKth(left,right,n:integer):integer;vartmp,value,i,j:integer;beginif left=right then exit(left);tmp:=random(right-left)+left;swap(atmp,aleft);value:= ;i:=left; j:=right;while ij do beginwhile (ij) and ( ) do dec(j);if ij then beginai:=

16、aj; inc(i);end else break;while (ij) and ( ) do inc(i);if ij then beginaj:=ai; dec(j);end else break;end; if in then begin dec(i); exit( ); end;exit(i);end;var i:integer;beginrandomize;m:=1000000;for i:=1 to m do read(ai);read(n);ans:=FindKth(1,m,n); writeln(aans);end.NOIP2008 年普及組（ Pascal 語言）參考答案與評

17、分標(biāo)準(zhǔn)（修正）一、單項(xiàng)選擇題：（每題1.5 分）1. A2. B3. C4.C5. B6. D7. C8. D9.A10. B11. D12. A13. B14.B15. B16. A17. B18. A19.B20. D二、問題求解：（共 2 題，每題 5 分，共計(jì) 10 分）112 42 7（1-2-5-6）三、閱讀程序?qū)懡Y(jié)果（共 4 題，每題 8 分，共計(jì) 32 分）1. 23 2. 2,3,13. 5 4 10 1 6 22 -59 -6 -11 -64. DBGEFCA （求樹的后序遍歷）四完善程序 （前 4 空，每空 2.5 分，后 6 空，每空 3 分，共 28 分 ） （說明：以下各程序