NOIP2000普及組初賽試題答案

1、精選優(yōu)質文檔-傾情為你奉上專心-專注-專業(yè)第六屆全國青少年信息學（計算機）奧林匹克分區(qū)聯(lián)賽試題第六屆全國青少年信息學（計算機）奧林匹克分區(qū)聯(lián)賽試題（ 普及組普及組 PASCAL 語言語言 二小時完成二小時完成 ） 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 一、選擇一個正確答案代碼（A/B/C/D），填入每題的括號內 (每題 1.5 分，多選無分，共30 分）1下列無符號數(shù)中，最小的數(shù)是（ ）A（）2 B（75）10 C（37）8 D（2A）162在外部設備中，繪圖儀屬于（ ） A輸入設備 B輸出設備 C輔（外）存儲器 D主（內）存

2、儲器3GB2312-80 規(guī)定了一級漢字 3755 個，二級漢字 3008 個，其中二級漢字字庫中的漢字是以（ ）為序排列的A以筆劃多少 B以部首 C以 ASCII 碼 D以機內碼4算法是指（ ）A為解決問題而編制的計算機程序 B為解決問題而采取的方法與步驟C為解決問題而需要采用的計算機語言 D為解決問題而采用的計算方法5RAM 中的信息是（ ）A生產廠家預先寫入的 B計算機工作時隨機寫入的C防止計算機病毒侵入所使用的 D專門用于計算機開機時自檢用的6計算機主機是由 CPU 與（ ）構成的 A控制器 B運算器 C輸入、輸出設備 D內存儲器7計算機病毒的特點是（ ） A傳播性、潛伏性、易讀性與隱

3、蔽性 B破壞性、傳播性、潛伏性與安全性 C傳播性、潛伏性、破壞性與隱蔽性 D傳播性、潛伏性、破壞性與易讀性8設循環(huán)隊列中數(shù)組的下標范圍是 1n，其頭尾指針分別為 f 和 r，則其元素個數(shù)為（ ） Ar- f Br- f +1 C（r- f ） MOD n+1 D（r- f + n） MOD n9在待排序的數(shù)據(jù)表已經(jīng)為有序時，下列排序算法中花費時間反而多的是（ ） A 堆排序 B 希爾排序 C 冒泡排序 D 快速排序10Internet 的規(guī)范譯名應為（ ）精選優(yōu)質文檔-傾情為你奉上專心-專注-專業(yè) A英特爾網(wǎng) B因特網(wǎng) C 萬維網(wǎng) D以太網(wǎng)11WINDOWS 9X 是一種（ ）操作系統(tǒng) A單任

4、務字符方式 B單任務圖形方式 C多任務字符方式 D多任務圖形方式12某種計算機的內存容量是 640K, 這里的 640K 容量是指( ) 個字節(jié)A640 B 640*1000 C 640 * 1024 D640*1024*1024 13在 Windows 9X 中，菜單項后帶有符號“”，表示該菜單項( ) A可以進行開關選擇 B執(zhí)行時有對話框C有若干子命令 D不能執(zhí)行14某數(shù)列有 1000 個各不相同的單元，由低至高按序排列；現(xiàn)要對該數(shù)列進行二分法檢索(binary search)，在最壞的情況下，需檢視( )個單元 A1000 B. 10 C. 100 D. 500 15已知數(shù)組 A 中，每

5、個元素 AI，J在存貯時要占 3 個字節(jié)，設 I 從 1 變化到 8，J 從 1變化到 10，分配內存時是從地址 SA 開始連續(xù)按行存貯分配的。試問：A5，8的起始地址為（ ） ASA+141 BSA+180 CSA+222 DSA+22516大家知道，不同類型的存儲器組成了多層次結構的存儲器體系，按存取速度從快到慢的排列是（ ）A快存 / 輔存 / 主存 B外存 / 主存 / 輔存C快存 / 主存 / 輔存 D主存 / 輔存 / 外存17線性表若采用鏈表存貯結構，要求內存中可用存貯單元地址（ ）A必須連續(xù) B部分地址必須連續(xù)C一定不連續(xù) D連續(xù)不連續(xù)均可18下列敘述中，正確的是（ ）A 線性

6、表的線性存貯結構優(yōu)于鏈表存貯結構 B 隊列的操作方式是先進后出C 棧的操作方式是先進先出 D二維數(shù)組是指它的每個數(shù)據(jù)元素為一個線性表的線性表19電線上停著兩種鳥（A，B），可以看出兩只相鄰的鳥就將電線分為了一個線段。這些線段可分為兩類：一類是兩端的小鳥相同；另一類則是兩端的小鳥不相同已知：電線兩個頂點上正好停著相同的小鳥，試問兩端為不同小鳥的線段數(shù)目一定是（ ） A奇數(shù) B偶數(shù) C可奇可偶 D數(shù)目固定精選優(yōu)質文檔-傾情為你奉上專心-專注-專業(yè)20請仔細閱讀下列程序段: PASCAL 語言 BASIC 語言 上列程序段的正確輸出是（ ） A-1 B-2 C-3 D-4 二、問題解答（每題 7 分

7、，共 14 分） 1已知，按中序遍歷二叉樹的結果為：abc問：有多少種不同形態(tài)的二叉樹可以得到這一遍歷結果，并畫出這些二叉樹。 2有 2n 的一個長方形方格，用一個 12 的骨牌鋪滿方格。例如 n=3 時，為 23 方格。 此時用一個 12 的骨牌鋪滿方格，共有 3 種鋪法： 試對給出的任意一個 n（n0），求出鋪法總數(shù)的遞推公式。三、閱讀程序，并寫出程序正確的運行結果（10+16 分，共 26 分）1PROGRAM NOI_002; VAR I, J, L, N, K, S, T : INTEGER; B : ARRAY1.10 OF 0.9; BEGIN READLN(L,N); S:=L

8、; K:=1; T:=L; WHILE S0 DO BEGIN J:=J-1; BJ:=N MOD L; N:=N DIV L END; FOR I:=10-K+1 TO 10 DO WRITE(CHR(ORD(A)+BI); END. 輸入：4 167 輸出：2PROGRAM NOI_004; VAR I, J, J1, J2, P, Q : INTEGER; P1 : BOOLEAN; B,C : ARRAY1.100 OF INTEGER; BEGIN READLN(Q,P); J:=1; P1:=TRUE; BJ:=Q; J1:=0; WHILE (Q0) AND P1 DO BEGI

9、N J1:=J1+1; CJ1:=Q*10 DIV P; Q:=Q*10-CJ1*P; IF Q0 THEN BEGIN J2:=1; WHILE (BJ2Q) AND (J2=J) DO J2:=J2+1; IF BJ2=Q THEN BEGIN P1:=FALSE; WRITE(0.); FOR I:=1 TO J2-1 DO WRITE(CI:1); WRITE(); FOR I:=J2 TO J1 DO WRITE(CI:1); WRITELN() END ELSE BEGIN J:=J+1; BJ:=Q END END END; IF Q=0 THEN BEGIN WRITE(0.)

10、; FOR I:=1 TO J1 DO WRITE(CI:1); WRITELN END; READLN END.輸入1 8輸出 輸入 2 7輸出四、完善程序完善程序（每題 15 分，共 30 分）1.將 2n個 0 和 2n 個 1，排成一圈。從任一個位置開始，每次按逆時針的方向以長度為n+1 的單位進行數(shù)二進制數(shù)。 要求給出一種排法，用上面的方法產生出來的 2個二進制數(shù)都不相同。例如，當 n=2 時, 即個 0 和個 1 排成如下一圈： A 00 10 11 1 0 精選優(yōu)質文檔-傾情為你奉上專心-專注-專業(yè)比如，從 A 位置開始，逆時針方向取三個數(shù) 000，然后再從 B 位置上開始取三個

11、數(shù) 001，接著從 C 開始取三個數(shù) 010，可以得到000，001，010，101，011，111，110，100 共 8 個二進制數(shù)且都不相同。程序說明程序說明 以 n=4 為例，即有 16 個 0，16 個 1， 數(shù)組 a 用以記錄 32 個 0，1 的排法， 數(shù)組 b 統(tǒng)計二進制數(shù)是否已出現(xiàn)過。程序清單程序清單 PROGRAM NOI00;VAR A : ARRAY1.36 OF 0.1; B :ARRAY0.31 OF INTEGER; I, J, K, S, P : INTEGER; BEGIN FOR I:=1 TO 36 DO AI:=0; FOR I:=28 TO 32 DO

12、 AI:=1; P:=1; A6:=1; WHILE (P=1) DO BEGIN J:=27; WHILE AJ=1 DO J:=J-1; FOR I:=J+1 TO 27 DO FOR I:=0 TO 31 DO BI:=0; FOR I:=1 TO 32 DO BEGIN FOR K:=I TO I+4 DO S:=S*2+AK; END; S:=0; FOR I:=0 TO 31 DO S:=S+BI; IF THEN P:=0 END; FOR I:=1 TO 32 DO FOR J：=I TO I+4 DO WRITE(AJ); WRITELN END.2多項式的乘法。 例如有如下

13、多項式： P(X)=2X2-X+1, Q(X)=X+1 則： P(X)Q(X)=(2X2-X+1)(X+1)=2X3+X2+1 程序說明：程序說明： 多項式的表示：系數(shù)、指數(shù) 如上例中： P(X)： 系數(shù) 指數(shù) Q(X) 系數(shù) 指數(shù) 2 2 1 1 -1 1 1 0精選優(yōu)質文檔-傾情為你奉上專心-專注-專業(yè) 1 0 0 0 0 0 PXQ 的結果存入 C 中。其輸出格式是：依次用一對括號內的（系數(shù)，指數(shù)）分別來表示。如上例的輸出結果表示為：（2，3）（1，2）（1，0）程序清單程序清單PROGRAM NOI_007; VAR I, J, K, L , JP, JQ, JC, X, Y, X1,

14、 Y1 : INTEGER; P, Q : ARRAY1.10,1.2 OF INTEGER; C : ARRAY1.20,1.2 OF INTEGER; BEGIN JP:=0; READLN(X,Y); WHILE X0 DO BEGIN JP:=JP+1; PJP,1:=X; PJP,2:=Y; READLN(X,Y) END; JQ:=0;READLN(X,Y); WHILE X0 DO BEGIN JQ:=JQ+1; QJQ,1:=X; QJQ,2:=Y; READLN(X,Y) END; JC:=1; CJC,1:=0; CJC,2:=-1000; FOR I:=1 TO JP D

15、O BEGIN Y:=PI,2; FOR J:=1 TO JQ DO BEGIN Y1:=Y+QJ,2; K:=1; WHILE Y10），用 F（N）表示其鋪法的總數(shù)的遞推公式為: （7 分） 賽區(qū)賽區(qū) 市市 學學校校 姓名姓名 = 密密 封封 線線 =三、閱讀程序，并寫出程序的正確運行結果（10+16 分，共 26 分） （1） 程序的運行結果是程序的運行結果是: （2） 程序的運行結果是程序的運行結果是:四、根據(jù)題意，將程序補充完整(每個點 3 分，共 30 分) PASCAL 語言語言 BASIC 語言語言 題一題一 70 110 140 180 220 題二題二 190 240 28

16、0精選優(yōu)質文檔-傾情為你奉上專心-專注-專業(yè) 300 350第六屆全國青少年信息學（計算機）奧林匹克分區(qū)聯(lián)賽初賽試第六屆全國青少年信息學（計算機）奧林匹克分區(qū)聯(lián)賽初賽試題題普及組參考答案普及組參考答案一、選擇一個正確答案代碼（A/B/C/D），填入每題的括號內 (每題 1.5 分，多選無分，共 30 分）題號 1 2 4 5 6 7 8 9 10選擇 C B B B B D C D D B題號 11 12 13 14 15 16 17 18 19 20選擇 D C B B A C D D B A二、問題解答（第 1 題的第 1 問 2 分，第 2 問 5 分，第 2 題 7 分，兩題共 14 分） 1答：答：有 5 種不同形態(tài)的二叉樹可以得到這一遍歷結果；可畫出的這些二叉樹為: a b a c c / / / b a c c a b / / c b b a 2對給出的任意一個 n（n0），用 F（n）表示其鋪法的總數(shù)的遞推公式為: F（1）=1 F（2）=2 F（n）=F（n-2）+F（n-1）（n3）三、閱讀程序，并寫出程序的正確運行結果（10+16 分，共 26 分）(1) 程序的運行結果是: BBAC(2) 程序的運行結果是: 0.125 0.四、根據(jù)題意，將程序補充完整(每個點 3 分，共 30 分) PAS