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

1、第十三屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（ 普及組 Pascal 語言 二小時(shí)完成） 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 一、 單項(xiàng)選擇題（共20題，每題1.5分，共計(jì)30分。每題有且僅有一個(gè)正確答案。）1 在以下各項(xiàng)中，（ ）不是CPU的組成部分。A控制器 B運(yùn)算器 C寄存器 D主板2在關(guān)系數(shù)據(jù)庫中，存放在數(shù)據(jù)庫中的數(shù)據(jù)的邏輯結(jié)構(gòu)以（ ）為主。A二叉樹 B多叉樹 C哈希表 D二維表3在下列各項(xiàng)中，只有（ ）不是計(jì)算機(jī)存儲(chǔ)容量的常用單位。AByte BKB CUB DTB4ASCII碼的含義是（ ）。A二十進(jìn)制轉(zhuǎn)換碼 B美國信息交換標(biāo)準(zhǔn)代碼 C數(shù)字的二進(jìn)制編碼 D計(jì)算機(jī)可

2、處理字符的唯一編碼5一個(gè)完整的計(jì)算機(jī)系統(tǒng)應(yīng)包括（ ）。A系統(tǒng)硬件和系統(tǒng)軟件 B硬件系統(tǒng)和軟件系統(tǒng) C主機(jī)和外部設(shè)備 D主機(jī)、鍵盤、顯示器和輔助存儲(chǔ)器6IT的含義是（ ）。A通信技術(shù) B信息技術(shù) C網(wǎng)絡(luò)技術(shù) D信息學(xué)7LAN的含義是（ ）。A因特網(wǎng) B局域網(wǎng) C廣域網(wǎng) D城域網(wǎng)8冗余數(shù)據(jù)是指可以由其它數(shù)據(jù)導(dǎo)出的數(shù)據(jù)。例如，數(shù)據(jù)庫中已存放了學(xué)生的數(shù)學(xué)、語文和英語的三科成績(jī)，如果還存放三科成績(jī)的總分，則總分就可以看作冗余數(shù)據(jù)。冗余數(shù)據(jù)往往會(huì)造成數(shù)據(jù)的不一致。例如，上面4個(gè)數(shù)據(jù)如果都是輸入的，由于操作錯(cuò)誤使總分不等于三科成績(jī)之和，就會(huì)產(chǎn)生矛盾。下面關(guān)于冗余數(shù)據(jù)的說法中，正確的是（ ）。A應(yīng)該在數(shù)據(jù)庫中

3、消除一切冗余數(shù)據(jù)B用高級(jí)語言編寫的數(shù)據(jù)處理系統(tǒng)，通常比用關(guān)系數(shù)據(jù)庫編寫的系統(tǒng)更容易消除冗余數(shù)據(jù)C為了提高查詢效率，在數(shù)據(jù)庫中可以保留一些冗余數(shù)據(jù)，但更新時(shí)要做相容性檢驗(yàn)D做相容性檢驗(yàn)會(huì)降低效率，可以不理睬數(shù)據(jù)庫中的冗余數(shù)據(jù)9在下列各軟件，不屬于NOIP競(jìng)賽（復(fù)賽）推薦使用的語言環(huán)境有（ ）。Agcc Bg+ CTurbo C DFree Pascal10以下斷電后仍能保存數(shù)據(jù)的有（ ）。A硬盤 B高速緩存 C顯存 DRAM11在下列關(guān)于計(jì)算機(jī)語言的說法中，正確的有（ ）。A高級(jí)語言比匯編語言更高級(jí)，是因?yàn)樗某绦虻倪\(yùn)行效率更高B隨著Pascal、C等高級(jí)語言的出現(xiàn)，機(jī)器語言和匯編語言已經(jīng)退出了

