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

1、第十三屆全國青少年信息學(xué)奧林匹克聯(lián)賽初賽試題（ 提高組 Pascal語言 兩小時(shí)完成 ）全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效一、 單項(xiàng)選擇題 （共 10 題，每題 1.5 分，共計(jì) 15 分。每題有且僅有一個(gè)正確答案）。1. 在以下各項(xiàng)中，（）不是 CPU 的組成部分。A. 控制器 B. 運(yùn)算器 C. 寄存器D. 主板 E. 算術(shù)邏輯單元(ALU)2. 在關(guān)系數(shù)據(jù)庫中，存放在數(shù)據(jù)庫中的數(shù)據(jù)的邏輯結(jié)構(gòu)以（）為主。A. 二叉樹 B. 多叉樹 C.哈希表D. B+樹 E.二維表3. 在下列各項(xiàng)中，只有（）不是計(jì)算機(jī)存儲(chǔ)容量的常用單位。A. Byte B. KB C.MBD.UB E.

2、TB4. ASCII 碼的含義是（）。 A. 二十進(jìn)制轉(zhuǎn)換碼 B. 美國信息交換標(biāo)準(zhǔn)代碼C. 數(shù)字的二進(jìn)制編碼 D. 計(jì)算機(jī)可處理字符的唯一編碼 E. 常用字符的二進(jìn)制編碼5. 在 Pascal 語言中，表達(dá)式(23 or 2 xor 5)的值是（） A. 18 B. 1 C.23D.32 E.246. 在 pascal 語言中，判斷整數(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<>

3、;0) C. not(a=0)and(b=0)or(c<>0) D. (a=0)and(b=0)and(c=0)E. not(a=0)or(b=0)or(c=0)7. 地面上有標(biāo)號(hào)為 A、B、C 的 3 根細(xì)柱，在 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 7B. 2 4 1 2 5 7C. 2 4 31 7 6

4、D. 2 4 3 6 7 5E. 2 1 4 3 7 58. 與十進(jìn)制數(shù) 17.5625 對(duì)應(yīng)的 8 進(jìn)制數(shù)是（ ）。A. 21.5625 B. 21.44 C. 21.73D. 21.731 E. 前 4 個(gè)答案都不對(duì)9. 歐拉圖 G 是指可以構(gòu)成一個(gè)閉回路的圖，且圖 G 的每一條邊恰好在這個(gè)閉回路上出現(xiàn)一次（即一筆 畫成）。在以下各個(gè)描述中，不一定是歐拉圖的是（）。A. 圖 G 中沒有度為奇數(shù)的頂點(diǎn)B. 包含歐拉環(huán)游的圖（歐拉環(huán)游是指通過圖中每邊恰好一次的閉路徑）C. 包含歐拉閉跡的圖（歐拉跡是指通過圖中每邊恰好一次的路徑）D. 存在一條回路，通過每個(gè)頂點(diǎn)恰好一次E. 本身為閉跡的圖10.

5、 一個(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)檢驗(yàn)B有些編譯系統(tǒng)可以檢測出死循環(huán)C. 死循環(huán)屬于語法錯(cuò)誤，既然編譯系統(tǒng)能檢查各種語法錯(cuò)誤，當(dāng)然也應(yīng)該能檢查出死循環(huán)D. 死循環(huán)與多進(jìn)程中出現(xiàn)的“死鎖”差不多，而死鎖是可以檢測的，因而，死循環(huán)也是可以檢測的E. 對(duì)于死循環(huán)，只能等到發(fā)生時(shí)做現(xiàn)場處理，沒有什么更積極的手段二、

