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

1、第十四屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（ 普及組 Pascal語(yǔ)言 二小時(shí)完成 ） 全部試題答案均要求寫(xiě)在答卷紙上，寫(xiě)在試卷紙上一律無(wú)效 一、單項(xiàng)選擇題（共20題，每題1.5分。每題有且僅有一個(gè)正確答案。）1微型計(jì)算機(jī)中，控制器的基本功能是（ ）。 A控制機(jī)器各個(gè)部件協(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(AB)(CDA) B(AB) C)DC(BCD) DA DA（DC）B3在下列關(guān)于圖靈獎(jiǎng)的說(shuō)法中，不正確的是（ ）。 A圖靈獎(jiǎng)是美國(guó)計(jì)算機(jī)協(xié)會(huì)于1966

2、年設(shè)立的，專(zhuān)門(mén)獎(jiǎng)勵(lì)那些對(duì)計(jì)算機(jī)事業(yè)作出重要貢獻(xiàn)的個(gè)人B圖靈獎(jiǎng)有“計(jì)算機(jī)界諾貝爾獎(jiǎng)”之稱(chēng) C迄今為止，還沒(méi)有華裔計(jì)算機(jī)科學(xué)家獲此殊榮 D圖靈獎(jiǎng)的名稱(chēng)取自計(jì)算機(jī)科學(xué)的先驅(qū)、英國(guó)科學(xué)家阿蘭·圖靈4計(jì)算機(jī)在工作過(guò)程中，若突然停電，（ ）中的信息不會(huì)丟失。 AROM 和 RAM BCPU CROM DRAM5完全二叉樹(shù)共有2*N-1個(gè)結(jié)點(diǎn)，則它的葉節(jié)點(diǎn)數(shù)是（ ）。 AN-1 BN C2*N D2N-16在以下各項(xiàng)中，( ）不是操作系統(tǒng)軟件。 ASolaris BLinux CWindows Vista DSybase7設(shè)棧S的初始狀態(tài)為空，元素a，b，c，d，e，f依次入棧S，出棧的序列為b，

3、d，f，e，c，a，則棧S的容量至少應(yīng)該是（ ）。A6 B5 C4 D38與十進(jìn)制數(shù)28.5625相等的四進(jìn)制數(shù)是（ ）。A123.21 B131.22 C130.22 D130.219設(shè)字符串S=”O(jiān)lympic”，S的非字串的數(shù)目是（ ）。A28 B29 C16 D1710Web2.0 是近年來(lái)互聯(lián)網(wǎng)的熱門(mén)概念之一，其核心思想是互動(dòng)與分享。下列網(wǎng)站中，（ ）是典型的Web 2.0應(yīng)用。ASina BFlicker CYahoo DGoogle11遞歸過(guò)程或函數(shù)調(diào)用時(shí)，處理參數(shù)和返回地址，通常使用一種稱(chēng)為（ ）的數(shù)據(jù)結(jié)構(gòu)。A隊(duì)列 B多維數(shù)組 C線性表 D棧12(2008)10+(5B)16的

4、結(jié)果是（ ）。A（833）16 B（2089）10 C（4163）8 D（100001100011）213二叉樹(shù)T，已知其先根遍歷是1 2 4 3 5 7 6（數(shù)字為節(jié)點(diǎn)的編號(hào)，下同），中根遍歷2 4 1 5 7 3 6，則該二叉樹(shù)的后根遍歷是（ ）。A4 2 5 7 6 3 1 B4 2 7 5 6 3 1 C7 4 2 5 6 3 1 D4 2 7 6 5 3 114將數(shù)組8，23，4，16，77，-5，53，100中的元素按從小到大的順序排列，每次可以交換任意兩個(gè)元素，最少需要交換（ ）次。A4 B5 C6 D715對(duì)有序數(shù)組 5，13，19，21，37，56，64，75，88，92，1

5、00進(jìn)行二分查找，成功查找元素19的查找長(zhǎng)度（比較次數(shù)）是（ ）。A1 B2 C3 D416 面向?qū)ο蟪绦蛟O(shè)計(jì)（Object-Oriented Programming）是一種程序設(shè)計(jì)的方法論，它將對(duì)象作為程序的基本單元，將數(shù)據(jù)和程序封裝在對(duì)象中，以提高軟件的重用性、靈活性和擴(kuò)展性。下面關(guān)于面向?qū)ο笤O(shè)計(jì)的說(shuō)法中，不正確的是（ ) A面向?qū)ο蟪绦蛟O(shè)計(jì)通常采用自頂向下設(shè)計(jì)方法進(jìn)行設(shè)計(jì)。 B面向?qū)ο蟪绦蛟O(shè)計(jì)方法具有繼承性（inheritance）、封裝性（encapsulation）、多態(tài)性 (polymorphism）等幾大特點(diǎn)。 C支持面向?qū)ο筇匦缘恼Z(yǔ)言稱(chēng)為面向?qū)ο蟮木幊陶Z(yǔ)言，目前較為流行的有C+

