資源簡介

第六屆全國青少年信息學（計算機）奧林匹克分區聯賽試題
（普及組PASCAL語言　二小時完成）
●●全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效●●
一、選擇一個正確答案代碼（A/B/C/D），填入每題的括號內（每題1.5分，多選無分，共30分）
1.下列無符號數中，最小的數是（　　）
A.（11011001）2 B.（75）10 C.（37）8 D.（2A）16
2.在外部設備中，繪圖儀屬于（　　）
A.輸入設備 B.輸出設備 C.輔（外）存儲器 D.主（內）存儲器
3.GB2312-80規定了一級漢字3755個，二級漢字3008個，其中二級漢字字庫中的漢字是以（　　）為序排列的。
A.以筆劃多少 B.以部首 C.以ASCⅡ碼 D.以機內碼
4.算法是指（　　）
A.為解決問題而編制的計算機程序
B.為解決問題而采取的方法與步驟
C.為解決問題而需要采用的計算機語言
D.為解決問題而采用的計算方法
5.RAM中的信息是（　　）
A.生產廠家預先寫入的 B.計算機工作時隨機寫入的
C.防止計算機病毒侵入所使用的 D.專門用于計算機開機時自檢用的
6.計算機主機是由CPU與（　　）構成的
A.控制器 B.運算器 C.輸入、輸出設備 D.內存儲器
7.計算機病毒的特點（　　）
A.傳播性、潛伏性、易讀性與隱蔽性
B.破壞性、傳播性、潛伏性與安全性
C.傳播性、潛伏性、破壞性與隱蔽性
D.傳播性、潛伏性、破壞性與易讀性
8.設循環隊列中數組的下標范圍是1～n，其頭尾指針分別為f和r，則其元素個數為（　　）
A.r-f B.r-f+1 C.(r-f)　MOD　n+1 D.(r-f+n)　MOD　n
9.在待排序的數據表已經為有序時，下列排序算法中花費時間反而多的是（　　）
A.堆排序 B.因特網 C.冒泡排序 D.快速排序
10.Internet的規范譯名應為（　　）
A.英特爾網B.因特網C.萬維網D.以太網
11.WINDOWS9x是一種（　　）操作系統
A.單任務字符方式 B.單任務圖形方式
C.多任務字符方式 D.多任務圖形方式
12.某種計算機的內存容量是640K，這里的640K容量是指（　　）個字節
A.640 B.640*1000 C.640*1024 D.640*1024*1024
13.在Windows9x中，菜單項后帶有符號“…”，表示該菜單項（　　）
A.可以進行開關選擇 B.執行時有對話框 C.有若干子命令 D.不能執行
14.某數列有1000個各不相同的單元，由低至高按序排列；現要對該數列進行二分法檢索（binary search），在最壞的情況下，需檢視（　　）個單元
A.1000 B.10 C.100 D.500
15.已知數組A中，每個元素A[I,J]在存貯時要占3個字節，設I從1變化到8，J從1變化到10，分配內存時是從地址SA開始連續按行存貯分配的。試問：A[5,8]的起始地址為（　　）
A.SA+141 B.SA+180 C.SA+222 D.SA+225
16.不同類型的存儲器組成了多層次結構的存儲器體系,按存取速度從快到慢的排列是（　　　）
A.快存/輔存/主存 B.外存/主存/輔存
C.快存/主存/輔存 D.主存/輔存/外存
17.線性表若采用鏈表存貯結構,要求內存中可用存貯單元地址（　　）
A.必須連續 B.部分地址必須連續
C.一定不連續 D.連續不連續均可
18.下列敘述中,正確的是（　　）
A.線性表的線性存貯結構優于鏈表存貯結構
B.隊列的操作方式是先進后出
C.棧的操作方式是先進先出
D.二維數組是指它的每個數據元素為一個線性表的線性表
19.電線上停著兩種鳥(A,B),可以看出兩只相鄰的鳥就將電線分為了一個線段。這些線段可分為兩類:
一類是兩端的小鳥相同;另一類則是兩端的小鳥不相同。
已知:電線兩個頂點上正好停著相同的小鳥,試問兩端為不同小鳥的線段數目一定是（　　）
A.奇數 B.偶數 C.可奇可偶 D.數目固定
20.請仔細閱讀下列程序段:
PASCAL語言 BASIC語言
var
　　　 a:array[1..3,1..4]of
integer;
　　　 b:array[1..4,1..3]of
integer;
　　　 x,y:integer;
　　 　begin
　　　 　　for x:=1 to 3 do
　　　　　　for y:=1 to 4 do
　　　　　　 　a[x,y]:=x-y;
　　　 　　 for x:=4 downto 1 do
　　　　　　　for y:=1 to 3 do
　　　　　　 　b[x,y]:=a[y,x];
　　　 　　 writeln(b[3,2]);
　　 　end. DIM A(3,4),B(4,3)
FOR X=1 TO 3
FOR Y=1 TO 4
A(X,Y)=X-Y
NEXT Y,X
FOR X=4 TO 1 STEP-1
FOR Y=1 TO 3
B(X,Y)=A(Y,X)
NEXT Y,X
PRINT B(3,2)
END
上列程序段的正確輸出是（　　）
A.-1 B.-2 C.-3 D.-4
二、問題解答：（每題7分，共14分）
1.已知，按中序遍歷二叉樹的結果為：abc
問：有多少種不同形態的二叉樹可以得到這一遍歷結果，并畫出這些二叉樹。
2.有2×n的一個長方形方格，用一個1×2的骨牌鋪滿方格。例如n=3時，為2×3方格。
此時用一個1×2的骨牌鋪滿方格，共有3種鋪法：
試對給出的任意一個n(n)0)，求出鋪法總數的遞推公式。
三、閱讀程序，并寫出程序正確的運行結果（10+16分，共26分）
　1.PROGRAM NOI__002;
　　　　VAR I,J,L,N,K,S,T: INTEGER;
　　　　　　B　　　　　　: ARRAY[1..10] OF 0..9;
　　　BEGIN
　　　　 READLN(L,N);S:=L;　　K:=1;　　T:=L;
　　　　 WHILE S　　　　 BEGIN K:=K+1;　　T:=T*L;　　 S:=S+T　　END;
　　　　 S:=S-T; N:=N-S-1;
　　　　 FOR I:=1 TO 10 DO　　B[I]:=0;
　　　　 J:=11;
　　　　 WHILE N>0 DO
　　　　　BEGIN　　J:=J-1;　　B[J]:=N MOD L;　　N:=N DIV L　　END;
　　　　 FOR I:=10-K+1 TO 10 DO WRITE(CHR(ORD('A')+B[I]));
　　　END
　　輸入：4　　167
輸出：
2.PROGRAM NOI__004;
　　　　VAR　I,J,J1,J2,P,Q: INTEGER;
　　　　　　 P1　　　　　 : BOOLEAN;
　　　　　　 B,C　　　　　: ARRAY[1..100] OF INTEGER;
　　　　BEGIN
　　　　　 READLN(Q,P);　　J:=1;　　P1:=TRUE;　　B[J]:=Q;　　J1:=0;
　　　　　 WHILE　（Q>0） AND P1 DO
　　　　　　BEGIN
　　　　　　　J1:=J1+1;　C[J1]:=Q*10　DIV P;　Q:=Q*10-C[J1]*P;
　　　　　　　IF Q>Q THEN BEGIN
　　　　　　　　　　　　　 J2:=1;
　　　　　　　　　　　　　 WHILE (B[J2]<>Q) AND (J2<=J) DO　　J2:=J2+1;
　　　　　　　　　　　　　　IF B[J2]=Q THEN
　　　　　　　　　　　　　　　BEGIN
　　　　　　　　　　　　　　　　P1:=FALSE;　　WRITE('0.');
　　　　　　　　　　　　　　　　FOR I:=1 TO J2-1 DO　　WRITE(C[I]:1);
　　　　　　　　　　　　　　　　WRITE('{'};
　　　　　　　　　　　　　　　　FOR I:=J2 TO J1 DO　　WRITE(C[I]:1);
　　　　　　　　　　　　　　　　WRITELN(')')
　　　　　　　　　　　　　　　END
　　　　　　　　　　ELSE　　BEGIN　　J:=J+1;　　B[J]:=Q　　END
　　　　　　　END
　　　　　　END;
　　　　　 IF Q=0 THEN BEGIN
　　　　　　　　　　　　　WRITE('0.');
　　　　　　　　　　　　　FOR I:=1 TO J1 DO　　WRITE(C[I]:1);
　　　　　　　　　　　　　WRITELN
　　　　　　　　　　　　END;
　　　　　　READLN
　　　END.　　
　　　輸入　　①1　　8　　輸出
　　　輸入　　②2　　7　　輸出
四、完善程序（每題15分，共30分）
1.將2n個0和2n個1，排成一圈。從任一個位置開始，每次按逆時針的方向以長度為n+1的單位進行數二進制數。
要求給出一種排法，用上面的方法產生出來的2n+1個二進制數都不相同。
　例如，當n=2時，即22個0和22個1排成如下一圈：
　　　比如，從A位置開始，逆時針方向取三個數000，然后再從B位置上開始取三個數001，接著從C開始取三個數010，...可以得到000，001，010，101，011，111，110，100共8個二進制數且都不相同。
　　程序說明
　以n=4為例，即有16個0，16個1，
　　　　數組a用以記錄32個0，1的排法，
　　　　數組b統計二進制數出現的可能性。
　程序清單
　PROGRAM NOI00;
　　VAR
　　　A　　　　:ARRAY[1..36] OF 0..1
　　　B　　　　:ARRAY[0..31] OF INTEGER;
　　　I,J,K,S,P:INTEGER;
　　　BEGIN
　　　　FOR I:=1 TO 36 DO　　A[I]:=0;
　　　　 FOR I:=28 TO 32 DO　　A[I]:=1;
　　　　P:=1;　　A[6]:=1;
　　　　WHILE (P=1) DO
　　　　　BEGIN
　　　　　　J:=27
　　　　　　WHILE A[J]=1 DO　　J:=J-1;
　　　　　　(　①　)
　　　　　　FOR I:=J+1 TO 27 DO (　②　)
　　　　　　FOR I:=0 TO 31 DO B[I]:=0;
　　　　　　FOR I:=1 TO 32 DO
　　　　　　 BEGIN
　　　　　　　(　③　)
　　　　　　　　FOR K:=I TO I+4 DO　　S:=S*2+A[k];
　　　　　　　　(　④　)
　　　　　　 END;
　　　　　　S:=0;
　　　　　　FOR I:=0 TO 31 DO　　S:=S+B[I];
　　　　　　IF (　⑤　) THEN P:=0
　　　　　END;
　 　　　FOR I:=1 TO 32 DO　　FOR J:=I TO I+4 DO　　WRITE(A[J]);
　　　WRITELN
　　END.
2.多項式的乘法。
　例如有如下多項式：
　P(X)=2X2-X+1,Q(X)=X+1
則：　P(X)·Q(X)=(2X2-X+1)(X+1)=2X3+X2+1
程序說明：
多項式的表示：系數、指數
　　如上例中：　P(X):　　系數　　指數　　　　Q(X)　　系數　　指數
　　　　　　　　　　　　　　　2　　　　2　　　　　　　　　1　　　　1
　　　　　　　　　　　　　　　-1　　　 1　　　　　　　　　1　　　　0
　　　　　　　　　　　　　　　1　　　　0　　　　　　　　　0　　　　0
　　　　　　　　　　　　　　　0　　　　0
　　　　PXQ的結果存入C中。其輸出格式是：依次用一對括號內的（系數，指數）分別來表示。如上例的
　　輸出結果表示為：（2，3）（1，2）（1，0）
　程序清單
　　PROGRAM NOI__007;
　　　VAR
　　　　　I,J,K,L,JP,JQ,JC,X,Y,X1,Y1: INTEGER;
　　　　　P,Q　　　　　:ARRAY[1..10,1..2] OF INTEGER;
　　　　　C　　　　　　:ARRAY[1..20,1..2] OF INTEGER;
　　　BEGIN
　　　　JP:=0;
　　　　READLN(X,Y) ;
　　　　WHILE X<>0 DO
　　　　 BEGIN　　JP:=JP+1;　P[JP,1]:=X;　P[JP,2]:=Y;　READLN(X,Y)　END;
　　　　JQ:=0;
　　　　READLN(X,Y);
　　　　WHILE X<>0 DO
　　　　 BEGIN　JQ:=JQ+1;　Q[JQ,1]:=X;　Q[JQ,2:]=Y;　READLN(X,Y)　END;
　　　　JC:=1　　C[JC,1]:=0;　　C[JC,2]:=-1000;
　　　　FOR I:=1 TO JP DO
　　　　　BEGIN
　　　　　　(　①　)
　　　　　　　Y:=P[I,2];
　　　　　　FOR J:=1 TO JQ DO
　　　　　　　BEGIN
　　　　　　　　(　②　)
　　　　　　　　Y1:=Y+Q[J,2];
　　　　　　　　K:=1;
　　　　　　　　WHILE Y1　　　　　　　　IF Y1=C[K,2] THEN (　③　)
　　　　　　　　　　　　　　 ELSE
　　　　　　　　　　　　　　　　BEGIN
　　　　　　　　　　　　　　　　　FOR L:=JC DOWNTO K DO
　　　　　　　　　　　　　　　　　　BEGIN
　　　　　　　　　　　　　　　　　　　C[L+1,1]:=C[L,1];
　　　　　　　　　　　　　　　　　　　C[L+1,2]:=C[L,2]
　　　　　　　　　　　　　　　　　　END;
　　　　　　　　　　　　　　　　　　C[K,1]:=X1; C[K,2]:=Y1;
　　　　　　　　　　　　　　　　　　(　④　)
　　　　　　　　　　　　　　　　END
　　　　　　　END
　　　　　END;
　　　　FOR I:=1 TO JC DO
　　　　　IF (　⑤　) THEN WRITE('(',C[I,1],',',C[I,2],')');
　　　　READLN
　　END.

展開更多......

收起↑