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

1、第十四屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（ 普及組 Pascal語(yǔ)言 二小時(shí)完成 ）一、單項(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年設(shè)立的，專門獎(jiǎng)勵(lì)那些對(duì)計(jì)算機(jī)事業(yè)作出重要貢獻(xiàn)的個(gè)人B圖靈獎(jiǎng)有“

2、計(jì)算機(jī)界諾貝爾獎(jiǎng)”之稱C迄今為止，還沒(méi)有華裔計(jì)算機(jī)科學(xué)家獲此殊榮D圖靈獎(jiǎ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，d，f，e，c，a，則棧S的容量至少應(yīng)該是（ ）。A6 B5 C4 D38與十進(jìn)制數(shù)2

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

4、100011）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，100進(jìn)行二分查找，成功查找元素19的查找長(zhǎng)度（比較次數(shù)）是（ ）。A1 B2 C3 D

5、416 面向?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ǔ)言稱為面向?qū)ο蟮木幊陶Z(yǔ)言，目前較為流行的有C+，JAVA，C# 等。D面向?qū)ο蟮某绦蛟O(shè)計(jì)的雛形來(lái)自于Simula語(yǔ)言，后來(lái)在SmallTa

6、lk語(yǔ)言的完善和標(biāo)準(zhǔn)化的過(guò)程中得到更多的擴(kuò)展和 1對(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在Pascal程序中，表達(dá)式（200 or 10）的值是（ ）。A20 B1 C220 D202二

7、、問(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城市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 0 7 9城市5 12 3 6 7 0 2城市6 15 12

8、5 9 2 0三、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計(jì)32分）if a>b then foo(c,a,b) 1VAR i,a,b,c,d:integer;f:array0.3 of integer; else writeln(a,',',b,',',c);BEGIN end;for i:=0 to 3 do varread(fi); a,b,c:integer;a:=f0+f1+f2+f3; begina:=a div f0; read(a,b,c);b:=f0+f2+f3; foo(a,b,c);b:=b div a; end.c:=(b*f1+a)

9、div f2; 輸入：3 1 2d:=f(b div c) mod 4; 輸出：_if (f(a+b+c+d) mod 4>f2) then 3type TT=array0.20of integer;begin prodecure func(var ary:TT;n:integer);a:=a+b; var i,j,x:integer;writeln(a); beginend else i:=0;j:=n-1;begin while i<j do beginc:=c+d; while (i<j) and (ary>0) do inc(i);writeln(c); whi

10、le (i<j) and (aryj<0) do dec(j);end; if i<j then begin x:=ary;END. ary:=aryj;aryj:=x; 輸入：9 19 29 39inc(i); 輸出：_dec(j); 2procedure foo(a,b,c:integer);begin end;end; if firstspos_f=midi then beginend; root_m:=i;var break;a:TT; end;i,m:integer; solve(first,spos_f+1,spos_f+(root_m-spos_m),mid,s

11、pos_m,robegin ot_m-1);m:=10; solve(first,spos_f+(root_m-spos_m)+1,epos_f,mid,root_m+1for i:=0 to m-1 do ,epos_m);read(a); write(firstspos_f);func(a,m); end;for i:=1 to m-1 do var first,mid:string;write(a,' '); len:integer;writeln; beginend. readln(len);readln(first); 輸入：5 4 -6 -11 6 -59 22 -

12、6 1 10輸出：_ readln(mid);solve(first,1,len,mid,1,len);writeln; 4proceduresolve(first:string;spos_f,epos_f:integer;mid:string;spos_m,epend.os_m:integer); 輸入：7var i,root_m:integer; ABDCEGFbegin BDAGECFif spos_f > epos_f then exit; 輸出：_ for i:=spos_m to epos_m do四完善程序（前四空，每空2.5分，后6空，每空3分，共28分）1（字符串替換）

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

14、eger;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

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

16、egin for i:=1 to m do read(ai);if (a<>b) then begin read(n);t:=a; a:=b; b:=t; ans:=FindKth(1,m,n);end; writeln(aans); 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 beginwhile (i<j) and