1、第六屆全國青少年信息學（計算機）奧林匹克分區聯賽初賽試題（提高組PASCAL語言二小時完成）全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 一、選擇一個正確答案代碼（A/B/C/D），填入每題的括號內（每題1.5分，多選無分，共30分）1.下列無符號數中，最小的數是（）A.（11011001）2B.(75)10C.(37)8D.(2A)162.在外部設備中，繪圖儀屬于（）A. 輸入設備B.輸出設備C. 輔(外)存儲器D.主(內)存儲器3.計算機主機是由CPU與（）構成的A. 控制器B. 輸入、輸出設備C. 運算器D.內存儲器4.計算機病毒的特點是（）A. 傳播性、潛伏性、易讀性與隱蔽性B

2、. 破壞性、傳播性、潛伏性與安全性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.計算機的運算速度取決于給定的時間內

3、，它的處理器所能處理的數據量。處理器一次能處理的數據量叫字長。 已知64位的奔騰處理器一次能處理64個信息位，相當于（）字節。A.8個 B.1個C.16個D. 2個10.某種計算機的內存容量是640K，這里的640K容量是指（）個字節A.640B. 640*1000C. 640*1024D. 640*1024*102411.下面哪些計算機網絡不是按覆蓋地域劃分的（）A.局域網B. 都市網C.廣域網D. 星型網12.在有N個葉子節點的哈夫曼樹中，其節點總數為（）A.不確定B. 2N-1C. 2N+1D. 2N13.已知數組中A中，每個元素A（I，J）在存貯時要占3個字節，設I從1變化到8，J從1

4、變化到10，分配內存時是從地址SA開始連續按行存貯分配的。試問：A（5，8）的起始地址為（）A.SA+141B. SA+180C. SA+222D. SA+22514.不同類型的存儲器組成了多層次結構的存儲器體系，按存取速度從快到慢的排列是（）A.快存/輔存/主存B. 外存/主存/輔存C. 快存/主存/輔存D. 主存/輔存/外存15.某數列有1000個各不相同的單元，由低至高按序排列；現要對該數列進行二分法檢索（binary-search），在最壞的情況下，需檢視（）個單元。A.1000B. 10C. 100D. 50016.請仔讀下列程序段：PASCAL語言Vara:array1.3,1.4

5、of integer;b:array1.4,1.3of integer;x,y:integer;beginfor x:=1to3dofor y:=1to4doax,y:=x-y;for x:=4 downto 1 dofor y:=1 to 3 dobx,y:=ay,x;writeln(b3,2);end. BASIC語言DIM A(3,4),B(4,3)FOR X=1 TO 3FOR Y=1 TO 4A(X,Y)=X-YNEXT Y,XFOR X=4 TO 1 STEP -1FOR Y=1 TO 3B(X,Y)=A(Y,X)NEXT Y,XPRINT B(3,2)END上列程序段的正確揄出是

6、（）A.-1B. -2C. -3D. 417.線性表若采用鏈表存貯結構，要求內存中可用存貯單元地址（）A.必須連續 B. 部分地址必須連續C. 一定不連續 D. 連續不連續均可18.下列敘述中，正確的是（）A.線性表的線性存貯結構優于鏈表存貯結構B.隊列的操作方式是先進后出C.棧的操作方式是先進先出D. 二維數組是指它的每個數據元素為一個線性表的線性表19.電線上停著兩種鳥（A，B），可以看出兩只相鄰的鳥就將電線分為了一個線段。這些線段可分為兩類； 一類是兩端的小鳥相同；另一類則是兩端的小鳥不相同。已知：電線兩個頂點上正好停著相同的小鳥，試問兩端為不同小鳥的線段數目一定是（）。A.奇數B. 偶

7、數C. 可奇可偶D. 數目固定20.一個文本屏幕有25列及80行，屏幕的左上角以（1，1）表示，而右下角則以（80，25）表示，屏幕上每一個字符占用兩字節（byte），整個屏幕則以線性方式存儲在電腦的存儲器內，內屏幕左上角開始，位移為0，然后逐列逐列存儲。求位於屏幕（X，Y）的第一個字節的位移是（）A.（Y*80+X）*2-1B.（Y-1）*80+X-1）*2C.（Y*80+X-1）*2D.（Y-1）*80+X）*2-1二、問題求解：（6+6=12分） 1.已知，按中序遍歷二叉樹的結果為：abc問：有多少種不同形態的二叉樹可以得到這一遍歷結果，并畫出這些二叉樹。2.設有一個共有n級的樓梯，某人

