1、第三屆全國青少年信息學（計算機）奧林匹克分區聯賽初賽試題第三屆全國青少年信息學（計算機）奧林匹克分區聯賽初賽試題（初中組）（初中組） （PASCAL 語言語言 競賽用時：競賽用時：2 小時）小時）全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效一、基礎部分： 我國先后自行研制成功“銀河”系列的巨型計算機，其中：“銀河”于 1983 年問世，其運算速度為每秒_次；“銀河”于 1992 年誕生，其運算速度為每秒_次；“銀河”于 1997 年通過國家鑒定，其運算速度為每秒_次。 下列軟件均屬于操作系統的是:_ A. WPS 與 PC DOS B

2、. WINDOWS 與 MS DOS C. WORD 與 WINDOWS D. FOXBASE 與 OS/2 在 MS DOS 的根目錄中，有如下文件： TIME.EXE TIME.COM TIME.BAT 試問：C:TIME 執行的是什么命令？ 設數組 A10.100,20.100 以行優先的方式順序存儲，每個元素占 4 個字節，且已知 A10，20的地址為 1000，則 A50，90的地址是 。 下面是一個求：1/1+1/2+2/3+3/5+5/8+8/13+13/21+21/32前 20 項的和的程序段，試將程序補充完整： S:=0 ;A:=1 ; B:=1 ; FOR K:=1 TO

3、10 DO BEGIN S:=_ ；A：= _ _； S:= _ _ ； B:= _ ； END； WRITELN（S） ； 一個漢字的機內碼目前通常用二個字節來表示：第一個字節是區位碼的區號加（160）10；第二個字節是區位碼的位碼加（160）10 。 已知：漢字“卻”的區位碼是 4020，試寫出機內碼兩個字節的二進制的代碼： 已知ASCII碼表中的大寫字母后有6個其它字符，接著便是小寫字母。現已知： A字母的ASCII碼為（41）16 表示16進制數41 ，試寫出如下字母用十進制表示的 ASCII碼： G （ ）10 B ( )10 T ( )10 下圖中用點表示城市，點與點之間的聯系表示

4、城市間的道路： D C A B 試問： 能否找出一條從 A 城市出發，經過圖中所有道路一次后又回到出發點的通路來？ 能否從 A 出發，找出去每個城市且只去一次的通路來？若能，則寫出通路，否則說明理由。 為了便于處理表達式，常常將普通表達式（稱為中綴表示）轉換為前綴運算符在前，如 X/Y 寫為/XY 和后綴 運算符在后，如 X/Y 寫為 XY/的表達形式。 在這樣的表示中可以不用括號即可確定求值的順序，如： （P+Q）*（R-S）*+PQ-RS 或 PQ + RS -* 試將下面的表達式改寫成前綴與后綴的表示形式： A+B*C/D A-C*D+BE 試將下面的前綴表示還原成中綴的表示形式，同時寫

5、出后綴表示：+A *BC 前綴式中表示一元運算符取負號，如A 表示（-A） 一個將角編了號的正三角形可以繞著外心 O（中心）逆時針旋轉 1200，如下圖所示： 1 3 0 0 2 3 1 2 圖一 圖二 如果將這一旋轉用字母 a 來表示，看作運算對象，同時用 aa 或 a2 表示旋轉1200后再旋轉 1200 ，也就是說將連續運動看作乘法運算，那么三角形狀態（可簡稱為元素）即可與運動表達式關聯起來，請回答： 如果將圖一的原始三角形連續旋轉 1200N 次，簡單地表示為 an （N 為任意自然數） ，試求 an 的值（指三角形旋轉后的結果狀態） ； 如果將下面的旋轉看作是 a 的逆元素，記為 a

6、-1 ，則有 a-1 = a2 試求：a-n 3 1 0 0 1 2 2 3EFaaa 圖三 二、根據題意，補充完善以下程序：1問題描述問題描述 讀入 n 個不相同且不為 0 的數(1=n=100)，不用排序，求出其中第 r個大的數(1rn)，即有 r-1 個數比它大，其余的數都比它小。例如：輸入 3，14，22，15，17，6，其中第 3 個大的數為 15。算法說明算法說明 以數組 a1.100記錄讀入的 n 個數，并以 0 結束（0 本身不是 n 個數中的數） 。然后從第一個數開始，將它與其余的數進行比較并記錄出比它大的數的個數（存于變量 y 中） ，若 y=r-1 時，得到所求結果：否則

7、對下一個數進行同樣的處理。程序清單程序清單 program exp2(input,output) Var r,i,j,k,x,y : integer; a : array1.100 of integer; p : boolean; Begin j:=0; readln(x); while do begin ; aj:=x; end; readln(r); p:=true; i:=1; while p do begin ; y:=0; for k:=1 to j do if x=y do begin r:=r-y; q:=q+1 end;結果，商在 q 中，余數在 r 中。 算法說明算法說明 上

