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

1、第十四屆全國青少年信息學奧林匹克聯(lián)賽初賽試題（ 普及組 Pascal語言 二小時完成 ）一、單項選擇題（共20題，每題1.5分。每題有且僅有一個正確答案。）1微型計算機中，控制器的基本功能是（ ）。A控制機器各個部件協(xié)調(diào)工作 B實現(xiàn)算術運算和邏輯運算C獲取外部信息 D存放程序和數(shù)據(jù)2設A=True，B=False，C=True，D=False，以下邏輯運算表達式值為真的是（ ）。A(AB)(CDA) B(AB) C)DC(BCD) DA DA（DC）B3在下列關于圖靈獎的說法中，不正確的是（ ）。A圖靈獎是美國計算機協(xié)會于1966年設立的，專門獎勵那些對計算機事業(yè)作出重要貢獻的個人B圖靈獎有“

2、計算機界諾貝爾獎”之稱C迄今為止，還沒有華裔計算機科學家獲此殊榮D圖靈獎的名稱取自計算機科學的先驅(qū)、英國科學家阿蘭圖靈4計算機在工作過程中，若突然停電，（ ）中的信息不會丟失。AROM 和 RAM BCPU CROM DRAM5完全二叉樹共有2*N-1個結點，則它的葉節(jié)點數(shù)是（ ）。AN-1 BN C2*N D2N-16在以下各項中，( ）不是操作系統(tǒng)軟件。ASolaris BLinux CWindows Vista DSybase7設棧S的初始狀態(tài)為空，元素a，b，c，d，e，f依次入棧S，出棧的序列為b，d，f，e，c，a，則棧S的容量至少應該是（ ）。A6 B5 C4 D38與十進制數(shù)2

3、8.5625相等的四進制數(shù)是（ ）。A123.21 B131.22 C130.22 D130.219設字符串S=”O(jiān)lympic”，S的非字串的數(shù)目是（ ）。A28 B29 C16 D1710Web2.0 是近年來互聯(lián)網(wǎng)的熱門概念之一，其核心思想是互動與分享。下列網(wǎng)站中，（ ）是典型的Web 2.0應用。ASina BFlicker CYahoo DGoogle11遞歸過程或函數(shù)調(diào)用時，處理參數(shù)和返回地址，通常使用一種稱為（ ）的數(shù)據(jù)結構。A隊列 B多維數(shù)組 C線性表 D棧12(2008)10+(5B)16的結果是（ ）。A（833）16 B（2089）10 C（4163）8 D（100001

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

5、416 面向?qū)ο蟪绦蛟O計（Object-Oriented Programming）是一種程序設計的方法論，它將對象作為程序的基本單元，將數(shù)據(jù)和程序封裝在對象中，以提高軟件的重用性、靈活性和擴展性。下面關于面向?qū)ο笤O計的說法中，不正確的是（ )A面向?qū)ο蟪绦蛟O計通常采用自頂向下設計方法進行設計。B面向?qū)ο蟪绦蛟O計方法具有繼承性（inheritance）、封裝性（encapsulation）、多態(tài)性 (polymorphism）等幾大特點。C支持面向?qū)ο筇匦缘恼Z言稱為面向?qū)ο蟮木幊陶Z言，目前較為流行的有C+，JAVA，C# 等。D面向?qū)ο蟮某绦蛟O計的雛形來自于Simula語言，后來在SmallTa

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

7、、問題求解（共2題，每題5分，共計10分）1書架上有4本不同的書A、B、C、D。其中A和B是紅皮的，C和D是黑皮的。把這4本書擺在書架上，滿足所有黑皮的書都排在一起的擺法有_種。滿足A必須比C靠左，所有紅皮的書要擺在一起，所有黑皮的書要擺放在一起，共有_種擺法。2有6個城市，任何兩個城市之間都有一條道路連接，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 0 7 9城市5 12 3 6 7 0 2城市6 15 12

8、5 9 2 0三、閱讀程序?qū)懡Y果（共4題，每題8分，共計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、給定一個字符串S（S僅包含大小寫字母），下面的程序?qū)中的每個字母用規(guī)定的字母替換，并輸出S經(jīng)過替換后的結果。程序的輸入是兩個字符串，第一個字符串是給定的字符串S，第二個字符串S由26個字母組成，它是az的任一排列，大小寫不定，S規(guī)定了每個字母對應的替換字母：S中的第一個字母是字母A和a的替換字母，即 S中的A用該字母的大寫替換，S中的a用該字母的小寫替換；S中的第二個字母是字母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ù)）給定一個長度為1,000,000的無序正整數(shù)序列，以及另一個數(shù)n（1n1000000），然后以類似快速排序的方法找到序列中第n大的數(shù)（關于第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