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

1、第十四屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（ 普及組 Pascal語言 二小時完成 ） 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 一、單項選擇題（共20題，每題1.5分。每題有且僅有一個正確答案。）1微型計算機(jī)中，控制器的基本功能是（ ）。A控制機(jī)器各個部件協(xié)調(diào)工作 B實現(xiàn)算術(shù)運算和邏輯運算C獲取外部信息 D存放程序和數(shù)據(jù)2設(shè)A=True，B=False，C=True，D=False，以下邏輯運算表達(dá)式值為真的是（ ）。 A(AB)(CDB) C)A) B(ADC(BCD) DA DAB （DC）3在下列關(guān)于圖靈獎的說法中，不正確的是（ ）。A圖靈獎是美國計算機(jī)協(xié)會于1966年設(shè)

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

3、的容量至少應(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 是近年來互聯(lián)網(wǎng)的熱門概念之一，其核心思想是互動與分享。下列網(wǎng)站中，（ ）是典型的Web 2.0應(yīng)用。ASina BFlicker CYahoo DGoogle11遞歸過程或函數(shù)調(diào)用時，處理參數(shù)和返回地址，通常使用一種稱為（ ）的數(shù)據(jù)結(jié)構(gòu)。 A隊列 B多維數(shù)組 C線性表 D棧12(2008)10+(5B)16的結(jié)果是（ ）。A（833

4、）16 B（2089）10 C（4163）8 D（100001100011）213二叉樹T，已知其先根遍歷是1 2 4 3 5 7 6（數(shù)字為節(jié)點的編號，下同），中根遍歷2 4 1 5 7 3 6，則該二叉樹的后根遍歷是（ ）。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中的元素按從小到大的順序排列，每次可以交換任意兩個元素，最少需要交換（ ）次。A4 B5 C6 D715對有序數(shù)組 5，13，19，21，37，56，64，75，88，92，100進(jìn)行二分查找，成功查

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

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

7、or 10）的值是（ ）。A20 B1 C220 D202二、問題求解（共2題，每題5分，共計10分）1書架上有4本不同的書A、B、C、D。其中A和B是紅皮的，C和D是黑皮的。把這4本書擺在書架上，滿足所有黑皮的書都排在一起的擺法有_種。滿足A必須比C靠左，所有紅皮的書要擺在一起，所有黑皮的書要擺放在一起，共有_種擺法。26個城市兩兩之間的距離如下表所示，有6個城市，任何兩個城市之間都有一條道路連接，則城市1到城市6的最短距離為_。 城市1 城市2 城市3 城市4 城市5 城市6城市1 0 2 3 1 12 15城市2 2 0 2 5 3 12城市3 3 2 0 3 6 5城市4 1 5 3

8、0 7 9城市5 12 3 6 7 0 2城市6 15 12 5 9 2 0三、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計32分） 1VAR i,a,b,c,d:integer;f:array0.3 of integer;BEGINfor i:=0 to 3 doread(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) thenbegina:=a+b;writeln(a);end elsebeginc:=c

9、+d;writeln(c);end;END.輸入：9 19 29 39輸出：_2procedure 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輸出：_3type TT=array0.20of integer; prodecure func(var ary:TT;n:integer); var i,j,x:integer;begin

10、i:=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:=10;for i:=0 to m-1 doread(a);func(a,m);for i:=1 to m-1 dowrite(a,' ');write

11、ln;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;beginif spos_f > epos_f then exit;for i:=spos_m to epos_m doif firstspos_f=midi then beginroot_m:=i;break;end;solve(first,spos_f+1,spos_f+(root_m-s

12、pos_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.輸入：7ABDCEGFBDAGECF輸出：_四完善程序（前四空，每空2.5分，后6空，每空3分，共28分）1（字符串替換）給定一個

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

14、;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;elsebegin_end;end;end;beginreadln(str);re

15、adln(change);CheckChangeRule;_writeln(str);end.2（找第k大的數(shù)）給定一個長度為1,000,000的無序正整數(shù)序列，以及另一個數(shù)n（1n1000000），然后以類似快速排序的方法找到序列中第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;beginif (a<>b) then begint:=a; a:=b; b:=t;en

16、d;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 beginwhile (i<j) and (_) do dec(j);if i<j then beginai:=aj; inc(i);end else break;while (i

17、<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 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.NO

18、IP2008年普及組（Pascal語言）參考答案與評分標(biāo)準(zhǔn)一、單項選擇題：（每題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. B16. A 17. B 18. A 19. B 20. D二、問題求解：（共2題，每題5分，共計10分）112 427(1->2->5->6)三、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計32分）1. 232. 2,3,13. 5 4 10 1 6 22 -59 -6 -11 -64. DBGEFCA （求樹的后序遍歷）四完善程序 (前4空，每空2.5分，后6空，每空3分，共28分)（說明：以下各程序填空可能還有一些等價的寫法，各省可請本省專家審定和上機(jī)驗證，不一定上報科學(xué)委員會審查）1. (changei >= 'A') and (changei <= 'Z')