8、面的算法有一個缺點，就是當 x 比較大、y 比較小時，則運算的次數非常多，速度太慢。為提高速度，下面給出改進的算法：先找一個非常接近 x 的數 w，且滿足：w=y2k，y2 k-1=xw，然后通過減法與移位的運算，以較少的運算次數完成除法。程序清單程序清單 program exp3(input,output) var x,y,w,r,q:integer; Begin readln(x); r:=x; while w=w then begin ; R:= ; end; end; writeln(q, , R); End. 3問題描述問題描述 一個正整數（非素數）可表示成它的因子（1 與其本身除外

9、）的乘積。 例如：12 有因子 2，3，4，6，所以可表示為： 12=223=43=26 給出任一個正整數 N，求出它所有的因子乘積的表達式（交換律得出的不同式子算同一種） 。 算法說明算法說明 讀入一個整數 N，首先求出它的所有的因子以及每個因子可能的次數。 例如：整數 48： 因子：2 3 4 6 8 12 16 24 次數：4 1 2 1 1 1 1 1將上面的結果存入數組 A:ARRAY0.20,1.2中。其中：A,1表示因子；A,2表示次數。然后用簡單回溯的方法求出所有可能的表示。數組 B0.20記錄取數情況；C:ARRAY0.20工作單元。程序清單程序清單 program exp4

10、(input,output); var a : array0.20,1.2 of integer; c,b : array0.20 of integer; n,m,I,j,s,k,l : integer; Begin WRITELN;readln(n); for i:=1 to 20 do ai,1:=0; ; a0.2:=1; j:=0; for i:=2 to n-1 do begin s:=0; m:=n; while(m0) and (m mod i=0) do begin m:=m div i; ; end; if then begin j:=j+1; ; aj,2:= ; end

11、end; for i:=0 to j do bi:=0; whil b0=0 do begin k:=j; while do k:=k-1; bk:=bk+1; for L:= do bL:=0; s:=1; for i:=1 to j do if bi0 then for L:=1 to bi do ; if s=n then begin for i:=1 to j do ci:=bi; WRITE(); M:=1; for i:=1 to j do while(ci0) and (MN) do begin M:=MAi.1; if M=N then write(ai,j) else beg

12、in write(Ai,1,); ci:=ci-1; end; end; writeln(); end end End.第三屆全國青少年信息學（計算機）奧林匹克分區聯賽初賽第三屆全國青少年信息學（計算機）奧林匹克分區聯賽初賽（初中組）（初中組） 參參 考考 答答 案案一、基礎部分：共 44 分（1）本題共 3 分。 （1+1+1）相應的運算速度分別為：每秒 1 億次 每秒 10 億次 每秒 100 億次（或 130 億次）（2）本題共 2 分。均屬于操作系統的是： B （3）本題共 2 分。執行的是： 內部命令 TIME 。（4）本題共 3 分。A50，90的地址是： 14240 。（5）本題

13、共 4 分。補充的相應語句為：PASCAL 語言 BASIC 語言 S+A/B 30 S+A/B A+B 40 A+B S+B/A 50 S+B/A A+B 60 A+B （6）本題共 4 分。兩個字節二進制代碼為：11001000，10110100（7）本題共 3 分。如下字母用十進制表示的 ASCII 碼為： G（71）10 b（98）10 t（116）10（8）本題共 6 分（2+4） 。根據問題，回答： 能。例如 ADCEAFCBA 不能。本題的回答要點如下：要到達 D，E，F，B 四個點之一，必須由 A，C出發才可，因為 A，C 只可能出發一次，所以這樣的通路不存在。（9）本題共 8

14、 分（1+1+1+1+2+2） 。 前綴形式為：+A/*BCD；后綴形式為：ABC*D/+ 前綴形式為：+-A*CDBE；后綴形式為：ACD*-BE+ 中綴形式為（-A）+B*（-C） ；后綴形式為：ABC*+（10） 本題共 9 分（3+6） 。 a ,當 n MOD 3=1 時； a2,當 n MOD 3=1 時； a2,當 n MOD 3=2 時； a ,當 n MOD 3=2 時； a3,當 n MOD 3=0 時； a3,當 n MOD 3=0 時；an=a-n=二、根據題目要求，補充完善以下程序：（共 56 分） PASCAL 語言 BASIC 語言（1）共 14 分（2+3+2+3+3+1 分） X0 40 X=0 J:=J+1 50 J=J+1 READLN(X) 60 INPUT X X:=AI 120 Y=Y+1 Y:=Y+1 140 YR-1 Y=R-1 140 GOTO 100 （2）共 17 分（2+3+3+3+3+3 分） W：=Y 25 W=Y W：=W+W 30 W=W