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

1、第十四屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（普及組Pasca語言二小時完成） 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效一、單項(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 DVA）B. （AA B） V C）ADC. （BVCV D） ADA AD. AA （DVC） AB3在下列關(guān)于圖靈獎的說法中

2、，不正確的是（） 。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完全二叉樹共有2*N-1 個結(jié)點(diǎn)，則它的葉節(jié)點(diǎn)數(shù)是（） 。A N-1B NC 2*ND 2N-16在以下各項(xiàng)中，（A Solaris）不是操作系統(tǒng)軟件。B LinuxC Windows VistaD Sybase7.設(shè)棧S的初始狀態(tài)為空，元素a

3、, b, c, d, e, f依次入棧S,出棧的序列為b, d, f, e,c, a,則棧S的容量至少應(yīng)該是（）。A 6B 5C 4D 38與十進(jìn)制數(shù)28.5625 相等的四進(jìn)制數(shù)是（） 。D 130.21A 123.21B 131.22C 130.229 .設(shè)字符串S="Olympic”, S的非字串的數(shù)目是（）。A 28B 29C 16D 1710 Web2.0 是近年來互聯(lián)網(wǎng)的熱門概念之一，其核心思想是互動與分享。下列網(wǎng)站中，（）是典型的Web 2.0 應(yīng)用。A SinaB FlickerC YahooD Google11遞歸過程或函數(shù)調(diào)用時，處理參數(shù)和返回地址，通常使用一種稱

4、為（）的數(shù)據(jù)結(jié)構(gòu)。A.隊(duì)列B.多維數(shù)組C.線性表D.棧12 . （2008）io+（5B）i6 的結(jié)果是（）。A （833）16B （2089）10C （4163）8D（ 100001100011 ） 213 .二叉樹T,已知其先根遍歷是 1 2 4 3 5 7 6 （數(shù)字為節(jié)點(diǎn)的編號，下同），中根遍歷2 4 15 7 3 6，則該二叉樹的后根遍歷是（） 。A 4 2 5 7 6 3 1 B 4 2 7 5 6 3 1 C 7 4 2 5 6 3 1 D 4 2 7 6 5 3 114將數(shù)組8， 23， 4， 16， 77， -5， 53， 100中的元素按從小到大的順序排列，每次可以交換任意

5、兩個元素，最少需要交換（）次。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ì)的說法中，不正確的是（）A.面向?qū)ο蟪绦蛟O(shè)計(jì)通常采用自頂向下設(shè)計(jì)方法進(jìn)行設(shè)計(jì)。B.面向?qū)ο蟪绦蛟O(shè)計(jì)方法具有繼承性（ inheritance）、封裝性（encap

6、sulation）、多態(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ù)之和是（A 512B 256C 384D 128D. T有n-1條邊D LazarusD 202C和D是黑皮的。把這 4_種。滿足A必須比C靠18 設(shè)T 是一棵有n

7、個頂點(diǎn)的樹，下列說法不正確的是（） 。A. T有n條邊B. T是連通的C. T是無環(huán)的19 .下列不屬于 NOIP競賽推薦使用的語言環(huán)境的是（）。A Dev-C+B Visual C+C Free Pascal20 .在Pascal程序中，表達(dá)式（200 or 10）的值是（）。A 20B 1C 220二、問題求解（共2 題，每題5 分，共計(jì)10 分）1 .書架上有4本不同的書 A、B、C、Do其中A和B是紅皮的, 本書擺在書架上，滿足所有黑皮的書都排在一起的擺法有左，所有紅皮的書要擺在一起，所有黑皮的書要擺放在一起，共有 種擺法。2.有6個城市，任何兩個城市之間都有一條道路連接，6個城市兩兩

8、之間的距離如下表所示，則城市1到城市6的最短距離為 。城市1 W 2W 3城市4城市5城市6城市102311215城市22025312城市3320365城市4153079城市51236702城市615125920三、閱讀程序?qū)懡Y(jié)果(共 4題，每題8分，共計(jì)32分) 1. VAR i,a,b,c,d:integer;f:array0.3 of integer; BEGIN for i:=0 to 3 do read(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)