6、 不定項(xiàng)選擇題 （共 10 題，每題 1.5 分，共計(jì) 15 分。每題正確答案的個(gè)數(shù)大于或等于 1。多選 或少選均不得分）。11. 設(shè)A=B=true，C=D=false，以下邏輯運(yùn)算表達(dá)式值為真的有（）。A. (¬ AB)(CDA) B. ¬ (AB)C)D) C. A(BCD)D D. (A(DC) B12. 命題“PQ”可讀做P蘊(yùn)涵Q，其中P、Q 是兩個(gè)獨(dú)立的命題。只有當(dāng)命題P成立而命題Q不成立時(shí)， 命題“PQ”的值為false，其他情況均為true。與命題“PQ”等價(jià)的邏輯關(guān)系式是（）。A. ¬ PQ B. PQ C. ¬ (PQ) D.

7、72; (¬ QP)13. (2070)16 + (34)8 的結(jié)果是（）。A. (8332)10 B. (208C)16C. (100000000110)2 D. (20214)8f14. 已知 7 個(gè)結(jié)點(diǎn)的二叉樹的先根遍歷是 1 2 4 5 6 3 7（數(shù)字為結(jié)點(diǎn)的編號(hào)，以下同），后根遍歷 是 4 6 5 2 7 3 1，則該二叉樹的可能的中根遍歷是（）A. 4 2 6 5 1 7 3B. 4 2 5 6 1 3 7C. 4 2 3 1 5 4 7D. 4 2 5 6 1 7 315. 冗余數(shù)據(jù)是指可以由其他數(shù)據(jù)導(dǎo)出的數(shù)據(jù)，例如，數(shù)據(jù)庫中已存放了學(xué)生的數(shù)學(xué)、語文和英語的三 科成績

8、，如果還存放三科成績的總分，則總分就可以看作冗余數(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ù)庫中可以適當(dāng)保留一些冗余數(shù)據(jù)，但更新時(shí)要做相容性檢驗(yàn) D. 做相容性檢驗(yàn)會(huì)降低效率，可以不理睬數(shù)據(jù)庫中的冗余數(shù)據(jù)16. 在下列各軟件中，屬于 NOIP 競賽（復(fù)賽）推薦使用的語言環(huán)境有（）。A. gcc B. g+C. Turbo

9、 C D. free pascal17. 以下斷電之后仍能保存數(shù)據(jù)的有（）。A. 硬盤 B. ROMC. 顯存 D. RAM18. 在下列關(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是一種面向過程的高級(jí)計(jì)算機(jī)語言19. 在下列關(guān)于算法復(fù)雜性的說法中，正確的有（）。A. 算法的時(shí)間復(fù)雜度，是指它在某臺(tái)計(jì)算機(jī)上具體實(shí)現(xiàn)時(shí)的運(yùn)行時(shí)間B. 算法的時(shí)間復(fù)雜度，是指對(duì)于該算法的一種或幾種主要的運(yùn)算

10、，運(yùn)算的次數(shù)與問題的規(guī)模之間的函 數(shù)關(guān)系C. 一個(gè)問題如果是NPC類的，就意味著在解決該問題時(shí)，不存在一個(gè)具有多項(xiàng)式時(shí)間復(fù)雜度的算法。 但這一點(diǎn)還沒有得到理論上的證實(shí)，也沒有被否定D. 一個(gè)問題如果是NP類的，與C有相同的結(jié)論20. 近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ù)雜的問題，用遞歸方式編程往往

11、比非遞歸方式更容易一些D. 對(duì)于已經(jīng)定義好的標(biāo)準(zhǔn)數(shù)學(xué)函數(shù) sin(x)，應(yīng)用程序中的語句“y=sin(sin(x);”就是一種遞 歸調(diào)用三問題求解（共 2 題，每題 5 分，共計(jì) 10 分）1 給定 n 個(gè)有標(biāo)號(hào)的球，標(biāo)號(hào)依次為 1，2，n。將這 n 個(gè)球放入 r 個(gè)相同的盒子里，不允許 有空盒，其不同放置方法的總數(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=7,r=4 時(shí)，S(7,4)= _。2 N 個(gè)人在

12、操場里圍成一圈，將這 N 個(gè)人按順時(shí)針方向從 1 到 N 編號(hào)，然后，從第一個(gè)人起，每 隔一個(gè)人讓下一個(gè)人離開操場，顯然，第一輪過后，具有偶數(shù)編號(hào)的人都離開了操場。依次做下去，直 到操場只剩 下一個(gè)人， 記這個(gè)人的 編號(hào)為 J(N) ，例如， J(5)=3 ， J(10)=5 ， 等等。 則 J(400)=_。（提示：對(duì) N=2m+r 進(jìn)行分析，其中 0r<2m ）。四閱讀程序?qū)懡Y(jié)果（共 4 題，每題 8 分，共計(jì) 32 分）1 program s401;var p,q: array0.5 of integer; i, x, y: integer;begin y := 20;for i

13、:= 0 to 4 doread(pi); readln; q0:=(p0+p1)+(p2+p3+p4) div 7; q1:=p0+p1 div (p2+p3) div p4); q2:=p0*p1 div p2; q3:=q0*q1; q4:=q1+q2+q3; x:=(q0+q4+2)-p(q3+3) mod 4; if (x>10) then y:=y+(q1*100-q3) div (pp4 mod 3*5) else y:=y+20+(q2*100-q3) div (pp4 mod 3*5); writeln(x,',',y);end./* 注：本例中，給定的

14、輸入數(shù)據(jù)可以避免分母為 0 或數(shù)組元素下標(biāo)越界。 */輸入：6 6 5 5 3 輸出：_2 program s402;var a, b: integer;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); write('No.1:',a,',',b,' '); fun(a,b); writeln('No.2:',a,','

15、;,b);end.輸出:_3 program S403;var a1: array1.50 of integer; i, j, t, t2, n, n2: integer;begin n:=50;for i:=1 to n do a1i:=0; n2 := round(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 mo

16、d 10=0) then writeln; end;writeln; end.輸出： _ _4.program S404;const n = 12; ch2: array0.12 of char =('q','A','S','O','R','T','E','X','A','M','P','L','E');var k: integer;ch: array0.12 of char; proce

