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

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

2、制編碼5 一個完整的計算機系統(tǒng)應(yīng)包括A 系統(tǒng)硬件和系統(tǒng)軟件C. 主機和外部設(shè)備存儲器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美國信息交換標準代碼計算機可處理字符的唯一編碼硬件系統(tǒng)和軟件系統(tǒng)主機、鍵盤、顯示器和輔助信息學城域網(wǎng)8冗余數(shù)據(jù)是指可以由其它數(shù)據(jù)導(dǎo)出的數(shù)據(jù)。例如，數(shù)據(jù)庫中已存放了學生的數(shù)學、語文和英語 的三科成績，如果還存放三科成績的總分，那么總分就可以看作冗余數(shù)據(jù)。冗余 數(shù)據(jù)往往會造成數(shù) 據(jù)的不一致。例如，上面 4 個數(shù)據(jù)如果都是輸入的，由于操作錯誤使 總分不等于三科成績之和，

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

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

5、對于已經(jīng)定義好的標準數(shù)學函數(shù) sin(x) , 應(yīng)用程序中的語 句 “ y=si n(sin( x);就是一種遞歸調(diào)用13 . 一個無法靠自身的控制終止的循環(huán)成為“死循環(huán)，例如，在C 語言程序中，語句while(1) printf(“ * ); 就是一個死循環(huán)，運行時它將無休止地打印 * 號。下面關(guān)于死循環(huán)的說法中，只有 ( ) 是正確的。A.不存在一種算法，對任何一個程序及相應(yīng)的輸入數(shù)據(jù)，都可以判斷是否會出現(xiàn)死循環(huán)，因而，任何編譯系統(tǒng)都不做死循環(huán)檢查B ?有些編譯系統(tǒng)可以檢測出死循環(huán)C. 死循環(huán)屬于語法錯誤，既然編譯系統(tǒng)能檢查各種語法錯誤，當然也應(yīng)該能檢查出死循環(huán)D. 死循環(huán)與多進程中出現(xiàn)的

6、“死鎖差不多，而死鎖是可以檢測的，因而，死循環(huán)也可以檢測的14 在 Pascal 語言中，表達式 ( 23 or 2 xor 5)的值是 ( ) 。A 18 B 1 C 23 D 3215 在 Pascal 語言中，判斷整數(shù) a 等于 0 或 b 等于 0 或 c 等于 0 的正確的條件表達 式是 ( ) 。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 . 地面上有標號為 A、B、C 的三根柱，在 A 柱上放有 10 個直徑相同中間有孔的圓盤， 從上到下依次編號為1 , 2 , 3，將A柱上的局部盤子經(jīng)過 B柱移入C柱，也可以在B 柱上暫存。如果 B 柱上的操作記錄為“進、進、出、進、進、出、出、進、進、出、33523540A.2 43 6 5 7B.2 4 1 2 5 7CD.2 4 3 6 7 517.與十進制數(shù)1770對應(yīng)的八進制數(shù)是。A.3350 B.3351C18 .設(shè)A=B=True , C=D=False，一下邏輯運算表達式值為假的有 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個節(jié)點的二叉樹的先根遍歷是數(shù)字為節(jié)點的編號，以下同，中根遍歷是4 2 6 5 1 7 3,那么該二叉樹的后根遍歷是A. 4 6 5 2 7 3 17 D. 4 6 5 3 1 7 2- 問題求解共 2題，每題5分,共計10分。1、子集劃分將n個數(shù)1 , 2，n劃分成r個子集。每個數(shù)都恰好屬于一個子集，任何兩個不同的子集沒有共同的數(shù)，也沒有空

9、集。將不同劃分方法的總數(shù)記為Sn,r。例如，S4,2=7，這7種不同的劃分方法依次為(1),(234)(2),(134),(3),(124),(4),(123),(12),(34),(13),(24)(14),(23)。當 n=6 , r=3 時，S(6,3)=提示：先固定一個數(shù)，對于其余的5個數(shù)考慮S5,3與S5,2，再分這兩種情況對原固定的數(shù)進行分析。2、最短路線某城市的街道是一個很規(guī)整的矩形網(wǎng)絡(luò) 見以下圖，有7條南北向的縱街，5條東西向的橫街?，F(xiàn)要從西南角的 A走到東北角的B，最短的走法共有多少種？三、閱讀程序?qū)懡Y(jié)果(共4題，每題8分，共計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 終止程序。請將程序補充完整。 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、棋盤覆蓋問題在一個 同圖中標記為-1的方格en d.2k x 2 k個方格組成的棋盤中恰有一個方格與其它方格不,稱之為特殊方格?，F(xiàn)用L型占3個小方格紙片覆蓋棋盤上除特殊方格的所有局部，各紙片不得重疊，于是，用到的紙片數(shù)恰好是4 k-1/3。在下表給出的一個覆蓋方案中，k=2，相同的3個數(shù)字構(gòu)成一個紙片。下面給出的程序使用分治法設(shè)計

18、的，將棋盤一分為四，依次處理左上角、右上角、左下角、右下角，遞歸進行。請將程序補充完整。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