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

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

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

3、B. 編寫(xiě)的系統(tǒng)更容易消除冗余數(shù)就會(huì)產(chǎn)生矛盾。 下面關(guān)于冗余數(shù)據(jù)的說(shuō)法中， 正確的選項(xiàng)是 。 A ?應(yīng)該在數(shù)據(jù)庫(kù)中消除一切冗 余數(shù)據(jù)用高級(jí)語(yǔ)言編寫(xiě)的數(shù)據(jù)處理系統(tǒng)， 通常比用關(guān)系數(shù)據(jù)庫(kù)C. 為了提高查詢效率，在數(shù)據(jù)庫(kù)中可以保存一些冗余數(shù)據(jù)，但更新時(shí)要做相容性檢驗(yàn)D. 做相容性檢驗(yàn)會(huì)降低效率，可以不理睬數(shù)據(jù)庫(kù)中的冗余數(shù)據(jù)9在以下各軟件，不屬于 NOIP 競(jìng)賽復(fù)賽推薦使用的語(yǔ)言環(huán)境有 A gcc BPascalg+ CTurbo CD Free10 以下斷電后仍能保存數(shù)據(jù)的有顯存D11 在以下關(guān)于計(jì)算機(jī)語(yǔ)言的說(shuō)法中，正確的有 RAMA . 高級(jí)語(yǔ)言比匯編語(yǔ)言更高級(jí)，是因?yàn)樗某绦虻倪\(yùn)行效率更高B 隨

4、著 Pascal 、 C 等高級(jí)語(yǔ)言的出現(xiàn)，機(jī)器語(yǔ)言和匯編語(yǔ)言已經(jīng)退出了歷史舞臺(tái)C ?高級(jí)語(yǔ)言比匯編語(yǔ)言程序更容易從一種計(jì)算機(jī)上移植到另一種計(jì)算機(jī)上DC 是一種面向?qū)ο蟮母呒?jí)計(jì)算機(jī)語(yǔ)言12 近 20 年來(lái)，許多計(jì)算機(jī)專(zhuān)家都大力推崇遞歸算法，認(rèn)為它是解決較復(fù)雜問(wèn)題的強(qiáng) 有力的工具。在以下關(guān)于遞歸算法的說(shuō)法中，正確的選項(xiàng)是 ( )。A .在 1977 年前后形成標(biāo)準(zhǔn)的計(jì)算機(jī)高級(jí)語(yǔ)言“ FORTRAN77 禁止在程序使用遞歸， 原因之一是該方法可能會(huì)占用更多的內(nèi)存空間B .和非遞歸算法相比，解決同一個(gè)問(wèn)題，遞歸算法一般運(yùn)行得更快一些C. 對(duì)于較復(fù)雜的問(wèn)題，用遞歸方式編程一般比非遞歸方式更難一些D.

5、對(duì)于已經(jīng)定義好的標(biāo)準(zhǔn)數(shù)學(xué)函數(shù) sin(x) , 應(yīng)用程序中的語(yǔ) 句 “ y=si n(sin( x);就是一種遞歸調(diào)用13 . 一個(gè)無(wú)法靠自身的控制終止的循環(huán)成為“死循環(huán)，例如，在C 語(yǔ)言程序中，語(yǔ)句while(1) printf(“ * ); 就是一個(gè)死循環(huán)，運(yùn)行時(shí)它將無(wú)休止地打印 * 號(hào)。下面關(guān)于死循環(huán)的說(shuō)法中，只有 ( ) 是正確的。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)屬于語(yǔ)法錯(cuò)誤，既然編譯系統(tǒng)能檢查各種語(yǔ)法錯(cuò)誤，當(dāng)然也應(yīng)該能檢查出死循環(huán)D. 死循環(huán)與多進(jìn)程中出現(xiàn)的

6、“死鎖差不多，而死鎖是可以檢測(cè)的，因而，死循環(huán)也可以檢測(cè)的14 在 Pascal 語(yǔ)言中，表達(dá)式 ( 23 or 2 xor 5)的值是 ( ) 。A 18 B 1 C 23 D 3215 在 Pascal 語(yǔ)言中，判斷整數(shù) a 等于 0 或 b 等于 0 或 c 等于 0 的正確的條件表達(dá) 式是 ( ) 。A not (a<>0) or (b<>0) or (c<>0)B not (a<>0) and (b<>0) and (c<>0)C not (a=0) and (b=0) or (c<>0)D (a=0

7、) and (b=0) and (c=0)16 . 地面上有標(biāo)號(hào)為 A、B、C 的三根柱，在 A 柱上放有 10 個(gè)直徑相同中間有孔的圓盤(pán)， 從上到下依次編號(hào)為1 , 2 , 3，將A柱上的局部盤(pán)子經(jīng)過(guò) B柱移入C柱，也可以在B 柱上暫存。如果 B 柱上的操作記錄為“進(jìn)、進(jìn)、出、進(jìn)、進(jìn)、出、出、進(jìn)、進(jìn)、出、33523540A.2 43 6 5 7B.2 4 1 2 5 7CD.2 4 3 6 7 517.與十進(jìn)制數(shù)1770對(duì)應(yīng)的八進(jìn)制數(shù)是。A.3350 B.3351C18 .設(shè)A=B=True , C=D=False，一下邏輯運(yùn)算表達(dá)式值為假的有 A. (AA B) V (C A DV A)C

