資源簡介

第六屆全國青少年信息學（計算機）奧林匹克分區聯賽初賽試題
（提高組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.計算機主機是由CPU與（　　）構成的
A. 控制器　　B. 輸入、輸出設備　　C. 運算器　　D.內存儲器
4.計算機病毒的特點是（　　）
A. 傳播性、潛伏性、易讀性與隱蔽性
　B. 破壞性、傳播性、潛伏性與安全性
C. 傳播性、潛伏性、破壞性與隱蔽性
D. 傳播性、潛伏性、破壞性與易讀性
5.WINDOWS 9X是一種（　　）操作系統
A. 單任務字符方式　　B. 單任務圖形方式
C. 多任務字符方式　　D. 多任務圖形方式
6.Internet的規范譯名應為（　　）
A. 英特爾網　　B. 因特網　　C. 萬維網　　D. 以太網
7.計算機網絡是一個（　　）系統
A.管理信息系統　　 B.管理數據系統
　C.編譯系統　　 D. 在協議控制下的多機互連系統
8.計算機系統總線上傳送的信號有（　　）
A.地址信號與控制信號　　B. 數據信號、控制信號與地址信號
C.控制信號與數據信號　　D. 數據信號與地址信號
9.計算機的運算速度取決于給定的時間內，它的處理器所能處理的數據量。處理器一次能處理的數據量叫字長。 已知64位的奔騰處理器一次能處理64個信息位，相當于（　　）字節。
A.8個　 　B.1個　　C.16個　　D. 2個
10.某種計算機的內存容量是640K，這里的640K容量是指（　　）個字節
A.640　　B. 640*1000　　C. 640*1024　　D. 640*1024*1024
11.下面哪些計算機網絡不是按覆蓋地域劃分的（　　）
A.局域網　　B. 都市網　　C.廣域網　　D. 星型網
12.在有N個葉子節點的哈夫曼樹中，其節點總數為（　　）
A.不確定　　B. 2N-1　　C. 2N+1　　D. 2N
13.已知數組中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
14.不同類型的存儲器組成了多層次結構的存儲器體系，按存取速度從快到慢的排列是（　　）
A.快存/輔存/主存　　B. 外存/主存/輔存
C. 快存/主存/輔存　　D. 主存/輔存/外存
15.某數列有1000個各不相同的單元，由低至高按序排列；現要對該數列進行二分法檢索（binary-search），在最壞的情況下，需檢視（　　）個單元。
A.1000　　B. 10　　C. 100　　D. 500
16.請仔讀下列程序段：
PASCAL語言
Var
　　　a:array[1..3,1..4]of integer;
　　　b:array[1..4,1..3]of integer;
　　　x,y:integer;
　　　begin
　　　　for x:=1to3do
　　　　for y:=1to4do
　　　　　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.
BASIC語言
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
17.線性表若采用鏈表存貯結構，要求內存中可用存貯單元地址（　　）
A.必須連續　　 B. 部分地址必須連續
　C. 一定不連續　　 D. 連續不連續均可
18.下列敘述中，正確的是（　　）
A.線性表的線性存貯結構優于鏈表存貯結構
　B.隊列的操作方式是先進后出
C.棧的操作方式是先進先出
D. 二維數組是指它的每個數據元素為一個線性表的線性表
19.電線上停著兩種鳥（A，B），可以看出兩只相鄰的鳥就將電線分為了一個線段。這些線段可分為兩類；
一類是兩端的小鳥相同；另一類則是兩端的小鳥不相同。
已知：電線兩個頂點上正好停著相同的小鳥，試問兩端為不同小鳥的線段數目一定是（　　）。
A.奇數　　B. 偶數　　C. 可奇可偶　　D. 數目固定
20.一個文本屏幕有25列及80行，屏幕的左上角以（1，1）表示，而右下角則以（80，25）表示，屏幕上每一個字符占用兩字節（byte），整個屏幕則以線性方式存儲在電腦的存儲器內，內屏幕左上角開始，位移為0，然后逐列逐列存儲。求位於屏幕（X，Y）的第一個字節的位移是（　　）
A.（Y*80+X）*2-1　　B.（（Y-1）*80+X-1）*2
C.（Y*80+X-1）*2　　D.（（Y-1）*80+X）*2-1
二、問題求解：（6+6=12分）
1.已知，按中序遍歷二叉樹的結果為：abc
問：有多少種不同形態的二叉樹可以得到這一遍歷結果，并畫出這些二叉樹。
2.設有一個共有n級的樓梯，某人每步可走1級，也可走2級，也可走3級，用遞推公式給出某人從底層開始走完全部樓梯的走法。例如：當n=3時，共有4種走法，即1+1+1，1+2，2+1，3。
三、閱讀程序，并寫出正確的運行結果（每題10分，共20分）
1.PROGRAM NOI_003;
CONST N=7; M=6;
VAR I,J,X0,Y0,X1,Y1,X2,Y2:INTEGER;
D:REAL; P:BOOLEAN; G:ARRAY[0..N,0..M] OF 0..1;
FUNCTION DISP(X1,Y1,X2,Y2:INTEGER):REAL;
BEGIN DISP:=SQRT((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)); END;
BEGIN
FOR I:=0 T0 N DO 　FOR J:=0 TO M DO 　G[I,J]:=0
READLN(X1,Y1,X2,Y2); G[X1,Y1]:=1; G[X2,Y2]:=1; P:=TRUE;
WHILE P DO
BEGIN
P:=FALSE; D:=DISP(X1,Y1,X2,Y2); X0:=X1; Y0:=Y1;
FOR I:=4 TO N DO FOR J:=0 TO M DO
IF (D>DISP(I,J,X2,Y2))AND(G[I,J]=0)THEN
BEGIN D:=DISP(I,J,X2,Y2); X0:=I; Y0:=J; END;
IF(X0<>X1) OR (Y0<>Y1) THEN
BEGIN X1:=X0; Y1:=Y0; P:=TRUE; G[X1,Y1]:=1; END;
D:=DISP(X1,Y1,X2,Y2); X0:=X2; Y0:=Y2;
FOR I:=0 TO 3 DO 　FOR J:=0 TO M DO
IF（DBEGIN D:=DISP(X1,Y1,I,J); X0:=I; Y0:=J END;
IF(X0<>X2)OR(Y0<>Y2) THEN
BEGIN X2:=X0;Y2=Y0;P:=TRUE; G[X2,Y2]:=1; END;
END; WRITELN(X1,Y1,X2,Y2)
END.
輸入：7 6 0 0 　　輸出：
2.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;
IF N>L THEN BEGIN
WHILE SBEGIN 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]));
READLN;
END
ELSE WRITELN(CHR(ORD(’A’)+N-1))
END
輸入： 4 　167 　　輸出：
四、完善程序（共38分）
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+1TO 27 DO（ ②　）
FOR I:=0 TO 31 DO B[1]:=O;
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問題描述
求出一棵樹的深度和寬度。例如有如下的一棵樹：
其樹的深度為從根結點開始到葉結點結束的最大深度，樹的寬度為同一層上結點數的最大值。在上圖中樹的深度為4，寬度為3。
用鄰接表來表示樹，上圖中的樹的鄰接表示如下：
1 2 3 4 0 0
2 0 0 0 0 0
3 5 0 0 0 0
4 6 0 0 0 0
5 0 0 0 0 0
6 7 0 0 0 0
7 0 0 0 0 0
程序清單
PROGRAM NOI00_6;
VAR I,J,SP1,SP2,L,MAX:INTEGER; TREE:ARRAY[1..20,1..6]OF INTEGER;
Q:ARRAY[1..100,0..6] OF INTEGER; D:ARRAY[0..20]OF INTEGER;
BEGIN
FOR I:=1 TO 14 DO FOR J:=1 TO 6 DO TREE[I,J]:=O;
FOR J:=1 TO 14 DO TREE[J,1]:=J;
TREE[1,2]:=2; TREE [1,3]:=3; TREE[1,4]:=4; TREE[2,2]:=5;
TREE[2,3]:=6; TREE [3,2]:=7; TREE[3,3]:=8; TREE[4,2]:=9;
TREE[4,3]:=10; TREE[4,4]:=11; TREE[7,2]:=12;
TREE[7,3]:=13; TREE[13,2]:=14;
SP1:=1; SP2:=1;
FOR I:=1 TO 6 DO Q[1,I]：=TREE[1，I]；
Q[1,0]:=1;
WHILE（　 ①　） DO
BEGIN
L:=（ ② ）; J:=2;
WHILE（ ③ ）DO
BEGIN
SP2:=SP2+1;Q[SP2,0]:=L;Q[SP2,1]:=Q[SP1,J];
FOR I:=2 TO 6 DO
Q[SP2,I]:=TREE[Q[SP1,J],I];
J:=J+1
END;
SP1：=SP1+1
END；
WRITELN（ ④ ）
FOR I:=0 TO 20 DO D[I]:=0;
FOR I:=1 TO SP2 DO
D[Q[I,0]]:=（ ⑤　）
MAX:=D[1];
FOR I:=2 TO 20 DO
IF D[I]>MAX THEN MAX:=D[I];
WRITELN(MAX);
READLN;
END.

展開更多......

收起↑