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

北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 更多競(jìng)賽真題免費(fèi)下載 見北京清北學(xué)堂官方網(wǎng)站 學(xué)習(xí)資源：自主招生 學(xué)科競(jìng)賽 高考等資源 NOIP2007 初賽普及組試題 第十三屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題 （ 普及組 Pascal 語言 二小時(shí)完成） 2007.10.20 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 一、 單項(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ǔ)容量的常用單位。 A Byte B KB C UB D TB 4 ASCII 碼的含義是（ ）。 A二 十進(jìn)制轉(zhuǎn)換碼 B美國信息交換標(biāo)準(zhǔn)代碼 C數(shù)字的二進(jìn)制編碼 D計(jì)算機(jī)可處理字符的唯一編碼 5一個(gè)完整的計(jì)算機(jī)系統(tǒng)應(yīng)包括（ ）。 A系統(tǒng)硬 件和系統(tǒng)軟件 B硬件系統(tǒng)和軟件系統(tǒng) C主機(jī)和外部設(shè)備 D主機(jī)、鍵盤、顯示器和輔助存儲(chǔ)器 6 IT 的含義是（ ）。 A通信技術(shù) B信息技術(shù) C網(wǎng)絡(luò)技術(shù) D信息學(xué) 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 7 LAN 的含義是（ ）。 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é)、語文和英語的三科成績，如果還存放三 科成績的總分，則總分就可以看作冗余數(shù)據(jù)。冗余數(shù)據(jù)往往會(huì)造成數(shù)據(jù)的不一致。例如，上面 4 個(gè)數(shù)據(jù)如果都是輸入的，由于操作錯(cuò)誤使總分不等于三科成績之和，就會(huì)產(chǎn)生矛盾。下面關(guān)于冗余數(shù)據(jù)的說法中，正確的是（ ）。 A應(yīng)該在數(shù)據(jù)庫中消除一切冗余數(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)境有（ ）。 A gcc B g+ C Turbo C D Free Pascal 10以下斷電后仍能保存數(shù)據(jù)的有（ ）。 A硬盤 B高速緩存 C顯存 D RAM 11在下列關(guān)于計(jì)算機(jī)語言的說法中，正確的有（ ）。 A高級(jí)語言比匯編語言更高級(jí)，是因?yàn)樗某绦虻倪\(yùn)行效率更高 B隨著 Pascal、 C 等高級(jí)語言的出現(xiàn)，機(jī)器語言和匯編語言已經(jīng)退出了歷史舞臺(tái) C高級(jí)語言比匯 編語言程序更容易從一種計(jì)算機(jī)上移植到另一種計(jì)算機(jī)上 D C 是一種面向?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)用 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 13一個(gè)無法靠自身的控制終止的循環(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）的值是（ ）。 A 18 B 1 C 23 D 32 15在 Pascal 語言中，判斷整數(shù) a 等于 0 或 b 等于 0 或 c 等于 0 的正確的條件表達(dá)式是（ ）。 A not (a0) or (b0) or (c0) B not (a0) and (b0) and (c0) C not (a=0) and (b=0) or (c0) 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 柱上的操作記錄為 “進(jìn)、進(jìn)、出、進(jìn)、進(jìn)、出、出、進(jìn)、進(jìn)、出、進(jìn)、出、出 ”。那么，在 C 柱上，從下到上的編號(hào)為（ ）。 A 2 4 3 6 5 7 B 2 4 1 2 5 7 C 2 4 3 1 7 6 D 2 4 3 6 7 5 17與十進(jìn)制數(shù) 1770 對(duì)應(yīng)的八進(jìn)制數(shù)是（ ）。 A 3350 B 3351 C 3352 D 3540 18設(shè) A=B=True， C=D=False，一下邏輯運(yùn)算表達(dá)式值為假的有（ ）。 A ( A B) (C D A) B (A B) C) D) C A (B C D) D D (A (D C) B 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 19 (2070)16 + (34)8 的結(jié)果是（ ）。 A（ 8332） 10 B（ 208A） 16 C（ 100000000110） 2 D (20212)8 20已知 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，則該二叉樹的后根遍歷是（ ）。 A 4 6 5 2 7 3 1 B 4 6 5 2 1 3 7 C 4 2 3 1 5 4 7 D 4 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)， (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)行分析。） 2、（最短路線）某城市的街道是一個(gè)很規(guī)整的矩形網(wǎng)絡(luò)（見下圖），有 7 條南北向的縱街，5 條東西向的橫街。現(xiàn)要從西南角的 A 走到東北角的 B，最短的走法共有多少種？ _ (圖畫不了 ) 三、閱讀程序?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:=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； 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 x:=a+b-p(p3+3) mod 4； if (x10) 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、 program 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 a1:=0； n2:=round(sqrt(n)； for i:=2 to n2 do 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 if (a1=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 (a1=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 isalpha(c:char):Boolean； Var i:integer； Begin i:=ord(c)； if (i=65) and (i=97) and (i=48) and (i=57) then isdigit:=true else isdigit:=false； end； procedure 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+1) do begin s2j:=a； inc(j)； inc(a)； end； end else begin s2j:=c； inc(j)； end； end1 else 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 終止程序。 請(qǐng)將程序補(bǔ)充完整。 Program j401； type str1=string100； 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 var line:str1； kz:integer； procedure reverse(var s:str1)； var I,j:integer； t:char； begin i:=1； j:=length(s)； while (ij) do begin t:=s； s:=sj； sj:=t； ； ； end； end； begin writeln(continue? -1 for end.)； readln(kz)； while ( )do begin readln(line)； ； writeln(line)； writeln(continue? -1 for end.)； readln(kz)； end； end. 2 2 3 3 2 -1 1 3 4 1 1 5 4 4 5 5 2、（棋盤覆蓋問題）在一個(gè) 2k2 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ì)的，將棋盤一分為四，依次處理左上角、右上角、左下角、北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 右下角，遞 歸進(jìn)行。請(qǐng)將程序補(bǔ)充完整。 (圖畫不了 .郁悶 ) Program j402； type 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+s-1:=t； end； if (dr=tc+s) then chessboard(tr,tc+s,dr,dc,s) else begin boardtr+s-1tc+s:=t； ； end； if (dr=tr+s) and (dc=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； 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 北京清北學(xué)堂 報(bào)名咨詢熱線： 400-699-3290 end； end； begin writeln(input size(4/8/16/64):)； readln(size)； writeln(input the position of speci