9、 mod 4; if (f(a+b+c+d) mod 4>f2) then begin a:=a+b; writeln(a);end else begin c:=c+d; writeln(c);end; END.輸入：9 19 29 39輸出：2 procedure foo(a,b,c:integer); beginif a>b then foo(c,a,b) else writeln(a,',',b,',',c);end;vara,b,c:integer;beginread(a,b,c);foo(a,b,c);end.輸入： 3 1 2輸出： 3

10、type TT=array0.20of integer;prodecure func(var ary:TT;n:integer);var i,j,x:integer;begini:=0;j:=n-1;while i<j do beginwhile (i<j) and (ary>0) do inc(i);while (i<j) and (aryj<0) do dec(j);if i<j then begin x:=ary;ary:=aryj;aryj:=x;inc(i);dec(j);end;end;end;vara:TT;i,m:integer;beginm

11、:=10;for i:=0 to m-1 doread(a);func(a,m);for i:=1 to m-1 dowrite(a,' ');writeln;end.輸入： 5 4 -6 -11 6 -59 22 -6 1 10輸出： 4 procedure solve(first:string;spos_f,epos_f:integer;mid:string;spos_m,epos_m:integer); var i,root_m:integer;beginif spos_f > epos_f then exit;for i:=spos_m to epos_m doi

12、f firstspos_f=midi then begin root_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; begin readln(len); readln(first); readln(mid); solve(first,1

13、,len,mid,1,len); writeln; end.輸入： 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用該字母的小寫

14、替換； S'中的第二個字母是字母 B和b的 替換字母，即S中的B用該字母的大寫替換， S中的b用該字母的小寫替換；以此類推。Var change:string;Str:string;Procedure CheckChangeRule;Var i:integer; Begin for i:=1 to 26 do begin if thenchangei:=chr(ord(changei)-ord('A')+ord('a');end;end;Procedure ChangeString;Var len,i:integer;beginlen:=length(s

15、tr);for i:=1 to len do beginif thenbeginstri:=upcase(changeord(stri-ord('A')+1);end;elsebegin end;end;end;beginreadln(str);readln(change);CheckChangeRule; writeln(str);end.2 .(找第k大的數(shù))給定一個長度為1,000,000的無序正整數(shù)序列，以及另一個數(shù) n (1<n w 1000000),然后以類似快速排序的方法找到序列中第n大的數(shù)(關(guān)于第n大的數(shù)：例如序列 1 ， 2， 3， 4， 5， 6中第

16、3 大的數(shù)是4。 )VAR a:array1.1000000 of integer;n,m,ans:integer;Procedure swap(var a,b:integer);var t:integer;beginif (a<>b) 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

17、(atmp,aleft);value:= ;i:=left; j:=right;while i<j do beginwhile (i<j) and ( ) do dec(j);if i<j then beginai:=aj; inc(i);end else break;while (i<j) and ( ) do inc(i);if i<j then beginaj:=ai; dec(j);end else break;end; if i<n then begin inc(i); exit(FindKth( ); end;if i>n then beg

18、in 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 語言）參考答案與評分標(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 分）1 12 42 7(1->2->5->6)三、閱讀程序?qū)懡Y(jié)果(共4 題，每題8 分，共計(jì)32 分)1. 232. 2,3,13. 5 4 10 1 6 22 -59 -6 -11 -64. DBGEFCA (求樹的后序遍歷)四完善程序(前4 空，每空2.5 分，后 6 空，每空3 分，共 28 分 )(說明：以下各程序填空可能還有一些等價的寫法，各省可請本省專家審定和上機(jī)驗(yàn)證，不一定上報(bào)科學(xué)委員會審查)1.(changei >= 'A') and (changei <= 'Z&