4、歷史舞臺(tái)C高級(jí)語言比匯編語言程序更容易從一種計(jì)算機(jī)上移植到另一種計(jì)算機(jī)上DC是一種面向?qū)ο蟮母呒?jí)計(jì)算機(jī)語言12近20年來，許多計(jì)算機(jī)專家都大力推崇遞歸算法，認(rèn)為它是解決較復(fù)雜問題的強(qiáng)有力的工具。在下列關(guān)于遞歸算法的說法中，正確的是（ ）。A在1977年前后形成標(biāo)準(zhǔn)的計(jì)算機(jī)高級(jí)語言“FORTRAN77”禁止在程序使用遞歸，原因之一是該方法可能會(huì)占用更多的內(nèi)存空間B和非遞歸算法相比，解決同一個(gè)問題，遞歸算法一般運(yùn)行得更快一些C對(duì)于較復(fù)雜的問題，用遞歸方式編程一般比非遞歸方式更難一些D對(duì)于已經(jīng)定義好的標(biāo)準(zhǔn)數(shù)學(xué)函數(shù) sin(x)，應(yīng)用程序中的語句“y=sin(sin(x);”就是一種遞歸調(diào)用13一個(gè)無

5、法靠自身的控制終止的循環(huán)成為“死循環(huán)”，例如，在C語言程序中，語句“while(1) printf(“*”);”就是一個(gè)死循環(huán)，運(yùn)行時(shí)它將無休止地打印*號(hào)。下面關(guān)于死循環(huán)的說法中，只有（ ）是正確的。A不存在一種算法，對(duì)任何一個(gè)程序及相應(yīng)的輸入數(shù)據(jù)，都可以判斷是否會(huì)出現(xiàn)死循環(huán)，因而，任何編譯系統(tǒng)都不做死循環(huán)檢查B有些編譯系統(tǒng)可以檢測(cè)出死循環(huán)C死循環(huán)屬于語法錯(cuò)誤，既然編譯系統(tǒng)能檢查各種語法錯(cuò)誤，當(dāng)然也應(yīng)該能檢查出死循環(huán)D死循環(huán)與多進(jìn)程中出現(xiàn)的“死鎖”差不多，而死鎖是可以檢測(cè)的，因而，死循環(huán)也可以檢測(cè)的14在Pascal語言中，表達(dá)式 （23 or 2 xor 5）的值是（ ）。A18 B1 C2

6、3 D3215在Pascal語言中，判斷整數(shù)a等于0或b等于0或c等于0的正確的條件表達(dá)式是（ ）。Anot (a<>0) or (b<>0) or (c<>0)Bnot (a<>0) and (b<>0) and (c<>0)Cnot (a=0) and (b=0) or (c<>0)D(a=0) and (b=0) and (c=0)16地面上有標(biāo)號(hào)為A、B、C的三根柱，在A柱上放有10個(gè)直徑相同中間有孔的圓盤，從上到下依次編號(hào)為1，2，3，將A柱上的部分盤子經(jīng)過B柱移入C柱，也可以在B柱上暫存。如果B柱上

7、的操作記錄為“進(jìn)、進(jìn)、出、進(jìn)、進(jìn)、出、出、進(jìn)、進(jìn)、出、進(jìn)、出、出”。那么，在C柱上，從下到上的編號(hào)為（ ）。A2 4 3 6 5 7 B2 4 1 2 5 7 C2 4 3 1 7 6 D2 4 3 6 7 517與十進(jìn)制數(shù)1770對(duì)應(yīng)的八進(jìn)制數(shù)是（ ）。A3350 B3351 C3352 D354018設(shè)A=B=True，C=D=False，以下邏輯運(yùn)算表達(dá)式值為假的有（ ）。A(AB)(CDA) B(AB)C)D) CA(BCD)D D(A(DC)B19(2070)16 + (34)8 的結(jié)果是（ ）。A（8332）10 B（208A）16 C（100000000110）2 D(20212

8、)820已知7個(gè)節(jié)點(diǎn)的二叉樹的先根遍歷是1 2 4 5 6 3 7（數(shù)字為節(jié)點(diǎn)的編號(hào)，以下同），中根遍歷是4 2 6 5 1 7 3，則該二叉樹的后根遍歷是（ ）。A4 6 5 2 7 3 1 B4 6 5 2 1 3 7 C4 2 3 1 5 4 7 D4 6 5 3 1 7 2二、問題求解（共2題，每題5分，共計(jì)10分）。1、（子集劃分）將n個(gè)數(shù)（1，2，n）劃分成r個(gè)子集。每個(gè)數(shù)都恰好屬于一個(gè)子集，任何兩個(gè)不同的子集沒有共同的數(shù)，也沒有空集。將不同劃分方法的總數(shù)記為S(n,r)。例如，S(4,2)=7，這7種不同的劃分方法依次為(1),(234)，(2),(134)，(3),(124)，

9、(4),(123)，(12),(34)，(13),(24)，(14),(23)。當(dāng)n=6，r=3時(shí)，S(6,3)=_。（提示：先固定一個(gè)數(shù)，對(duì)于其余的5個(gè)數(shù)考慮S(5,3)與S(5,2)，再分這兩種情況對(duì)原固定的數(shù)進(jìn)行分析。）B2、（最短路線）某城市的街道是一個(gè)很規(guī)整的矩形網(wǎng)絡(luò)（見下圖），有7條南北向的縱街，5條東西向的橫街?，F(xiàn)要從西南角的A走到東北角的B，最短的走法共有多少種？_ A三、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計(jì)32分。）1、program j301;var i,a,b,c,x,y:integer; p:array0.4 of integer;begin y:=20; for i

10、:=0 to 4 do read(p); readln; a:=(p0+p1)+(p2+p3+p4) div 7; b:=p0+p1 div (p2+p3) div p4); c:=p0*p1 div p2; x:=a+b-p(p3+3) mod 4; if (x>10) then y:=y+(b*100-a) div (pp4 mod 3*5) else y:=y+20+(b*100-c) div (pp4 mod 3*5); writeln(x,',',y);end.注：本例中，給定的輸入數(shù)據(jù)可以避免分母為0或數(shù)組元素下表越界。輸入：6 6 5 5 3 輸出：_2、p