17、dure shift(k,n:integer); var v: char;j: integer;begin v:=chk; j:=k+k; while (j<=n) do begin if (j<n) and (ord(chj)<ord(chj+1) then inc(j); if (ord(v)<ord(chj) then begin chj div 2:=chj; j:=j*2; end else exit; chj div 2:=v;end;end;procedure hpsrt;var k: integer; tmp: char;beginfor k:=n di

18、v 2 downto 1 do shift(k,n); write('No.1: ');for k:=1 to n dowrite(chk); writeln;for k:=n downto 1 do begin tmp:=ch1; ch1:=chk; chk:=tmp; shift(1,k-1); end; end; beginfor k:=0 to n do chk:=ch2k; hpsrt; write('No.2: ');for k:=1 to n do write(chk); writeln;end.輸出：_五完善程序 (前 5 空，每空 2 分，后

19、6 空，每空 3 分，共 28 分)1 （格雷碼，Gray Code） 格雷碼是對(duì)十進(jìn)制數(shù)的一種二進(jìn)制編碼。編碼順序與相應(yīng)的十進(jìn)制數(shù)的大小不一致。其特點(diǎn)是：對(duì)于兩個(gè)相鄰的十進(jìn)制數(shù)，對(duì)應(yīng)的兩個(gè)格雷碼只有一個(gè)二進(jìn)制位不同。另外，最大數(shù)與最小數(shù)之間也僅有一個(gè) 二進(jìn)制位不同，以 4 位二進(jìn)制數(shù)為例，編碼如下：十進(jìn)制數(shù)格雷碼十進(jìn)制數(shù)格雷碼0 00008 11001 00019 11012 00111011113 00101111104 01101210105 01111310116 01011410017 0100151000如果把每個(gè)二進(jìn)制的位看作一個(gè)開關(guān)，則將一個(gè)數(shù)變?yōu)橄噜彽牧硪粋€(gè)數(shù)，只須改動(dòng)一個(gè)開

20、關(guān)。因此， 格雷碼廣泛用于信號(hào)處理、數(shù)-模轉(zhuǎn)換等領(lǐng)域。下面程序的任務(wù)是：由鍵盤輸入二進(jìn)制數(shù)的位數(shù) n (n<16)，再輸入一個(gè)十進(jìn)制數(shù) m(0m<2n)，然 后輸出對(duì)應(yīng)于 m 的格雷碼（共 n 位，用數(shù)組 gr存放）。為了將程序補(bǔ)充完整，你必須認(rèn)真分析上表的規(guī)律，特別是對(duì)格雷碼固定的某一位，從哪個(gè)十進(jìn)制數(shù) 起，由 0 變?yōu)?1，或由 1 變?yōu)?0。程序：program S501;var bound, m, n, i, j, b, p: integer; gr: array0.14 of integer;begin bound:=1; writeln('input n,m&#

21、39;); readln(n,m);for i:=1 to n do bound:= ;if (m<0) or(m>=bound) then begin writeln('Data error!'); ; end; b := 1;for i := 1 to n do begin p := 0; b := b * 2; for to m do if ( ) then p:=1-p; gri:=p; end; for i:=n do write(gri); writeln;end.2 （連續(xù)郵資問題）某國發(fā)行了 n 種不同面值的郵票，并規(guī)定每封信最多允許貼 m 張郵票，