6、，JAVA，C# 等。D面向?qū)ο蟮某绦蛟O(shè)計(jì)的雛形來(lái)自于Simula語(yǔ)言，后來(lái)在SmallTalk語(yǔ)言的完善和標(biāo)準(zhǔn)化的過(guò)程中得到更多的擴(kuò)展和對(duì)以前思想的重新注解。至今，SmallTalk語(yǔ)言仍然被視為面向?qū)ο笳Z(yǔ)言的基礎(chǔ)17在32*32點(diǎn)陣的“字庫(kù)”中，漢字“北”與“京”的字模占用字節(jié)數(shù)之和是（ ）。A512 B256 C384 D12818設(shè)T是一棵有n個(gè)頂點(diǎn)的樹(shù)，下列說(shuō)法不正確的是（ ）。AT有n條邊 BT是連通的 CT是無(wú)環(huán)的 DT有n-1條邊19下列不屬于NOIP競(jìng)賽推薦使用的語(yǔ)言環(huán)境的是（ ）。ADev-C+ BVisual C+ CFree Pascal DLazarus20在Pasc

7、al程序中，表達(dá)式（200 or 10）的值是（ ）。A20 B1 C220 D202二、問(wèn)題求解（共2題，每題5分，共計(jì)10分）1書(shū)架上有4本不同的書(shū)A、B、C、D。其中A和B是紅皮的，C和D是黑皮的。把這4本書(shū)擺在書(shū)架上，滿足所有黑皮的書(shū)都排在一起的擺法有_種。滿足A必須比C靠左，所有紅皮的書(shū)要擺在一起，所有黑皮的書(shū)要擺放在一起，共有_種擺法。2有6個(gè)城市，任何兩個(gè)城市之間都有一條道路連接，6個(gè)城市兩兩之間的距離如下表所示，則城市1到城市6的最短距離為_(kāi)。城市1城市2城市3城市4城市5城市6城市102311215城市22025312城市3320365城市4153079城市51236702城

8、市615125920三、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計(jì)32分）1VARi,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) 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);

9、 end;END.輸入：9 19 29 39輸出：_2procedure foo(a,b,c:integer);begin if a>b then foo(c,a,b) else writeln(a,',',b,',',c);end;var a,b,c:integer;begin read(a,b,c); foo(a,b,c);end.輸入：3 1 2輸出：_3type TT=array0.20of integer;prodecure func(var ary:TT;n:integer); var i,j,x:integer; begin i:=0;j:=