8、. AA (B V CV D) V D(A A B) V C) A D)(A A (D V C) A B19 . (2070)16 + (34)8A. (8332 ) 10的結(jié)果是()。B.( 208A ) 16 C .2 D . (20212)820 .7個(gè)節(jié)點(diǎn)的二叉樹(shù)的先根遍歷是數(shù)字為節(jié)點(diǎn)的編號(hào)，以下同，中根遍歷是4 2 6 5 1 7 3,那么該二叉樹(shù)的后根遍歷是A. 4 6 5 2 7 3 17 D. 4 6 5 3 1 7 2- 問(wèn)題求解共 2題，每題5分,共計(jì)10分。1、子集劃分將n個(gè)數(shù)1 , 2，n劃分成r個(gè)子集。每個(gè)數(shù)都恰好屬于一個(gè)子集，任何兩個(gè)不同的子集沒(méi)有共同的數(shù)，也沒(méi)有空

9、集。將不同劃分方法的總數(shù)記為Sn,r。例如，S4,2=7，這7種不同的劃分方法依次為(1),(234)(2),(134),(3),(124),(4),(123),(12),(34),(13),(24)(14),(23)。當(dāng) n=6 , r=3 時(shí)，S(6,3)=提示：先固定一個(gè)數(shù)，對(duì)于其余的5個(gè)數(shù)考慮S5,3與S5,2，再分這兩種情況對(duì)原固定的數(shù)進(jìn)行分析。2、最短路線某城市的街道是一個(gè)很規(guī)整的矩形網(wǎng)絡(luò) 見(jiàn)以下圖，有7條南北向的縱街，5條東西向的橫街?，F(xiàn)要從西南角的 A走到東北角的B，最短的走法共有多少種？三、閱讀程序?qū)懡Y(jié)果(共4題，每題8分，共計(jì)32分。)1、program j301;var

10、i,a,b,c,x,y:i n teger;p:array0.4 of in teger;begi ny:=20;for i:=0 to 4 do read(p);readl n;a：=(p0+p1)+(p2+p 3+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,','

11、;,y);end. 注：本例中，給定的輸入數(shù)據(jù)可以防止分母為 輸 0 或數(shù)組元素下表越界。 入： 6 6 5 5 3 輸出： 2 、 program j302; var a,b:integer;var x,y? in teger;procedure fun(a,b:integer);var k:integer; begin k:=a; a:=b; b:=k; end;begina:=3; b:=6; x:=a; y:=b;fun( x A,yA); writeln(a,',',b);end.輸出： 3 、 program j303;var a1:array1.50 of int

12、eger;var i,j,t,t2,n,n2:integer;beginn:=50;for i:=1 to n do a1:=0; n2:=round(sqrt(n);for i:=2 to n2 doif (a1=0) thenbegint2:=n div i;for j:=2 to t2 do a1i*j:=1;end;t:=0;for i:=2 to n doif (a1=0) thenbegin write(i:4); inc(t); if (t mod 10=0) then writeln; end;writeln;end.輸出：4 、 Program j304;Type str1=

13、string100;Str2=string200;VarS1:str1; s2:str2;Function isalpha(c:char):Boolean;Var i:integer;Begini:=ord(c);if (i>=65) and (i<=90) or (i>=97) and (i<=122) then isalpha:=trueelse isalpha:=false;end;function isdigit(c:char):Boolean;var i:integer;begini:=ord(c); if (i>=48) and (i<=57)

14、then isdigit:=trueelse isdigit:=false;end;procedure expand(s1:str1;var s2:str2);var i,j:integer; a,b,c:char;beginj:=1; c:=char(1); i:=0;while (i<=ord(s10) dobegin 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 isdigi t(b) then begin

15、 dec(j);while (ord(upcase(a)<ord(upcase(s1i+1 ) dobegins2j:=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 分，共 2

16、8 分。出該行，最后鍵入1 、求字符的逆序 下面的程序的功能是輸入假設(shè)干行字符串，每輸入一行，就按逆序輸 -1 終止程序。請(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 begin t:=s; s:=sj; sj:=t; ; ;end; end; begin-1 forend.');write ln

17、( con ti nue?read ln( kz);while ()dobegi nread In (1 ine);-1 forend.');write ln( li n e);write ln( con ti nue?read ln( kz);en d;2、棋盤(pán)覆蓋問(wèn)題在一個(gè) 同圖中標(biāo)記為-1的方格en d.2k x 2 k個(gè)方格組成的棋盤(pán)中恰有一個(gè)方格與其它方格不,稱(chēng)之為特殊方格?，F(xiàn)用L型占3個(gè)小方格紙片覆蓋棋盤(pán)上除特殊方格的所有局部，各紙片不得重疊，于是，用到的紙片數(shù)恰好是4 k-1/3。在下表給出的一個(gè)覆蓋方案中，k=2，相同的3個(gè)數(shù)字構(gòu)成一個(gè)紙片。下面給出的程序使用分治法設(shè)計(jì)

18、的，將棋盤(pán)一分為四，依次處理左上角、右上角、左下角、右下角，遞歸進(jìn)行。請(qǐng)將程序補(bǔ)充完整。Program j402;type arr 仁 array1.65 of in teger;arr2=array1.65 of arr1;var board:arr2; tile:integer; size,dr,dc:integer;procedure chessboard(tr,tc:integer; dr,dc:integer; var size:int eger);var t,s:i n teger;begi nif (size=1) the n;22332-11341154455t:=tile; in c(tile);s:=size div 2;if the n chessboard(tr,tc,dr,dc,s) else beginboardtr+s-1:=t; ;end;if (dr<tr+s) and