22、在這 些約束下，為了能貼出1，2，3,，maxvalue連續(xù)整數(shù)集合的所有郵資，并使 maxvalue 的值最 大，應(yīng)該如何設(shè)計(jì)各郵票的面值？例如，當(dāng) n=5、m=4 時(shí)，面值設(shè)計(jì)為1，3，11，15，32，可使 maxvalue 達(dá)到最大值 70（或者說，用這些面值的 1 至 4 張郵票可以表示不超過 70 的所有郵資，但無 法表示郵資 71。而用其他面值的 1 至 4 張郵票如果可以表示不超過 k 的所有郵資，必有 k70）。 下面是用遞歸回溯求解連續(xù)郵資問題的程序。數(shù)組 x1:n表示 n 種不同的郵票面值，并約定各元 素按下標(biāo)是嚴(yán)格遞增的。數(shù)組 bestx 1:n存放使 maxvalue

23、 達(dá)到最大值的郵票面值（最優(yōu)解）， 數(shù)組 ymaxl用于記錄當(dāng)前已選定的郵票面值 x1:i能貼出的各種郵資所需的最少郵票張數(shù)。請(qǐng)將程序補(bǔ)充完整。程序：program S502;const NN=20; maxint=30000; maxl=500;var bestx, x: array 0.NN of integer; y: array 0.maxl of integer; j, n, m, maxvalue: integer;procedure result; 輸出結(jié)果：最大值：maxvalue及最優(yōu)解： bestx1:n（略）procedure backtrace(i,r:integer)

24、;var j, k: integer; z: array0.maxl of integer;begin for j:=0 to do if (yj<m) then for k:=1 to m-yj do if (yj+k<=y ) then y := yj + k;while (yr<maxint) do inc(r); if (i>n) then begin if (r 1 > maxvalue) then begin maxvalue:= ; for j:=1 to n do bestxj := xj; end; exit;end;for k := 0 to

25、maxl do zk := yk; for j := to r do begin xi:=j; ; for k:=0 to maxl do yk:=zk; end; end;begin maxvalue:=0;writeln('input n,m:'); readln(n,m);for j:=1 to maxl do yj:=maxint; y0:=0; x0:=0; x1:=1;backtrace(2,1);result;end.NOIP2007年提高組（Pascal語言）參考答案與評(píng)分標(biāo)準(zhǔn)一、單項(xiàng)選擇題：（每題1.5分）1. D   

26、2. E   3. D   4. B   5. A    6. B   7. D   8. B   9. D  10. A 二、 不定項(xiàng)選擇題 （共10題，每題1.5分，共計(jì)15分。每題正確答案的個(gè)數(shù)大于或等于1。多選或少選均不得分）

27、60;11. ABC   12. AD   13. ABD  14. ABD  15. BC    16. ABD   17. AB   18. CD   19. BC    20. AC 三、問題求解：（共2題，每題5分，共計(jì)10分）13502289四、閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計(jì)32分）1 129,432 No.1:3,6 &#