11、rogram j302;var a,b:integer;var x,y:integer;procedure fun(a,b:integer);var k:integer;begin k:=a; a:=b; b:=k; end;begin a:=3; b:=6; x:=a; y:=b; fun(x,y); writeln(a,',',b);end.輸出：_3、program j303;var a1:array1.50 of integer;var i,j,t,t2,n,n2:integer;begin n:=50; for i:=1 to n do a1i:=0; n2:=rou

12、nd(sqrt(n); for i:=2 to n2 do if (a1i=0) then begin t2:=n div i; for j:=2 to t2 do a1i*j:=1; end; t:=0; for i:=2 to n do if (a1i=0) then begin write(i:4); inc(t); if (t mod 10=0) then writeln; end; writeln;end.輸出：_ _4、Program j304;Type str1=string100; Str2=string200;Var S1:str1; s2:str2;Function isa

13、lpha(c:char):Boolean;Var i:integer;Begin i:=ord(c); if (i>=65) and (i<=90) or (i>=97) and (i<=122) then isalpha:=true else isalpha:=false;end;function isdigit(c:char):Boolean;var i:integer;begin i:=ord(c); if (i>=48) and (i<=57) then isdigit:=true else isdigit:=false;end;procedure

14、expand(s1:str1;var s2:str2);var i,j:integer; a,b,c:char;begin j:=1; c:=char(1); i:=0; while (i<=ord(s10) do begin inc(i); c:=s1; if c='-' then begin 1 a:=s1i-1; b:=s1i+1; if (isalpha(a) and isalpha(b) or (isdigit(a) and isdigit(b) then begin dec(j); while (ord(upcase(a)<ord(upcase(s1i+

15、1) do begin s2j:=a; inc(j); inc(a); end; end elsebegin s2j:=c; inc(j); end;end1else begin s2j:=c; inc(j); end; end; s20:=char(j-2); end;begin readln(s1); expand(s1,s2); writeln(s2);end.輸入：wer2345d-h454-82qqq 輸出：_四、完善程序（前4空，每空2.5分，后6空，每空3分，共28分）。1、（求字符的逆序）下面的程序的功能是輸入若干行字符串，每輸入一行，就按逆序輸出該行，最后鍵入-1終止程序。

16、請(qǐng)將程序補(bǔ)充完整。Program j401;type str1=string100;var line:str1; kz:integer;procedure reverse(var s:str1);var I,j:integer; t:char;begini:=1; j:=length(s);while (i<j) do begint:=si; si:=sj; sj:=t; ;end;end;beginwriteln(continue? -1 for end.);readln(kz);while ()dobeginreadln(line);writeln(line);writeln(con

17、tinue? -1 for end.);readln(kz);end;end.2 2 3 32 -1 1 34 1 1 54 4 5 52、（棋盤覆蓋問題）在一個(gè)2k×2 k個(gè)方格組成的棋盤中恰有一個(gè)方格與其它方格不同（圖中標(biāo)記為-1的方格），稱之為特殊方格。現(xiàn)用L型（占3個(gè)小方格）紙片覆蓋棋盤上除特殊方格的所有部分，各紙片不得重疊，于是，用到的紙片數(shù)恰好是（4 k-1）/3。在下表給出的一個(gè)覆蓋方案中，k=2，相同的3各數(shù)字構(gòu)成一個(gè)紙片。 下面給出的程序使用分治法設(shè)計(jì)的，將棋盤一分為四，依次處理左上角、右上角、左下角、右下角，遞歸進(jìn)行。請(qǐng)將程序補(bǔ)充完整。Program j402;t

18、ype arr1=array1.65 of integer; arr2=array1.65 of arr1;var board:arr2; tile:integer; size,dr,dc:integer;procedure chessboard(tr,tc:integer; dr,dc:integer; var size:integer);var t,s:integer;begin if (size=1) then ; t:=tile; inc(tile); s:=size div 2; if then chessboard(tr,tc,dr,dc,s) else begin boardtr

19、+s-1:=t;end;if (dr<tr+s) and (dc>=tc+s) then chessboard(tr,tc+s,dr,dc,s) else begin boardtr+s-1tc+s:=t; ; end;if (dr>=tr+s) and (dc<tc+s) then chessboard(tr+s,tc+s,dr,dc,s) else begin boardtr+stc+s:=t; ; end;if (dr>=tr+s) and (dc>=tc+s) then chessboard(tr+s,tc+s,dr,dc,s)else begin boardtr+stc+s:=t; end;end;procedure prt1(n:integer);var I,j:integer;begin for I:=1 to n do begin for j:=1 to n do write(boardj:3); writeln;end;end;begin writeln(input size(4/8/16/64):); readln(size); writeln(input the position of special block(x,y):); readln(dr,dc); boarddr