10、n-1; while i<j do begin while (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;var a:TT; i,m:integer;begin m:=10; for i:=0 to m-1 do read(a); func(a,m); for i:=1 to m-1 do write(a,' '

11、); writeln;end.輸入：5 4 -6 -11 6 -59 22 -6 1 10輸出：_4procedure solve(first:string;spos_f,epos_f:integer;mid:string;spos_m,epos_m:integer);var i,root_m:integer;begin if spos_f > epos_f then exit; for i:=spos_m to epos_m do if firstspos_f=midi then begin root_m:=i; break; end;solve(first,spos_f+1,spos

12、_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,len,mid,1,len); writeln;end.輸入：7 ABDCEGF BDAGECF輸出：_四完善程序（前四空，每空2.5分，后6空，每空3分

13、，共28分）1（字符串替換）給定一個(gè)字符串S（S僅包含大小寫(xiě)字母），下面的程序?qū)中的每個(gè)字母用規(guī)定的字母替換，并輸出S經(jīng)過(guò)替換后的結(jié)果。程序的輸入是兩個(gè)字符串，第一個(gè)字符串是給定的字符串S，第二個(gè)字符串S由26個(gè)字母組成，它是az的任一排列，大小寫(xiě)不定，S規(guī)定了每個(gè)字母對(duì)應(yīng)的替換字母：S中的第一個(gè)字母是字母A和a的替換字母，即 S中的A用該字母的大寫(xiě)替換，S中的a用該字母的小寫(xiě)替換；S中的第二個(gè)字母是字母B 和b的替換字母，即S中的B用該字母的大寫(xiě)替換，S中的b用該字母的小寫(xiě)替換； 以此類(lèi)推。Var change:string;Str:string;Procedure CheckChange

14、Rule;Var i:integer;Begin for i:=1 to 26 do begin if _ then changei:=chr(ord(changei)-ord('A')+ord('a'); end; end;Procedure ChangeString;Var len,i:integer;begin len:=length(str); for i:=1 to len do begin if _ then begin stri:=upcase(changeord(stri-ord('A')+1); end; else begin

15、_ end; end;end;begin readln(str); readln(change); CheckChangeRule; _ writeln(str);end.2（找第k大的數(shù)）給定一個(gè)長(zhǎng)度為1,000,000的無(wú)序正整數(shù)序列，以及另一個(gè)數(shù)n（1n1000000），然后以類(lèi)似快速排序的方法找到序列中第n大的數(shù)（關(guān)于第n大的數(shù)：例如序列1，2，3，4，5，6中第3大的數(shù)是4。）VAR a:array1.1000000 of integer; n,m,ans:integer;Procedure swap(var a,b:integer);var t:integer;begin if (

16、a<>b) then begin t:=a; a:=b; b:=t; end;end;function FindKth(left,right,n:integer):integer;var tmp,value,i,j:integer;begin if left=right then exit(left); tmp:=random(right-left)+left; swap(atmp,aleft); value:=_; i:=left; j:=right; while i<j do begin while (i<j) and (_) do dec(j); if i<

17、j then begin ai:=aj; inc(i); end else break; while (i<j) and (_) do inc(i); if i<j then begin aj:=ai; dec(j); end else break; end; _ if i<n then begin inc(i); exit(FindKth(_); end; if i>n then begin dec(i); exit(_); end; exit(i);end;var i:integer;begin randomize; m:=1000000; for i:=1 to

18、m do read(ai); read(n); ans:=FindKth(1,m,n); writeln(aans);end.NOIP2008年普及組（Pascal語(yǔ)言）參考答案與評(píng)分標(biāo)準(zhǔn)（修正）一、單項(xiàng)選擇題：（每題1.5分） 1. A 2. B 3. C 4. C 5. B6. D 7. C 8. D 9. A 10. B11. D 12. A 13. B 14. B 15. B 16. A 17. B 18. A 19. B 20. D二、問(wèn)題求解：（共2題，每題5分，共計(jì)10分）112 4 27(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 （求樹(shù)的后序遍歷）四完善程序 (前4空，每空2.5分，后6空，每空3分，共28分) （說(shuō)明：以下各程序填空可能還有一些等價(jià)的寫(xiě)法，各省可請(qǐng)本省專(zhuān)家審定和上機(jī)驗(yàn)證，不一定上報(bào)科學(xué)委員會(huì)審查）1. (changei >= 'A') and (changei <= 'Z