8、每步可走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:ARRAY0.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

9、); END;BEGINFOR I:=0 T0 N DO FOR J:=0 TO M DO GI,J:=0 READLN(X1,Y1,X2,Y2); GX1,Y1:=1; GX2,Y2:=1; P:=TRUE; WHILE P DOBEGINP:=FALSE; D:=DISP(X1,Y1,X2,Y2); X0:=X1; Y0:=Y1;FOR I:=4 TO N DO FOR J:=0 TO M DOIF (D>DISP(I,J,X2,Y2)AND(GI,J=0)THENBEGIN D:=DISP(I,J,X2,Y2); X0:=I; Y0:=J; END;IF(X0<>X1)

10、 OR (Y0<>Y1) THENBEGIN X1:=X0; Y1:=Y0; P:=TRUE; GX1,Y1:=1; END;D:=DISP(X1,Y1,X2,Y2); X0:=X2; Y0:=Y2;FOR I:=0 TO 3 DO FOR J:=0 TO M DOIF（D<DISP(X1,Y1,I,J)AND(GI,J=0) THENBEGIN D:=DISP(X1,Y1,I,J); X0:=I; Y0:=J END;IF(X0<>X2)OR(Y0<>Y2) THENBEGIN X2:=X0;Y2=Y0;P:=TRUE; GX2,Y2:=1; END

11、;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:ARRAY1.10 OF 0.9;BEGINREADLN(L,N); S:=L; K:=1; T:=L;IF N>L THEN BEGINWHILE S<N DOBEGIN K:=K+1;T:=T*L;S:=S+T END;S:=S-T;N:=N-S-1;FOR I:=1 TO 10 DO BI:=0;J:=11;WHILE N>0 DOBEGIN J:=J-1; BJ:=N MOD L; N:=

12、N DIV L END;FOR I:=10-K+1 TO 10 DO WRITE(CHR(ORD(A )+BI);READLN;ENDELSE 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，可以

13、得到000，001，010，101，011，111，110，100共8個二進制數且都不相同。程序說明以N=4為例，即有16個0，16個1，數組A用以記錄32個0，1的排法，數組B統計二進制數是否已出現過。程序清單PROGRAM NOI00;VARA :ARRAY1.36 OF 0.1;B :ARRAY0.31 OF INTEGER;I,J,K,S,P:INTEGER;BEGINFOR I:=1 TO 36 DO AI:=0;FOR I:=28 TO 32 DO AI:=1;P:=1;A6:=1;WHILE (P=1) DOBEGINJ:=27;WHILE AJ=1 DO J:=J-1;（）FO

14、R I:=J+1TO 27 DO（ ）FOR I:=0 TO 31 DO B1:=O;FOR I:=1 TO 32 DOBEGIN（）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:=0END;FOR I:=1 TO 32 DO FOR J:=I TO I+4 DO WRITE(AJ);WRITELNEND.2問題描述求出一棵樹的深度和寬度。例如有如下的一棵樹：其樹的深度為從根結點開始到葉結點結束的最大深度，樹的寬度為同一層上結點數的最大值。在上圖中樹的深度為4，寬度為3。用鄰接表來表示

15、樹，上圖中的樹的鄰接表示如下：123400200000350000460000500000670000700000程序清單PROGRAM NOI00_6;VAR I,J,SP1,SP2,L,MAX:INTEGER; TREE:ARRAY1.20,1.6OF INTEGER;Q:ARRAY1.100,0.6 OF INTEGER; D:ARRAY0.20OF INTEGER;BEGINFOR I:=1 TO 14 DO FOR J:=1 TO 6 DO TREEI,J:=O;FOR J:=1 TO 14 DO TREEJ,1:=J;TREE1,2:=2; TREE 1,3:=3; TREE1,4:=4; TREE2,2:=5;TREE2,3:=6; TREE 3,2:=7; TREE3,3:=8; TREE4,2:=9;TREE4,3:=10; TREE4,4:=11; TREE7,2:=12;TREE7,3:=13; TREE13,2:=14;SP1:=1; SP2:=1;FOR I:=1 TO 6 DO Q1,I：=TREE1，I；Q1,0:=1;WHILE（ ） DOBEGINL:=（ ）; J:=2;W